sort a list of integers by rank in python

Question

I'm trying to create a function that for each number, it counts how many elements are smaller than it (this is the number’s rank) and then places the number in its rank in the sorted list. 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. I wrote this code:

def sort_by_rank(lst):
    for i in range(len(lst)):
        # rank = how many elements are smaller than lst[i]?
        rank = 0
        for elem in lst:
            if elem < lst[i]:
                rank += 1
        lst[rank] = lst[i]
    return lst

but it has a bug that i don't manage to debug.

Answer 1

The simpler way to do this is make a sorted copy of the list, then get the indexes:

L = [4,7,9,10,6,11,3]
s = sorted(L)
result = [s.index(x) for x in L]  # [1, 3, 4, 5, 2, 6, 0]

Now, this is the naive approach, and it works great for small lists like yours, but for long lists it would be slow since list.index is relatively slow and it's being run over and over.

To make it more efficient, use enumerate to make a dict of element-index pairs. Lookups in a dict are much faster than list.index.

s = {x: i for i, x in enumerate(sorted(set(L)))}
result = [s[x] for x in L]  # [1, 3, 4, 5, 2, 6, 0]

Here I'm also converting L to a set in case of duplicates, otherwise later occurrences would override the indexes of earlier ones.