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.
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(
"argsort.png",
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="len(x)",
)
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!
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 operator
module`:
from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))
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.
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.
myList = [1, 2, 3, 100, 5]
sorted(range(len(myList)),key=myList.__getitem__)
[0, 1, 2, 4, 3]
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.
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()
`
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))
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
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)
argsort
implementationIf 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__)
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.
1
and it is at index 1
in the original so the first element of the result is 1
. 2
is at index 2
in the original so the second element of the result is 2
. 3
is at index 0
in the original so the third element of the result is 0
. 4
and it is at index 3
in the original so the last element of the result is 3
.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 :
3
, which is the third largest value so it would have index 2
in the sorted array/list so the first element is 2
.1
, which is the smallest value so it would have index 0
in the sorted array/list so the second element is 0
.2
, which is the second-smallest value so it would have index 1
in the sorted array/list so the third element is 1
.4
which is the largest value so it would have index 3
in the sorted array/list so the last element is 3
.If you do not want to use numpy,
sorted(range(len(seq)), key=seq.__getitem__)
is fastest, as demonstrated here.
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])
Source: Stackoverflow.com