308

I have a numerical list:

myList = [1, 2, 3, 100, 5]

Now if I sort this list to obtain [1, 2, 3, 5, 100]. What I want is the indices of the elements from the original list in the sorted order i.e. [0, 1, 2, 4, 3] --- ala MATLAB's sort function that returns both values and indices.

9
  • 2
    Related: stackoverflow.com/questions/7851077/…
    – kevinarpe
    Commented Oct 25, 2014 at 18:30
  • @unutbu This is not a dupe (IMO). The question does not contradict using Numpy.argsort()
    – amit
    Commented Jun 4, 2015 at 22:35
  • @amit: What do you mean by "does not contradict"?
    – unutbu
    Commented Jun 4, 2015 at 22:38
  • 3
    Unfortunately, this question has a severe flaw in its choice of example, as two different ways of reading the question would give the same answer when the input is just a transposition out of sorted order.
    – user1084944
    Commented Jun 5, 2015 at 17:49
  • 2
    order vs rank
    – djvg
    Commented Jun 16, 2021 at 12:44

18 Answers 18

293

If you are using numpy, you have the argsort() function available:

>>> import numpy
>>> numpy.argsort(myList)
array([0, 1, 2, 4, 3])

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

This returns the arguments that would sort the array or list.

1
219

Something like next:

>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]

enumerate(myList) gives you a list containing tuples of (index, value):

[(0, 1), (1, 2), (2, 3), (3, 100), (4, 5)]

