1

I am trying to sort the list of items below by the frequency of the individual items. With the largest first, to the smallest last. I wanted to see if I can do it first with sorted() before trying with collection.Counter.

Code I have so far is;

items = [4, 6, 2, 2, 6, 4, 4, 4]
x = sorted(items, key=items.count, reverse=True)
print(x)

The above code prints; [4, 4, 4, 4, 6, 2, 2, 6] Rather than; [4, 4, 4, 4, 6, 6, 2, 2]

Could someone please explain why it doesn't go "6,6,2,2"?

Improve this question
6
  • 10
    6 and 2 both occur twice, so the sort value for all 6 and 2 is "2", meaning they're all equal as far as the sorting algorithm is concerned and their relative order is undefined and/or won't change. Commented Aug 5, 2020 at 10:45
  • 1
    Isn't this doing a stable sorting? Commented Aug 5, 2020 at 10:46
  • 1
    This is because Python's sort is stable Commented Aug 5, 2020 at 10:47
  • 1
    This seems to be the duplicate of stackoverflow.com/questions/2290962/… Commented Aug 5, 2020 at 10:50
  • 2
    @deceze has answered the question but jfyi you could achieve what you want by doing this: x = sorted(sorted(items, reverse=True), key=items.count, reverse=True), i.e. pre-sort to "group" same numbers. Commented Aug 5, 2020 at 10:51

2 Answers 2

Reset to default
4

The reason it does this is best explained by the documentation for the function:

The built-in sorted() function is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade).

https://docs.python.org/3/library/functions.html#sorted

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

I would slightly modify the key parameter:

result = sorted(items, key=lambda x: (items.count(x), x), reverse=True)

By the way, you should really use Counter as it would be much much faster! The complexity of your approach is O(n^2log(n))! Instead, it could be the usual O(nlog(n))...

Improve this answer

7 Comments

The OP is already aware of Counter. He's interested in knowing why his other approach is not working as expected.
Haha, I was literally in the middle of posting almost the exact same answer. Beat me to it, good job!
I didn't downvote you, but you didn't address the question: Could someone please explain why it doesn't go "6,6,2,2"? Might be why.
@mobiusxs Thanks! You answer is indeed great and it perfectly address the problem. Also, it should be the accepted answer. Hope my answer just provide some more interesting details to yours.
@Undead2k Sorting algorithms work using comparisons (like x < y). In your case, comparing two counts is not enough. What's the element that comes first when they share the same frequency? Thats why I compare tuples instead of single numbers. When you compare tuples your first compare the first element, and if its the same then you compare the second one etc. For example: (3,2) < (4,2) (because of the first element), (3,2) < (3,7) (because of the second element. To sum up, the second element is needed to disambiguate the cases in which the first element is the same.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.