1

Is there an algorithm better than O(n^2) for re-ordering List 2 to match List 1

List 1 : A B C D

List 2 : B D C A

note: List 2 can have more, less or even completely different items compared to List 1.

vtbose
  • 325
  • 1
  • 3
  • 15
  • 1
    Do you know anything special about the contents of the two lists? If the elements of list 1 and 2 are the same, it seems like you can just copy list 1 into list 2. If not, what do you do if you encounter an item in list 2 that isn't in list 1? Where does that get sorted to? – Dave McClelland Nov 29 '10 at 15:36
  • 3
    can clarify? what is re-ordering? is it finding the permutation from list 2 to list 1? – lijie Nov 29 '10 at 15:37
  • the edit just made things less clear! how does one reorder a list A to another list B when the elements may be different?! – lijie Nov 29 '10 at 16:29
  • What n is? Length of List 1 or List 2 or list1+list2? – Fabio Filippi Nov 29 '10 at 18:24

2 Answers2

1

If you can create a total-ordering for the type of items in the lists, then you can create an index for list 1 by sorting the items. You can then use this index to re-order list 2. This algorithm is O(n log n) in time, and requires an extra O(n) in space.

Jeffrey L Whitledge
  • 58,241
  • 9
  • 71
  • 99
0

One possibility that would result in O(n Log(n)) would be the following. This requires reading the list values into an array/vector/sortable type of structure:

  • Sort list 1 based on value and keep the position information. This provides a quick way to look up an item and know its position. The cost for the sort is O(n log n)
  • Sort list 2 using the sorted list from the first step as the compare function. Two compare two values, look them up in the sorted list 1 results and use the relative positions as the comparison between the two values. The cost of this sort is also O(n log n).

After the edit, you mention that the second list may have no correlation to the first list. So the comparison function would have to take that into account. If one or both values being compared are not in the first list, then the compare function needs to make a decision on ordering the values (e.g., do they go at the end or the beginning?).

Mark Wilkins
  • 40,729
  • 5
  • 57
  • 110