You sort the list by passing it to sorted and specifying a function to extract the sort key (the second element of each tuple; that's what the lambda is for. Finally, the original index of each sorted element is extracted using the [i[0] for i in ...] list comprehension.

6
  • 9
    you can use itemgetter(1) instead of the lambda function Commented Jun 21, 2011 at 10:26
  • 4
    @gnibbler is referring to the itemgetter function in the operator module, FYI. So do from operator import itemgetter to use it. Commented Jun 21, 2011 at 11:12
  • 2
    you can get the sorted list and indicies by using zip: sorted_items, sorted_inds = zip(*sorted([(i,e) for i,e in enumerate(my_list)], key=itemgetter(1)))
    – Charles L.
    Commented Nov 30, 2015 at 2:58
  • 3
    @RomanBodnarchuk this doesn't work, x = [3,1,2]; numpy.argsort(x) yields [1,2,0].
    – Dawn
    Commented May 14, 2019 at 8:50
  • Adding to @JohnLaRooy, you can use itemgetter to do the indexing in both cases, e.g. sorted_indices = list(map(itemgetter(0), sorted(enumerate(myList), key=itemgetter(1)))). Alternatively, since indexing is one of those weirdly slow things in Python, you can continue to use the listcomp, and use unpacking instead of indexing: [i for i, _ in sorted(enumerate(myList), key=itemgetter(1))] Commented Feb 6, 2023 at 19:37
96
myList = [1, 2, 3, 100, 5]    
sorted(range(len(myList)),key=myList.__getitem__)

[0, 1, 2, 4, 3]
2
54

I did a quick performance check on these with perfplot (a project of mine) and found that it's hard to recommend anything else but

np.argsort(x)

(note the log scale):

enter image description here


Code to reproduce the plot:

import perfplot
import numpy as np


def sorted_enumerate(seq):
    return [i for (v, i) in sorted((v, i) for (i, v) in enumerate(seq))]


def sorted_enumerate_key(seq):
    return [x for x, y in sorted(enumerate(seq), key=lambda x: x[1])]


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


b = perfplot.bench(
    setup=np.random.rand,
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, np.argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
)
b.save("out.png")
1
  • It's also very nice to see the shortest pure python solution was the fastest as the PEPs intended! Commented Oct 27, 2021 at 13:51
27

The answers with enumerate are nice, but I personally don't like the lambda used to sort by the value. The following just reverses the index and the value, and sorts that. So it'll first sort by value, then by index.

sorted((e,i) for i,e in enumerate(myList))
16

Updated answer with enumerate and itemgetter:

sorted(enumerate(a), key=lambda x: x[1])
# [(0, 1), (1, 2), (2, 3), (4, 5), (3, 100)]

Zip the lists together: The first element in the tuple will the index, the second is the value (then sort it using the second value of the tuple x[1], x is the tuple)

Or using itemgetter from the operatormodule`:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))
1
  • 1
    enumerate seems more appropriate than zip in this case
    – njzk2
    Commented May 21, 2013 at 12:33
10

Essentially you need to do an argsort, what implementation you need depends if you want to use external libraries (e.g. NumPy) or if you want to stay pure-Python without dependencies.

The question you need to ask yourself is: Do you want the

  • indices that would sort the array/list
  • indices that the elements would have in the sorted array/list

Unfortunately the example in the question doesn't make it clear what is desired because both will give the same result:

>>> arr = np.array([1, 2, 3, 100, 5])

>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)

>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)

Choosing the argsort implementation

If you have NumPy at your disposal you can simply use the function numpy.argsort or method numpy.ndarray.argsort.

An implementation without NumPy was mentioned in some other answers already, so I'll just recap the fastest solution according to the benchmark answer here

def argsort(l):
    return sorted(range(len(l)), key=l.__getitem__)

Getting the indices that would sort the array/list

To get the indices that would sort the array/list you can simply call argsort on the array or list. I'm using the NumPy versions here but the Python implementation should give the same results

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)

The result contains the indices that are needed to get the sorted array.

Since the sorted array would be [1, 2, 3, 4] the argsorted array contains the indices of these elements in the original.

  • The smallest value is 1 and it is at index 1 in the original so the first element of the result is 1.
  • The 2 is at index 2 in the original so the second element of the result is 2.
  • The 3 is at index 0 in the original so the third element of the result is 0.
  • The largest value 4 and it is at index 3 in the original so the last element of the result is 3.

Getting the indices that the elements would have in the sorted array/list

In this case you would need to apply argsort twice:

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)

In this case :

  • the first element of the original is 3, which is the third largest value so it would have index 2 in the sorted array/list so the first element is 2.
  • the second element of the original is 1, which is the smallest value so it would have index 0 in the sorted array/list so the second element is 0.
  • the third element of the original is 2, which is the second-smallest value so it would have index 1 in the sorted array/list so the third element is 1.
  • the fourth element of the original is 4 which is the largest value so it would have index 3 in the sorted array/list so the last element is 3.
8

If you do not want to use numpy,

sorted(range(len(seq)), key=seq.__getitem__)

is fastest, as demonstrated here.

1
8

The other answers are WRONG.

Running argsort once is not the solution. For example, the following code:

import numpy as np
x = [3,1,2]
np.argsort(x)

yields array([1, 2, 0], dtype=int64) which is not what we want.

The answer should be to run argsort twice:

import numpy as np
x = [3,1,2]
np.argsort(np.argsort(x))

gives array([2, 0, 1], dtype=int64) as expected.

5
  • 1
    Your claim makes x[2] (3) the smallest element, and x[1] (1) the largest element (since sorting integers orders them from smallest value to largest value). Also, with the OPs example, a single np.argsort([1, 2, 3, 100, 5]) yields array([0, 1, 2, 4, 3]), which appears to be the indices the OP wants.
    – 9769953
    Commented Jan 17, 2020 at 13:51
  • 1
    @0 0 your example is a specific case. If we run arr = [1,2,3,100, 5, 9] res = np.argsort(arr) print(res) then we get [0 1 2 4 5 3] which is wrong.
    – Dawn
    Commented Jan 19, 2020 at 12:45
  • I'm unclear what is wrong: arr[res] yields array([ 1, 2, 3, 5, 9, 100]), which seems to be perfectly fine, since that resulting array is in (increasing) order.
    – 9769953
    Commented Jan 19, 2020 at 14:21
  • @0 0 for arr=[1,2,3,100, 5, 9], I expect the output to be inds=[0,1,2,5,3,4], because this is the order in which you'll order the elements (increasingly) - 1 is in the 0s place, 2 in the 1st place, .... , 5 on the 3rd place and 9 on the 4th place. In order to get that output (inds) I need to run argsort twice, like I mentioned.
    – Dawn
    Commented Jan 20, 2020 at 12:51
  • So those indices are a kind of ranking of the array elements (0th place, 1st place, etc). Given the OP's mention to MATLAB's sort, I reckon the OP wants the other functionality, much like np.argsort is normally used (where one can use arr[np.argsort[arr]] to obtain the sorted array, as in the last MATLAB example). Your answer applies to this case / question instead.
    – 9769953
    Commented Jan 20, 2020 at 16:39
3

Most easiest way you can use Numpy Packages for that purpose:

import numpy
s = numpy.array([2, 3, 1, 4, 5])
sort_index = numpy.argsort(s)
print(sort_index)

But If you want that you code should use baisc python code:

s = [2, 3, 1, 4, 5]
li=[]
  
for i in range(len(s)):
      li.append([s[i],i])
li.sort()
sort_index = []
  
for x in li:
      sort_index.append(x[1])
  
print(sort_index)
2

We will create another array of indexes from 0 to n-1 Then zip this to the original array and then sort it on the basis of the original values

ar = [1,2,3,4,5]
new_ar = list(zip(ar,[i for i in range(len(ar))]))
new_ar.sort()

`

2
s = [2, 3, 1, 4, 5]
print([sorted(s, reverse=False).index(val) for val in s]) 

For a list with duplicate elements, it will return the rank without ties, e.g.

s = [2, 2, 1, 4, 5]
print([sorted(s, reverse=False).index(val) for val in s]) 

returns

[1, 1, 0, 3, 4]
2
  • What if s contains duplicates?
    – pho
    Commented Jan 30, 2023 at 17:16
  • The method returns the rank without ties if there are duplicated elements.
    – Lorry
    Commented Jan 30, 2023 at 21:48
1

Import numpy as np

FOR INDEX

S=[11,2,44,55,66,0,10,3,33]

r=np.argsort(S)

[output]=array([5, 1, 7, 6, 0, 8, 2, 3, 4])

argsort Returns the indices of S in sorted order

FOR VALUE

np.sort(S)

[output]=array([ 0,  2,  3, 10, 11, 33, 44, 55, 66])
1

firstly convert your list to this:

myList = [1, 2, 3, 100, 5]

add a index to your list's item

myList = [[0, 1], [1, 2], [2, 3], [3, 100], [4, 5]]

next :

sorted(myList, key=lambda k:k[1])

result:

[[0, 1], [1, 2], [2, 3], [4, 5], [3, 100]]
1

Note that you'll often want to get the sorted values as well as the indices. Here's quick and nice way to do that (which doesn't waste time sorting everything twice):

myList = [1, 2, 3, 100, 5]
indices, values = zip(*sorted(enumerate(myList), key=lambda x: x[1]))
>>> indices
(0, 1, 2, 4, 3)
>>> values
(1, 2, 3, 5, 100)
0
0

Code:

s = [2, 3, 1, 4, 5]
li = []

for i in range(len(s)):
    li.append([s[i], i])
li.sort()
sort_index = []

for x in li:
    sort_index.append(x[1])

print(sort_index)

Try this, It worked for me cheers!

0

A variant on RustyRob's answer (which is already the most performant pure Python solution) that may be superior when the collection you're sorting either:

  1. Isn't a sequence (e.g. it's a set, and there's a legitimate reason to want the indices corresponding to how far an iterator must be advanced to reach the item), or
  2. Is a sequence without O(1) indexing (among Python's included batteries, collections.deque is a notable example of this)

Case #1 is unlikely to be useful, but case #2 is more likely to be meaningful. In either case, you have two choices:

  1. Convert to a list/tuple and use the converted version, or
  2. Use a trick to assign keys based on iteration order

This answer provides the solution to #2. Note that it's not guaranteed to work by the language standard; the language says each key will be computed once, but not the order they will be computed in. On every version of CPython, the reference interpreter, to date, it's precomputed in order from beginning to end, so this works, but be aware it's not guaranteed. In any event, the code is:

sizediterable = ...
sorted_indices = sorted(range(len(sizediterable)), key=lambda _, it=iter(sizediterable): next(it))

All that does is provide a key function that ignores the value it's given (an index) and instead provides the next item from an iterator preconstructed from the original container (cached as a defaulted argument to allow it to function as a one-liner). As a result, for something like a large collections.deque, where using its .__getitem__ involves O(n) work (and therefore computing all the keys would involve O(n²) work), sequential iteration remains O(1), so generating the keys remains just O(n).

If you need something guaranteed to work by the language standard, using built-in types, Roman's solution will have the same algorithmic efficiency as this solution (as neither of them rely on the algorithmic efficiency of indexing the original container).

To be clear, for the suggested use case with collections.deque, the deque would have to be quite large for this to matter; deques have a fairly large constant divisor for indexing, so only truly huge ones would have an issue. Of course, by the same token, the cost of sorting is pretty minimal if the inputs are small/cheap to compare, so if your inputs are large enough that efficient sorting matters, they're large enough for efficient indexing to matter too.

0

a little confused for me.

The question is about "How to get indices of a sorted array in Python", I was understanding that How to get sorted indices of each elements in array.

So give my solution for someone who may need:

a = [1, 2, 3, 100, 5]
b = [m[0] for m in sorted([j for j in enumerate([i[0] for i in sorted(enumerate(a), key=lambda x:x[1])])],key=lambda x:x[1])]
print(b)

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.