Creating a list containing the rank of the elements in the original list

I don't really know how to explain what I'm looking for in a way that makes sense, but here goes:

Say I have a list
$$L=(4,7,9,10,6,11,3)$$
What I want to produce is a corresponding list
$$ K = (1,3,4,5,2,6,0)$$

where element K[i] has the value of the 'rank' of the element for the corresponding location in L. So the higher the number the higher the rank, starting from rank 0 for the smallest number in L

The code I have written for this is:

x = [4,7,9,10,6,11,3]
index = [0]*len(x)

for i in range(len(x)):
    index[x.index(min(x))] = i
    x[x.index(min(x))] = max(x)+1

and it works, but I just feel it looks horrible, and was wondering if there might exist a more aesthetic way.

I believe your solution is \$O(n^2)\$, and we can reduce that to \$O(n \log n)\$. I'm not well-versed in python, but this is the general idea:

• The output is a permutation of the indices \$0, 1, \ldots, n - 1\$, where \$n\$ is the length of the input.

• We sort the indices based on the element at the specified index. In your example, we get \$6, 0, 4, 1, 2, 3, 5\$, i.e. the \$6\$th element (\$3\$) is smallest, so \$6\$ is first.

• Seeing that \$6\$ is at index \$0\$, we know that the \$6\$th element of the output is \$0\$, and so on. This step is easier to explain in code than in words, sorry about that.

In code,

indices = list(range(len(input)))
indices.sort(key=lambda x: input[x])
output = [0] * len(indices)
for i, x in enumerate(indices):
    output[x] = i

Or the more terse

output = [0] * len(input)
for i, x in enumerate(sorted(range(len(input)), key=lambda y: input[y])):
    output[x] = i

I used the timeit module to compare the running times of this version and the original for different input sizes. The functions were each called 1,000 times on randomly shuffled input of size \$n\$. Here are some of the results

n     this version (s)  original version (s)
  10                 0.02                  0.04
 100                 0.17                  1.40
1000                 1.81                133.35

This is asymptotically optimal, since if it were not, we would have a sub-linearithmic comparison sort:

sorted = [0] * len(input)
for i, x in enumerate(output):
    sorted[x] = input[i]

StackExchange Code Review Q#65031, answer score: 11