Custom order by frequency in Python

Why this matters

Most sorting examples order values by the value itself. Numbers go from small to large, words go from A to Z. Real programs often need a different rule. A shop may want to list products by how many people bought them. A log viewer may want to show the error codes that happened most often first. A text tool may want to list letters by how common they are in a document.

This lesson teaches one such rule: sort by frequency, where frequency means how many times a value appears in the list. The rule has a catch. Many values can have the same frequency, so the rule needs a second step that decides their order. That second step is called a tie-break.

The sorts in this module compare two items and decide which one comes first. The idea here is the same. The only change is that the key looks at a count first, and at the value second. The multi-key sorting lesson covers sorts on two real fields. Here the second key is always the value itself, and the first key is a count that the program builds.

Words used in this lesson

A frequency is the number of times a value appears in a list. In the list [4, 6, 2, 2, 6, 4, 4, 4], the value 4 has frequency 4, and the value 2 has frequency 2.

A key function is a small function that gives each item the value to sort by. Python's sorted() calls it on each item, and sorts the items by the values it returns.

A tie happens when two items get the same answer on the first question. In this lesson, two values tie when they have the same frequency.

A tie-break is the second question the key asks when the first answer is a tie. Here the tie-break compares the values.

A dictionary is a table that stores pairs of a key and a value. You give it a key and it gives back the value stored with that key. In this lesson the key is a value from the list, and the stored value is its count.

A Counter is a dictionary from the collections module that counts things for you. Counter([4, 6, 2]) gives a table with each value as a key and its count as the value.

A stable sort keeps items that compare as equal in the same order they had before the sort. Python's sorted() is stable. You will need this idea in the mistakes section.

The idea with one example

Take this list.

4, 6, 2, 2, 6, 4, 4, 4

Count the values. The value 4 appears four times. The value 6 appears two times. The value 2 appears two times.

Now sort the list from the least frequent value to the most frequent value. The value 2 and the value 6 both appear two times, so they tie. The tie-break says to put the smaller value first, so 2 goes before 6. The value 4 appears four times, so it goes last.

The result is:

2, 2, 6, 6, 4, 4, 4, 4

Notice that the output keeps every copy. The input has eight numbers, and the output has eight numbers. The sort does not remove duplicates. It only moves them. That is the reason we sort the full list and not a list of unique values.

The whole method has two steps.

1. Count how many times each value appears. Store the counts in a Counter.
2. Sort the list with a key. The key looks up each value's count. If two counts differ, the key uses them. If the counts are equal, the key uses the values themselves.

Step 1: count with a Counter

The first step is to build the counts. A Counter does this in one line.

from collections import Counter
 
counts = Counter([4, 6, 2, 2, 6, 4, 4, 4])
print(counts[4], counts[6], counts[2])

The output is:

4 2 2

Reading a key that is not in the Counter gives 0 instead of an error, which is handy when you look up counts for values you have not seen. A plain dictionary would raise a KeyError in that case.

If you want to see how the counting works, here is the same count written with a loop and a plain dictionary. The get method returns a default when the key is missing, so the first time a value appears, its count starts at 0.

counts = {}
for v in [4, 6, 2, 2, 6, 4, 4, 4]:
    counts[v] = counts.get(v, 0) + 1

Here is a hand trace of that loop on [4, 6, 2, 2, 6, 4, 4, 4]. Each row shows the dictionary after one value is processed.

The table ends with the count for each value. The order of entries in a dictionary is the order they were first added, and the key function looks up counts by key, so that order does not affect the result.

Step 2: sort with a key

Now the list must be sorted. Here is the full function for ascending order, which means least frequent first.

from collections import Counter
 
def sort_ascending(values):
    counts = Counter(values)
    return sorted(values, key=lambda v: (counts[v], v))

The lambda v: part is a one-line function. It takes a value and returns its key, the tuple (counts[v], v), which is a pair of values in parentheses. Python compares two tuples one item at a time, from the left. The first item is the count, so the sort puts the less frequent values first. When two counts are equal, Python moves to the second item, the value itself, and the smaller value comes first.

