Counting Sort

Lesson 5 of 5 · Sorting

When the values of the elements are small integers (for example grades 1–5 or numbers from 0 to a million), an array can be sorted without a single comparison: we count how many times each value appears and print them in order. This runs in time O(n + K), where K is the largest value.

Before you start: prerequisites – simple sorting algorithms.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea

For the array 3 1 4 1 0 3 3 with values from 0 to 4 we make an array of counters cnt, where cnt[v] is the number of occurrences of the value v:

v01234
cnt[v]12031

We get the sorted array when we print the value 0 once, 1 twice, 2 not at all, 3 three times and 4 once: 0 1 1 3 3 3 4.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int K = 1000000;              // the largest possible value
    int n;
    cin >> n;
    vector<int> cnt(K + 1, 0);          // cnt[v] = how many times v appears
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    for (int v = 0; v <= K; v++)        // we print the values in order
        for (int k = 0; k < cnt[v]; k++)
            cout << v << " ";
    cout << "\n";
    return 0;
}

When is it worth it?

The algorithm goes once through the array (n steps) and once through all the possible values (K steps). It is worth it when K is not much larger than n, and it cannot be used for real numbers or for values up to 109 (the array of counters would be too large).

SituationCounting?
106 grades from 1 to 5yes – ideal
105 numbers from 0 to 106yes
1000 numbers up to 109no – use sort
negative numbers from −1000 to 1000yes, with an offset: cnt[x + 1000]++

The same array of counters is often the goal of the task: the most frequent value, the number of different values, whether some value repeats – everything is read from cnt.

A stable version: sorting records by a key

When we sort whole records (for example students by grade), we must not just print the grades. Then from the counters we calculate the starting position of every value (prefix sums – see prefix sums) and copy the records in order to their places. The order of the students with the same grade stays the same – the sort is stable.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> name(n);
    vector<int> grade(n);
    for (int i = 0; i < n; i++) cin >> name[i] >> grade[i];

    vector<int> start(7, 0);                  // grades 1..5
    for (int i = 0; i < n; i++) start[grade[i] + 1]++;
    for (int v = 1; v <= 6; v++) start[v] += start[v - 1];   // start[v] = the first position for the grade v

    vector<string> result(n);
    for (int i = 0; i < n; i++) result[start[grade[i]]++] = name[i];
    for (auto &s : result) cout << s << " ";
    cout << endl;
    return 0;
}

Example

Input

5
Anna 4
Mark 5
John 3
Mia 4
Peter 3

Output

John Peter Anna Mia Mark

John comes before Peter and Anna before Mia, just as in the input – that is what stability means.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: easy

The most frequent grade

n grades from 1 to 5 are given (1 ≤ n ≤ 106). Print the grade that appears the most times; if there are several, the smallest of them.

Example

Input

8
4 5 3 4 5 4 2 5

Output

4
TASK 02Difficulty: easy

The first number that repeats

n numbers from 1 to 106 are given. Print the first number (looking from the left) that has already appeared earlier in the array, or NONE.

Example 1

Input

6
7 3 9 3 7 1

Output

3

Example 2

Input

3
1 2 3

Output

NONE
Common mistakes and tips
  • The array of counters must have K + 1 elements (indexes from 0 to K).
  • A large array of counters is made as a vector or a global array, not as a local array in main (the stack is small).
  • For negative values use an offset (cnt[x + M]).

Check your knowledge

Open the quiz

Counting sort

1. What is the complexity of counting sort for n elements with values from 0 to K?




2. For which input is counting sort NOT suitable?




3. How many comparisons of two elements does this algorithm make?