Find positions of elements in sorted array

Question

Suppose I have some numpy array (all elements are unique) that I want to sort in descending order. I need to find out which positions elements of initial array will take in sorted array.

Example.

In1: [1, 2, 3] # Input

Out1: [2, 1, 0] # Expected output

In2: [1, -2, 2] # Input

Out2: [1, 2, 0] # Expected output

I tried this one:

def find_positions(A):
    A = np.array(A)
    A_sorted = np.sort(A)[::-1]
    return np.argwhere(A[:, None] == A_sorted[None, :])[:, 1]

But it doesn't work when the input array is very large (len > 100000). What I did wrong and how can I resolve it?

Answer 1

Approach #1

We could use double argsort -

np.argsort(a)[::-1].argsort() # a is input array/list

Approach #2

We could use one argsort and then array-assignment -

# https://stackoverflow.com/a/41242285/ @Andras Deak
def argsort_unique(idx):
    n = idx.size
    sidx = np.empty(n,dtype=int)
    sidx[idx] = np.arange(n)
    return sidx

out = argsort_unique(np.argsort(a)[::-1])

Answer 2

Take a look at numpy.argsort(...) function:

Returns the indices that would sort an array.

Perform an indirect sort along the given axis using the algorithm specified by the kind keyword. It returns an array of indices of the same shape as a that index data along the given axis in sorted order.

Here is the reference from the documentation, and the following is a simple example:

import numpy
arr = numpy.random.rand(100000)
indexes = numpy.argsort(arr)

the indexes array will contain all the indexes in the order in which the array arr would be sorted

Answer 3

I face the same problem for plain lists, and would like to avoid using numpy. So I propose a possible solution that should also work for an np.array, and which avoids reversal of the result:

def argsort(A, key=None, reverse=False):
    "Indirect sort of list or array A: return indices of elements in order."
    keyfunc = (lambda i: A[i]) if key is None else lambda i: key(A[i])
    return sorted(range(len(A)), keyfunc, reverse=reverse)

Example of use:

>>> L = [3,1,4,1,5,9,2,6]
>>> argsort( L )
[1, 3, 6, 0, 2, 4, 7, 5]
>>> [L[i]for i in _]
[1, 1, 2, 3, 4, 5, 6, 9]
>>> argsort( L, key=lambda x:(x%2,x) )  # even elements first
[6, 2, 7, 1, 3, 0, 4, 5]
>>> [L[i]for i in _]
[2, 4, 6, 1, 1, 3, 5, 9]
>>> argsort( L, key=lambda x:(x%2,x), reverse = True)
[5, 4, 0, 1, 3, 7, 2, 6]
>>> [L[i]for i in _]
[9, 5, 3, 1, 1, 6, 4, 2]

Feedback would be welcome! (Efficiency compared to previously proposed solutions? Suggestions for improvements?)