0

I have N lists of items

eg:

  • A, B, C, D
  • 1, 2, 3
  • V, W, X, Y, Z

They are flattened into a single long list, and the user chooses an ordering to their liking

eg:

1, C, X, 3, B, A, Y, Z, 2, W, D, V

I need to re-order my N original lists so their relative sort order matches that in the user's ordering

eg:

  • C, B, A, D
  • 1, 3, 2
  • X, Y, Z, W, V

The simple brute-force approach is to create N new empty containers, loop over the user's ordering and add each item into the relevant container as it is encountered.

Is there a more elegant approach?

2 Answers 2

1

There is not possibly a more elegant approach unless assumptions can be made about the ordering of the data.

You must, at some point, create each of the N new containers.

You must also, at some point, add the necessary elements to those N containers.

These two things cannot be avoided. Your approach has both of those and nothing more, and thus is proved minimal.

A minor caveat is that block array copies are slightly faster than iterative copies, so if you know of large blocks that are the same, then you can make a slightly faster copy for those blocks. But usually, in order to get that information, you must first visit and analyze the data. So instead of visiting and analyzing, you should just visit and insert.

2
  • I was thinking perhaps something along the lines of swapping elements to their sorted position in their respective containers as they are encountered in the sorted list, thus negating the need for N new containers, but it's escaping me Commented Jun 7, 2018 at 22:12
  • 1
    If you're fine overwriting the existing data in the original lists, you can do that. Once the data is out of the original lists and in the big list for the user to copy, you can just go for(List list : lists) list.clear(); for(item x : bigList) { getListFor(x).add(x); } sure - but you can't avoid visiting each element in the big array at least once.
    – corsiKa
    Commented Jun 7, 2018 at 22:17
1

You must either store the knowledge of which container an element came from at the beginning, or else store a mapping of element to position in the list and use that for sorting. (Or else save memory and do a ton of searching.)

If you're going to rearrange all lists, then it is more efficient to store the knowledge of which container each element comes from and proceed as you suggest. If you're going to only rearrange SOME lists (or rearrange future lists), then it may make more sense to store the mapping of element to position in the list and sort based on that. Which you can do either with a comparison function that goes through that lookup, or with a Schwartzian transform.

BTW have you thought about how to handle repeated elements?

1
  • each element is unique, so repeated elements is not an issue Commented Jun 7, 2018 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.