python - How to sort two lists (which reference each other) in the exact same way

Question

Say I have two lists:

list1 = [3, 2, 4, 1, 1]
list2 = ['three', 'two', 'four', 'one', 'one2']

If I run list1.sort(), it'll sort it to [1,1,2,3,4] but is there a way to get list2 in sync as well (so I can say item 4 belongs to 'three')? So, the expected output would be:

list1 = [1, 1, 2, 3, 4]
list2 = ['one', 'one2', 'two', 'three', 'four']

My problem is I have a pretty complex program that is working fine with lists but I sort of need to start referencing some data. I know this is a perfect situation for dictionaries but I'm trying to avoid dictionaries in my processing because I do need to sort the key values (if I must use dictionaries I know how to use them).

Basically the nature of this program is, the data comes in a random order (like above), I need to sort it, process it and then send out the results (order doesn't matter but users need to know which result belongs to which key). I thought about putting it in a dictionary first, then sorting list one but I would have no way of differentiating of items in the with the same value if order is not maintained (it may have an impact when communicating the results to users). So ideally, once I get the lists I would rather figure out a way to sort both lists together. Is this possible?

Answer 1

One classic approach to this problem is to use the "decorate, sort, undecorate" idiom, which is especially simple using python's built-in zip function:

>>> list1 = [3,2,4,1, 1]
>>> list2 = ['three', 'two', 'four', 'one', 'one2']
>>> list1, list2 = zip(*sorted(zip(list1, list2)))
>>> list1
(1, 1, 2, 3, 4)
>>> list2 
('one', 'one2', 'two', 'three', 'four')

These of course are no longer lists, but that's easily remedied, if it matters:

>>> list1, list2 = (list(t) for t in zip(*sorted(zip(list1, list2))))
>>> list1
[1, 1, 2, 3, 4]
>>> list2
['one', 'one2', 'two', 'three', 'four']

It's worth noting that the above may sacrifice speed for terseness; the in-place version, which takes up 3 lines, is a tad faster on my machine for small lists:

>>> %timeit zip(*sorted(zip(list1, list2)))
100000 loops, best of 3: 3.3 us per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100000 loops, best of 3: 2.84 us per loop

On the other hand, for larger lists, the one-line version could be faster:

>>> %timeit zip(*sorted(zip(list1, list2)))
100 loops, best of 3: 8.09 ms per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100 loops, best of 3: 8.51 ms per loop

As Quantum7 points out, JSF's suggestion is a bit faster still, but it will probably only ever be a little bit faster, because Python uses the very same DSU idiom internally for all key-based sorts. It's just happening a little closer to the bare metal. (This shows just how well optimized the zip routines are!)

I think the zip-based approach is more flexible and is a little more readable, so I prefer it.