Sortiranje prebrojavanjem (Counting Sort)

Lekcija 5 od 5 · Sortiranje

Kada su vrednosti elemenata mali celi brojevi (na primer ocene 1–5 ili brojevi od 0 do milion), niz može da se sortira bez ijednog poređenja: prebrojimo koliko puta se javlja svaka vrednost i ispišemo ih redom. To radi u vremenu O(n + K), gde je K najveća vrednost.

Pre nego što počneš: potrebno predznanje – jednostavni algoritmi sortiranja.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Ideja

Za niz 3 1 4 1 0 3 3 sa vrednostima od 0 do 4 pravimo niz brojača br, gde je br[v] broj pojavljivanja vrednosti v:

v	0	1	2	3	4
br[v]	1	2	0	3	1

Sortiran niz dobijamo kada ispišemo vrednost 0 jednom, 1 dva puta, 2 nijednom, 3 tri puta i 4 jednom: 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;              // najveća moguća vrednost
    int n;
    cin >> n;
    vector<int> br(K + 1, 0);           // br[v] = koliko puta se javlja v
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        br[x]++;
    }
    for (int v = 0; v <= K; v++)        // ispisujemo vrednosti redom
        for (int k = 0; k < br[v]; k++)
            cout << v << " ";
    cout << "\n";
    return 0;
}

Kada se isplati?

Algoritam prolazi jednom kroz niz (n koraka) i jednom kroz sve moguće vrednosti (K koraka). Isplati se kada K nije mnogo veće od n, a ne može se koristiti za realne brojeve ni za vrednosti do 10⁹ (niz brojača bi bio prevelik).

Situacija	Prebrojavanje?
10⁶ ocena od 1 do 5	da – idealno
10⁵ brojeva od 0 do 10⁶	da
1000 brojeva do 10⁹	ne – koristi `sort`
negativni brojevi od −1000 do 1000	da, uz pomeraj: `br[x + 1000]++`

Isti niz brojača često je i cilj zadatka: najčešća vrednost, broj različitih vrednosti, da li se neka vrednost ponavlja – sve se čita iz br.

Stabilna verzija: sortiranje zapisa po ključu

Kada sortiramo cele zapise (na primer učenike po oceni), ne smemo samo da ispišemo ocene. Tada iz brojača računamo početnu poziciju svake vrednosti (prefiksni zbirovi – vidi prefiksne sume) i zapise prepisujemo redom na njihova mesta. Redosled učenika sa istom ocenom ostaje isti – sortiranje je stabilno.

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

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

    vector<int> poc(7, 0);                    // ocene 1..5
    for (int i = 0; i < n; i++) poc[ocena[i] + 1]++;
    for (int v = 1; v <= 6; v++) poc[v] += poc[v - 1];   // poc[v] = prva pozicija za ocenu v

    vector<string> rez(n);
    for (int i = 0; i < n; i++) rez[poc[ocena[i]]++] = ime[i];
    for (auto &s : rez) cout << s << " ";
    cout << endl;
    return 0;
}

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Lako

Najčešća ocena

Dato je n ocena od 1 do 5 (1 ≤ n ≤ 10⁶). Ispiši ocenu koja se javlja najviše puta; ako ih ima više, najmanju od njih.

Primer

Ulaz

8
4 5 3 4 5 4 2 5

Izlaz

Rešenje (C++)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, br[6] = {0};
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        br[x]++;
    }
    int naj = 1;
    for (int v = 2; v <= 5; v++)
        if (br[v] > br[naj]) naj = v;     // strogo veće: kod jednakih ostaje manja ocena
    cout << naj << endl;
    return 0;
}

ZADATAK 02Težina: Lako

Prvi broj koji se ponavlja

Dato je n brojeva od 1 do 10⁶. Ispiši prvi broj (gledano sleva) čije se pojavljivanje već desilo ranije u nizu, ili NEMA.

Primer 1

Ulaz

6
7 3 9 3 7 1

Izlaz

Primer 2

Ulaz

3
1 2 3

Izlaz

NEMA

Rešenje (C++)

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

int main() {
    int n;
    cin >> n;
    vector<bool> videno(1000001, false);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (videno[x]) {
            cout << x << endl;
            return 0;
        }
        videno[x] = true;
    }
    cout << "NEMA" << endl;
    return 0;
}

Česte greške i saveti

Niz brojača mora da ima K + 1 elemenata (indeksi od 0 do K).
Veliki niz brojača pravi se kao vector ili globalni niz, ne kao lokalni niz u main (stek je mali).
Za negativne vrednosti koristi pomeraj (br[x + M]).

Proveri znanje

Otvori kviz