Sorting based on one of the list among Nested list in python

Question

I have a list as [[4,5,6],[2,3,1]]. Now I want to sort the list based on list[1] i.e. output should be [[6,4,5],[1,2,3]]. So basically I am sorting 2,3,1 and maintaining the order of list[0].

While searching I got a function which sorts based on first element of every list but not for this. Also I do not want to recreate list as [[4,2],[5,3],[6,1]] and then use the function.

Answer 1

Since [4, 5, 6] and [2, 3, 1] serves two different purposes I will make a function taking two arguments: the list to be reordered, and the list whose sorting will decide the order. I'll only return the reordered list.

This answer has timings of three different solutions for creating a permutation list for a sort. Using the fastest option gives this solution:

def pyargsort(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)

def using_pyargsort(a, b):
    "Reorder the list a the same way as list b would be reordered by a normal sort"
    return [a[i] for i in pyargsort(b)]                     

print using_pyargsort([4, 5, 6], [2, 3, 1])    # [6, 4, 5]

The pyargsort method is inspired by the numpy argsort method, which does the same thing much faster. Numpy also has advanced indexing operations whereby an array can be used as an index, making possible very quick reordering of an array.

So if your need for speed is great, one would assume that this numpy solution would be faster:

import numpy as np

def using_numpy(a, b):
    "Reorder the list a the same way as list b would be reordered by a normal sort"
    return np.array(a)[np.argsort(b)].tolist()

print using_numpy([4, 5, 6], [2, 3, 1])     # [6, 4, 5]

However, for short lists (length < 1000), this solution is in fact slower than the first. This is because we're first converting the a and b lists to array and then converting the result back to list before returning. If we instead assume you're using numpy arrays throughout your application so that we do not need to convert back and forth, we get this solution:

def all_numpy(a, b):
    "Reorder array a the same way as array b would be reordered by a normal sort"
    return a[np.argsort(b)]

print all_numpy(np.array([4, 5, 6]), np.array([2, 3, 1]))    # array([6, 4, 5])

The all_numpy function executes up to 10 times faster than the using_pyargsort function.

The following logaritmic graph compares these three solutions with the two alternative solutions from the other answers. The arguments are two randomly shuffled ranges of equal length, and the functions all receive identically ordered lists. I'm timing only the time the function takes to execute. For illustrative purposes I've added in an extra graph line for each numpy solution where the 60 ms overhead for loading numpy is added to the time.

As we can see, the all-numpy solution beats the others by an order of magnitude. Converting from python list and back slows the using_numpy solution down considerably in comparison, but it still beats pure python for large lists.

For a list length of about 1'000'000, using_pyargsort takes 2.0 seconds, using_nympy + overhead is only 1.3 seconds, while all_numpy + overhead is 0.3 seconds.

Answer 2

The sorting you describe is not very easy to accomplish. The only way that I can think of to do it is to use zip to create the list you say you don't want to create:

lst = [[4,5,6],[2,3,1]]
# key = operator.itemgetter(1) works too, and may be slightly faster ...
transpose_sort = sorted(zip(*lst),key = lambda x: x[1])
lst = zip(*transpose_sort)

Is there a reason for this constraint?

(Also note that you could do this all in one line if you really want to:

lst = zip(*sorted(zip(*lst),key = lambda x: x[1]))

This also results in a list of tuples. If you really want a list of lists, you can map the result:

lst = map(list, lst)

Or a list comprehension would work as well:

lst = [ list(x) for x in lst ]

Answer 3

If the second list doesn't contain duplicates, you could just do this:

l = [[4,5,6],[2,3,1]]   #the list
l1 = l[1][:]            #a copy of the to-be-sorted sublist
l[1].sort()             #sort the sublist
l[0] = [l[0][l1.index(x)] for x in l[1]] #order the first sublist accordingly

(As this saves the sublist l[1] it might be a bad idea if your input list is huge)

Answer 4

How about this one:

a = [[4,5,6],[2,3,1]]
[a[0][i] for i in sorted(range(len(a[1])), key=lambda x: a[1][x])]

It uses the principal way numpy does it without having to use numpy and without the zip stuff.

Neither using numpy nor the zipping around seems to be the cheapest way for giant structures. Unfortunately the .sort() method is built into the list type and uses hard-wired access to the elements in the list (overriding __getitem__() or similar does not have any effect here).

So you can implement your own sort() which sorts two or more lists according to the values in one; this is basically what numpy does.

Or you can create a list of values to sort, sort that, and recreate the sorted original list out of it.