How to Get Indices of a Sorted Array in Python

How to get indices of sorted array in descending order

You can combine enumerate() with custom key= parameter in sorted():

maxList = [7, 3, 6, 9, 1, 3]

print([i[0] for i in sorted(enumerate(maxList), key=lambda k: k[1], reverse=True)])

Prints:

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

numpy: find index in sorted array (in an efficient way)

You just need to invert the permutation that sorts the array. As shown in the linked question, you can do that like this:

import numpy as np

def sorted_position(array):
    a = np.argsort(array)
    a[a.copy()] = np.arange(len(a))
    return a

print(sorted_position([0.1, 0.2, 0.0, 0.5, 0.8, 0.4, 0.7, 0.3, 0.9, 0.6]))
# [1 2 0 5 8 4 7 3 9 6]

how to return index of a sorted list?

You can use the python sorting functions' key parameter to sort the index array instead.

>>> s = [2, 3, 1, 4, 5, 3]
>>> sorted(range(len(s)), key=lambda k: s[k])
[2, 0, 1, 5, 3, 4]
>>> 

Finding the Index of sorted elements in Python Array

You can simply use your technique twice to get the indices in the sorted list:

A=[4, 1, 0, 8, 5, 2]
B=sorted(range(len(A)),key=lambda x:A[x],reverse=True)
C=sorted(range(len(A)),key=lambda x:B[x])
print C

prints

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

Explanation

The idea is that the first iteration produces a list:

B = [3, 4, 0, 5, 1, 2]

giving the locations in the original list of the sorted sequence.

In other words, A[3]=8 is the largest element in the original list, A[4]=5 is the next largest, etc.

The second stage then sorts these indices in B back into the order 0,1,2,3,4,5 and produces C which contains the index in the list B.

It may help to think of B as sorting the list into descending order, and C as reversing the sort back into the original unsorted order, while keeping track of the indices in the sorted list.

Numpy get index of insertion in a sorted array

You are looking for np.searchsorted:

indices = np.searchsorted(y_array, x_array)

The only difference is that this returns the size of the array if you exceed the maximum element:

>>> indices
array([0, 1, 0, 3, 5], dtype=int64)

If you need to get -1 instead, you can use np.where or direct masking:

indices = np.where(indices < y_array.size, indices, -1)

OR

indices[indices >= y_array.size] = -1

Find the indices where a sorted list of integer changes

When it comes to asymptotic complexity I think you can improve slightly on the binary search on average when you apply a more evenly spread divide-and-conquer approach: try to first pinpoint the value-change that occurs closer to the middle of the input list, thereby splitting the range in approximately two halves, which would reduce the next binary search operation path by about one.

Yet, because this is Python, the gain might not be noticeable, because of the Python-code overhead (like for yield, yield from, the recursion, ...). It might even perform worse for the list sizes you work with:

from bisect import bisect_left

def locate(data, start, end):
    if start >= end or data[start] == data[end - 1]:
        return
    mid = (start + end) // 2
    val = data[mid] 
    if val == data[start]:
        start = mid
        val += 1
    i = bisect_left(data, val, start + 1, end)
    yield from locate(data, start, i)
    yield i
    yield from locate(data, i, end)

data = [1] * 3 + [4] * 5 + [5] * 2 + [9] * 3
print(*locate(data, 0, len(data)))  # 3 8 10

Note that this only outputs valid indices, so 13 is not included for this example input.

Getting indices of ascending order of list

The argsort() is basically converting your list to a sorted list of indices.

l = [4, 2, 1, 3]

First it gets index of each element in the list so new list becomes:

indexed=[0, 1, 2, 3]

Then it sorts the indexed list according to the items in the original list. As 4:0 , 2:1 , 1:2 and 3:3 where : means "corresponds to".

Sorting the original list we get

l=[1, 2, 3, 4]

And placing values of each corresponding index of old list

new=[2,1,3,0]

So basically it sorts the indices of a list according to the original list.

---

Related Topics