The function sorted returns a new list, so the input list is not changed. Every copy of each value stays in the output, because the function sorts values, not the keys of the counter.

Here is a small program that runs the function on the example.

The output from running it is:

input:      [4, 6, 2, 2, 6, 4, 4, 4]
ascending:  [2, 2, 6, 6, 4, 4, 4, 4]

The result matches the hand answer.

Example 2: most frequent first

Sometimes the most common values should come first. A top-ten list is a common case. To do this, put a minus sign on the count. A bigger count gives a more negative number, so it sorts first. The value tie-break stays in ascending order.

The output is:

descending: [4, 4, 4, 4, 2, 2, 6, 6]

The value 4 has the highest count, so it comes first. The values 2 and 6 tie with a count of 2. The tie-break puts 2 before 6, because the value is not negated.

The minus sign is applied only to the count, inside the tuple. That is why the value tie-break keeps its direction. The mistakes section shows what happens when the whole sort is reversed instead.

Example 3: words and letters

The same function works for any values that can be counted. Here is a list of words. The word "cat" appears three times, "dog" twice, and "bird" once.

The output is:

words:           ['cat', 'dog', 'cat', 'bird', 'dog', 'cat']
words ascending: ['bird', 'dog', 'dog', 'cat', 'cat', 'cat']

The word "bird" has count 1, so it comes first. The words "dog" and "cat" have counts 2 and 3. The function puts "dog" before "cat" because its count is smaller.

Words are compared as text, so the tie-break does not need any special form. A string compares alphabetically in Python, so w as the second item of the key is enough.

A harder version of the same idea sorts the letters of a text. The next program counts the letters in a string and then sorts the letters from most frequent to least frequent. Ties go in alphabetical order. This is the same problem that is sometimes asked in coding interviews under the name "frequency sort."

The output is:

eert
aaannb
iiiissssppm

Check the last line by hand. The letters in "mississippi" are i (4 times), s (4 times), p (2 times) and m (1 time). Highest count first gives the i and s groups first. The tie between i and s is broken by the letter itself, and "i" comes before "s" in the alphabet, so the four i letters come first. Then the four s letters, then the two p letters, then the single m.

The function "".join(...) joins a list of single letters into one string. The sorted call works on the string itself, because a string can be looped over one character at a time.

Why the tie-break is needed

Without a tie-break, the result depends on the input order. Look at this version, which only uses counts.

The output is:

count only: [6, 2, 2, 6, 4, 4, 4, 4]

The count rule is correct. The two 6s and the two 2s both have count 2, so they are in the right block. But inside that block the values are not in order. The 6 comes first because it appeared first in the input.

Python's sorted is stable. Stable means that items which compare as equal keep the order they had in the input. In this case, the first 6 and the first 2 both have count 2, so they tie, and the sort leaves them where they were. The result is stable, but the values inside each group are not sorted. If the output must always look the same for the same set of numbers, you must add the tie-break.

Common mistakes

Mistake 1: putting the minus sign on the wrong part

A beginner who wants most frequent first may set reverse=True on the whole key. The counts come out right, but the ties come out backwards. The next program shows that mistake next to the fix.

The output is:

reverse=True on the whole key: [4, 4, 4, 4, 6, 6, 2, 2]
minus sign on the count only: [4, 4, 4, 4, 2, 2, 6, 6]

The first line is the mistake. reverse=True flips both parts of the key, so the value tie-break runs from large to small: 6 comes before 2. The second line is the fix. The minus sign changes only the count, and the value tie-break stays in ascending order. Check which part of the key each direction applies to before you run the sort.

Mistake 2: using a minus sign on text

A minus sign works only on numbers. If you try to sort words most frequent first with a minus sign on the word itself, Python refuses:

The output is:

Traceback (most recent call last):
  File "/path/to/words.py", line 5, in <module>
    print(sorted(words, key=lambda w: (-counts[w], -w)))
          ~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/path/to/words.py", line 5, in <lambda>
    print(sorted(words, key=lambda w: (-counts[w], -w)))
                                                   ^^
TypeError: bad operand type for unary -: 'str'

