[python] how to return index of a sorted list?

I need to sort a list and then return a list with the index of the sorted items in the list. For example, if the list I want to sort is [2,3,1,4,5], I need [2,0,1,3,4] to be returned.

This question was posted on bytes, but I thought I would repost it here. http://bytes.com/topic/python/answers/44513-sorting-list-then-return-index-sorted-item

My specific need to sort a list of objects based on a property of the objects. I then need to re-order a corresponding list to match the order of the newly sorted list.

Is there a good way to do this?

What I would do, looking at your specific need:

Say you have list a with some values, and your keys are in the attribute x of the objects stored in list b

keys = {i:j.x for i,j in zip(a, b)}
a.sort(key=keys.__get_item__)

With this method you get your list ordered without having to construct the intermediate permutation list you were asking for.

you can use numpy.argsort

or you can do:

test =  [2,3,1,4,5]
idxs = list(zip(*sorted([(val, i) for i, val in enumerate(test)])))[1]

zip will rearange the list so that the first element is test and the second is the idxs.

You can do this with numpy's argsort method if you have numpy available:

>>> import numpy
>>> vals = numpy.array([2,3,1,4,5])
>>> vals
array([2, 3, 1, 4, 5])
>>> sort_index = numpy.argsort(vals)
>>> sort_index
array([2, 0, 1, 3, 4])

If not available, taken from this question, this is the fastest method:

>>> vals = [2,3,1,4,5]
>>> sorted(range(len(vals)), key=vals.__getitem__)
[2, 0, 1, 3, 4]

Straight out of the documentation for collections.OrderedDict:

>>> # dictionary sorted by value
>>> OrderedDict(sorted(d.items(), key=lambda t: t[1]))
OrderedDict([('pear', 1), ('orange', 2), ('banana', 3), ('apple', 4)])

Adapted to the example in the original post:

>>> l=[2,3,1,4,5]
>>> OrderedDict(sorted(enumerate(l), key=lambda x: x[1])).keys()
[2, 0, 1, 3, 4]

See http://docs.python.org/library/collections.html#collections.OrderedDict for details.

If you need both the sorted list and the list of indices, you could do:

L = [2,3,1,4,5]
from operator import itemgetter
indices, L_sorted = zip(*sorted(enumerate(L), key=itemgetter(1)))
list(L_sorted)
>>> [1, 2, 3, 4, 5]
list(indices)
>>> [2, 0, 1, 3, 4]

Or, for Python <2.4 (no itemgetter or sorted):

temp = [(v,i) for i,v in enumerate(L)]
temp.sort
indices, L_sorted = zip(*temp)

p.s. The zip(*iterable) idiom reverses the zip process (unzip).

Update:

To deal with your specific requirements:

"my specific need to sort a list of objects based on a property of the objects. i then need to re-order a corresponding list to match the order of the newly sorted list."

That's a long-winded way of doing it. You can achieve that with a single sort by zipping both lists together then sort using the object property as your sort key (and unzipping after).

combined = zip(obj_list, secondary_list)
zipped_sorted = sorted(combined, key=lambda x: x[0].some_obj_attribute)
obj_list, secondary_list = map(list, zip(*zipped_sorted))

Here's a simple example, using strings to represent your object. Here we use the length of the string as the key for sorting.:

str_list = ["banana", "apple", "nom", "Eeeeeeeeeeek"]
sec_list = [0.123423, 9.231, 23, 10.11001]
temp = sorted(zip(str_list, sec_list), key=lambda x: len(x[0]))
str_list, sec_list = map(list, zip(*temp))
str_list
>>> ['nom', 'apple', 'banana', 'Eeeeeeeeeeek']
sec_list
>>> [23, 9.231, 0.123423, 10.11001]

How about

l1 = [2,3,1,4,5]
l2 = [l1.index(x) for x in sorted(l1)]