How to get indices of a sorted array in Python

PythonIndexingSorted

Python Problem Overview


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.

Python Solutions


Solution 1 - Python

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.

Solution 2 - Python

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.

Solution 3 - Python

myList = [1, 2, 3, 100, 5]    
sorted(range(len(myList)),key=myList.__getitem__)

[0, 1, 2, 4, 3]

Solution 4 - Python

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")

Solution 5 - Python

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))

Solution 6 - Python

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))

Solution 7 - Python

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.

Solution 8 - Python

If you do not want to use numpy,

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

is fastest, as demonstrated here.

Solution 9 - Python

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.

Solution 10 - Python

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)

Solution 11 - Python

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()

`

Solution 12 - Python

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

It works even for a list with duplicate elements.

Solution 13 - Python

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])

Solution 14 - 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)

Try this, It worked for me cheers!

Solution 15 - Python

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]]

Attributions

All content for this solution is sourced from the original question on Stackoverflow.

The content on this page is licensed under the Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) license.

Content TypeOriginal AuthorOriginal Content on Stackoverflow
QuestionGyanView Question on Stackoverflow
Solution 1 - PythonMatthew LewisView Answer on Stackoverflow
Solution 2 - PythonRoman BodnarchukView Answer on Stackoverflow
Solution 3 - Pythonrobert kingView Answer on Stackoverflow
Solution 4 - PythonNico SchlömerView Answer on Stackoverflow
Solution 5 - PythonAnt6nView Answer on Stackoverflow
Solution 6 - PythonMattView Answer on Stackoverflow
Solution 7 - PythonMSeifertView Answer on Stackoverflow
Solution 8 - PythonmabView Answer on Stackoverflow
Solution 9 - Pythonshahar_mView Answer on Stackoverflow
Solution 10 - Pythonuser15349912View Answer on Stackoverflow
Solution 11 - PythonJai dewaniView Answer on Stackoverflow
Solution 12 - PythonLorryView Answer on Stackoverflow
Solution 13 - PythonnegiView Answer on Stackoverflow
Solution 14 - PythonDRVView Answer on Stackoverflow
Solution 15 - PythonJ.ZhaoView Answer on Stackoverflow