Kaina: k yra raktų aibė

Skaičiavimo rikiavimas surikiavo 100 000 įrašų per 3 ms be nė vieno palyginimo. Natūralus klausimas: kodėl juo nerikiuojam visko?

Pabandyk pritaikyti jį Title.

k yra raktų aibės dydis

count masyve turi būti po vietą kiekvienai galimai rakto reikšmei.

raktas	k	count masyvas
Rating (0–100)	101	101 vieta
Year (1900–2030)	131	131 vieta
int32	4 294 967 296	4,3 mlrd. vietų — 34 GB
Title, iki 20 simbolių	?	pratybose suskaičiuosi

Trečioji eilutė jau neįmanoma. Ketvirtoji nėra „didelė" — ji beprasmiška, ir pratybose pamatysi, kiek tiksliai.

Esmė paprasta: skaičiavimo rikiavimas nėra greitesnis rikiavimas. Tai rikiavimas kitokiam uždaviniui — tam, kur raktas yra mažas sveikasis skaičius iš žinomo intervalo.

Trys prielaidos, ir visos privalomos

1. Raktas yra sveikasis skaičius arba į jį verčiamas.
2. Intervalas žinomas iš anksto — ne po duomenų peržiūros, o rašant kodą.
3. k yra palyginamas su n. Prie k ≫ n O(n + k) tampa O(k), ir tada tai jau ne greitas rikiavimas, o didelio masyvo alokacija.

Palyginimų rikiavimai neturi nė vienos iš šių sąlygų. Todėl jie visur ir naudojami, o skaičiavimo rikiavimas — tik ten, kur sąlygos išpildytos.

O tavo bibliotekoje

Iš keturių Item laukų skaičiavimo rikiavimui tinka du: Rating ir Year. Title ir Artist — ne, nei šiandien, nei kada nors.

Šitas santykis — du iš keturių — ir yra tikras atsakymas į „kodėl juo nerikiuojam visko".