Grade 9 · Sorting and searchingCitește în română

Counting sort

Original: Sortarea prin numărare

O(n)C++1742 lines1 example

The idea

When the values are small natural numbers (here 0..10000), we do not compare elements: we count how many times each value appears in a frequency array, then go through the possible values in increasing order and print each value as many times as it appeared.

Original description (Romanian)

Când valorile sunt numere naturale mici (aici 0..10000), nu comparăm elemente: numărăm de câte ori apare fiecare valoare într-un vector de frecvență, apoi parcurgem valorile posibile în ordine crescătoare și afișăm fiecare valoare de câte ori a apărut.

Complexity
O(n + V), where V is the largest possible value
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

8
7 3 0 7 10 3 3 1

Expected output

0 1 3 3 3 7 7 10

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

sortare-prin-numarare.cpp
/*
 * Titlu: Sortarea prin numărare
 * Clasa: 9
 * Capitol: Sortare și căutare
 * Descriere: Când valorile sunt numere naturale mici (aici 0..10000), nu
 *            comparăm elemente: numărăm de câte ori apare fiecare valoare într-un
 *            vector de frecvență, apoi parcurgem valorile posibile în ordine
 *            crescătoare și afișăm fiecare valoare de câte ori a apărut.
 * Complexitate: O(n + V), unde V este valoarea maximă posibilă
 *
 * Exemplu
 * Intrare:
 * 8
 * 7 3 0 7 10 3 3 1
 * Ieșire: 0 1 3 3 3 7 7 10
 */
#include <iostream>
using namespace std;

const int VMAX = 10000;
int frecv[VMAX + 1];

int main()
{
    int n, x;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        frecv[x]++;
    }
    for (int val = 0; val <= VMAX; val++)
    {
        for (int k = 1; k <= frecv[val]; k++)
        {
            cout << val << ' ';
        }
    }
    cout << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.