How to get indices of a sorted array in Python

Question

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

User · Answer

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

User · Answer

myList    1  2  3  100  5      sorted range len myList   key myList   getitem      0  1  2  4  3

User · Answer

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

User · Answer

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 numpy  note the log scale     Code to reproduce the plot  import perfplot import numpy   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      def numpy argsort x       return numpy argsort x    perfplot save       quot argsort png quot       setup lambda n  numpy random rand n       kernels  sorted enumerate  sorted enumerate key  sorted range  numpy argsort       n range  2    k for k in range 15        xlabel  quot len x  quot

User · Answer

If you are using numpy  you have the argsort   function available    gt  gt  gt  import numpy  gt  gt  gt  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

User · Answer

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

User · Answer

If you do not want to use numpy    sorted range len seq    key seq   getitem      is fastest  as demonstrated here

User · Answer

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

User · Answer

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

User · Answer

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    gt  gt  gt  arr   np array  1  2  3  100  5     gt  gt  gt  np argsort np argsort arr   array  0  1  2  4  3   dtype int64    gt  gt  gt  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   gt  gt  gt  arr   np array  3  1  2  4    gt  gt  gt  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    gt  gt  gt  arr   np array  3  1  2  4    gt  gt  gt  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

User · Answer

Something like next    gt  gt  gt  myList    1  2  3  100  5   gt  gt  gt   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

User · Answer

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

[python] How to get indices of a sorted array in Python

Examples related to python

Examples related to indexing

Examples related to sorted