CODEWITHSUNDEEP
python
Rona
Rona

Reputation: 41

sort a list of integers by rank in python

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.

Upvotes: 4

Views: 1311

Answers (3)

Michael Hsi
Michael Hsi

Reputation: 439

First of all, your L and K are not lists, they are tuples. Your code probably bugged because you're trying to modify values within a tuple.

You can use map function to map each element to the amount of numbers smaller than it. 

result = list(map(lambda item: sum([number < item for number in L]), L))

know that when calculating sum of True and False, True is same as 1 and False is same as 0. By calculating the sum of the new list, where each element is True/False depending on if item is larger than number, we are essentially counting how many True is in the list, which should be what you're asking.

My apology, did not saw the part you need you number sorted by the rank. You can use the key argument to sort it 

L = [(item, sum([number < item for number in L])) for item in L]
L.sort(key=lambda item: item[1])

where each element in L is converted to tuple of (original_value, its_rank)

Upvotes: 0

wjandrea
wjandrea

Reputation: 32997

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.

Upvotes: 3

blhsing
blhsing

Reputation: 106618

For a more efficient approach, you can use enumerate to create indices for the items for sorting together, and then use another enumerate create indices for the sorted sequence to map the old indices to the sorted indices as a dict, and then iterate an index through the range of the list to output the new indices in a list comprehension:

L=(4,7,9,10,6,11,3)
d = {o: i for i, (o, _) in enumerate(sorted(enumerate(L), key=lambda t: t[1]))}
print([d[i] for i in range(len(L))])

This outputs:

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

Upvotes: 0

Related Questions