🎓 A1Learner
🔍

DSA Counting Sort

Counting sort is a sorting method that counts how often each value appears. It places values by their counts instead of comparing values.

Building the count table

A count table holds one cell for every value that can appear. The cell for a value stores how many times that value appears.

scores = [7, 3, 7, 9, 3, 7]
counts = [0] * 10
for score in scores:
    counts[score] += 1
print(counts)

Rebuilding from the counts

Rebuilding walks the table in order and writes each value its counted number of times. The rebuilt list comes out sorted because the table is in value order.

counts = [0, 0, 0, 2, 0, 0, 0, 3, 0, 1]
result = []
for value in range(len(counts)):
    for _ in range(counts[value]):
        result.append(value)
print(result)

A wide range wastes cells

The table size follows the largest value, not the number of scores. One large score forces many empty cells into the table.

scores = [5, 100, 5]
counts = [0] * (max(scores) + 1)
for score in scores:
    counts[score] += 1
print("cells:", len(counts))
print("values stored:", sum(counts))

Example

scores = [8, 5, 9, 5, 10, 7, 8, 5, 9, 6, 8, 7]
counts = [0] * 11
for score in scores:
    counts[score] += 1
print("scores:", scores)
print("counts:", counts)
result = []
for value in range(len(counts)):
    for _ in range(counts[value]):
        result.append(value)
print("sorted:", result)
print("total counted:", sum(counts))

Key points

  • Counting sort sorts by counting values, not by comparing them.
  • The range of the data is the span from its smallest value to its largest value.
  • The count table needs one cell for every value in the range.
  • Counting sort is a poor fit when the range is far larger than the data.

In this example, twelve exam scores between 0 and 10 are sorted without a single comparison. The first loop counts how often each score appears in a table of eleven cells. The printed table shows three scores of 5, two of 7, and the rest in their cells. The rebuild then writes each score as many times as its cell says. The total counted matches the twelve scores, so nothing was lost.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A count table is [2, 0, 1] for the values 0, 1 and 2. What sorted list does rebuilding produce?