The last line says the minus sign has no meaning for a string. For a reversed text tie-break, sort twice: first by the word in reverse order, then by the count in reverse order with reverse=True. Because Python's sort is stable, the second sort keeps the text order inside each count.

Mistake 3: comparing counts with is

This mistake is easy to make in a hand-written comparison. Suppose you wrote a tie check like this:

if counts[a] is counts[b]:
    ...

The is operator checks whether two names point to the same object, not whether the numbers are equal. Python keeps one shared object for small integers, from -5 to 256. For those numbers, two equal counts are often the same object, so is looks correct. For bigger numbers it is wrong.

This program counts two values that each appear 200 times, and then 300 times:

The output is:

200 counts: a is b: True a == b: True
300 counts: a is b: False a == b: True

Both counts are the same number in both cases. The is answer changes with the size of the number, which is why it is unsafe for comparing values. Use == to compare counts. A key function such as (counts[v], v) uses the numbers themselves, so it does not have this problem.

Mistake 4: sorting the keys instead of the list

Some people build a counter, and then sort the keys of the counter. A key appears only once in a dictionary. The result has one entry per distinct value, so the duplicates disappear. For the example [4, 6, 2, 2, 6, 4, 4, 4] you would get three numbers, not eight. The list you sort must contain every copy of each value. The counter is only used to look up counts.

Mistake 5: subtracting counts in the key

A key can be written with a subtraction in a comparison function, such as counts[a] - counts[b]. In Python this does not overflow, because integers have no size limit. The same expression in Java could give a wrong sign for large numbers. A key tuple avoids the question altogether, because the sort compares the numbers directly and never subtracts them.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

Exercise 1

Sort this list ascending by frequency, with ties broken by value from small to large.

3, 1, 3, 2, 1, 3

Show the answer

The answer is [2, 1, 1, 3, 3, 3]. The value 2 appears once, so it comes first. The values 1 and 3 appear twice and three times. The value 1 appears twice, so the two 1s come before the three 3s.

Exercise 2

Sort this list of words descending by how often each word appears. Break ties in alphabetical order.

pear, fig, pear, apple, fig, pear

Show the answer

The answer is ['pear', 'pear', 'pear', 'fig', 'fig', 'apple']. The word "pear" appears three times, "fig" appears twice, and "apple" appears once. The count goes first with a minus sign, and the word tie-break stays in alphabetical order.

Exercise 3

Count the letters in the word hello and list them from least frequent to most frequent. Break ties by the letter itself, from A to Z. Write the answer as one string.

Show the answer

The answer is eholl. The letters e, h and o each appear once. Sorted by letter, they are e, h, o. The letter l appears twice, so it comes last, and the two l letters are written together.

Exercise 4

The following code is meant to sort the list [4, 6, 2, 2, 6, 4, 4, 4] by frequency, most frequent first, with ties in ascending value order. It does not do that. Find the mistake and say what the output is.

sorted(example, key=lambda v: (counts[v], v), reverse=True)

Show the answer

The mistake is reverse=True. It flips both parts of the key, so the value tie-break runs from large to small as well as the count. The output is [4, 4, 4, 4, 6, 6, 2, 2]. The fix is to put a minus sign on the count and remove reverse=True: sorted(example, key=lambda v: (-counts[v], v)).

Exercise 5

Write the key that sorts a list by count, most frequent first, and breaks ties by value from largest to smallest.

Show the answer

sorted(example, key=lambda v: (-counts[v], -v))

The count is negated first, so the bigger count comes first. Then the value is negated, so larger values come first in a tie. For the input [4, 6, 2, 2, 6, 4, 4, 4] the output is [4, 4, 4, 4, 6, 6, 2, 2]. This works because the values are numbers, so a minus sign is allowed.

Summary

• To sort by frequency, first count each value with a Counter, then sort the full list with a key that looks up each count.
• Use a tuple key. The count is the first item and the value is the second, so the value breaks ties.
• Put a minus sign on a count to sort it from most to least. A minus sign works only on numbers.
• reverse=True flips every part of the key, so it also flips the tie-break.
• Compare counts with ==, not is. Python's is gives different answers for small and large numbers.
• Sort the full list, not the keys of the counter, so that every copy of each value stays in the output.