CODEWITHSUNDEEP
pythonpython-3.xsorting
TechMatt
TechMatt

Reputation: 93

How to sort iterable with Python without using stable sort?

So, I have an iterable in Input like this:

[4, 6, 2, 2, 6, 4, 4, 4]

And I want to sort it based on decreased frequency order. So that the result will be this:

[4, 4, 4, 4, 6, 6, 2, 2]

So what happened here is that, when an element has the same frequency of another one, they will be in the same order (6 appeared first so the 6 goes before the 2).

I tried to implement this mechanism using the sorted function but I have a big problem.

def frequency_sort(items):
    
    return sorted(items, key=lambda elem: sum([True for i in items if i == elem]), reverse=True)

I know this short way is difficult to read but it just sort the array using the key parameter to extract the frequency of a number. But, the output is this:

[4, 4, 4, 4, 6, 2, 2, 6]

As you can see the output is a little different from what it should be. And that happened (I think) because sorted() is a function that does a "stable sort" i.e. a sort that will keep the order as it is if there are same keys.

So what is happening here is like a strong stable sort. I want more like a soft-sort that will take into account the order but will put the same elements next to each other.

Upvotes: 1

Views: 100

Answers (1)

Dani Mesejo
Dani Mesejo

Reputation: 61910

You could use collections.Counter and use most_common that returns in descending order of frequency:

from collections import Counter


def frequency_sorted(lst):
    counts = Counter(lst)
    return [k for k, v in counts.most_common() for _ in range(v)]


result = frequency_sorted([4, 6, 2, 2, 6, 4, 4, 4])
print(result)

Output

[4, 4, 4, 4, 6, 6, 2, 2]

From the documentation on most_common:

Return a list of the n most common elements and their counts from the most common to the least. If n is omitted or None, most_common() returns all elements in the counter. Elements with equal counts are ordered in the order first encountered

Upvotes: 5

Related Questions