5
Doslej opisani postopki za urejanje so delovali za poljubne podatke (samo da se jih je dalo primerjati z <). Za nekatere posebne primere pa se da sestaviti posebne, učinkovitejše postopke. Recimo, da imamo tabelo a, v kateri so vsi elementi majhna naravna števila. Potem jo lahko uredimo takole: najprej poiščimo največjo vrednost v tabeli a, recimo ji k; nato si pripravimo pomožno tabelo, dolgo k + 1 elementov (recimo tej tabeli b), in za vsako število od 0 do k preštejmo, kolikokrat se pojavlja v tabeli a. Zdaj torej za vsako vrednost x od 0 do k vemo, da se v tabeli a pojavi b[x]-krat. Urejena tabela a bo torej takšne oblike: najprej b[0] ničel, nato b[1] enic, nato b[2] dvojk in tako naprej. To moramo torej le še vpisati v tabelo a, pa imamo urejeno tabelo. Temu postopku pravimo urejanje s štetjem.
(a) Zapiši ta postopek kot funkcijo v nekem konkretnem programskem jeziku. Pri tem pazi na to, da naj tvoj postopek določi število pojavitev za vse vrednosti od 0 do k z enim samim prehodom čez tabelo a, ne s (k + 1) prehodi ali čim podobnim. Tako bo časovna zahtevnost postopka O(n + k), ne pa na primer O(n · k).
(b) Preizkusi dobljeni postopek na nekaj konkretnih primerih vhodne tabele a. Kako hiter je v primerjavi z drugimi postopki urejanja, ki smo jih videli doslej? Kdaj se splača uporabiti urejanje s štetjem namesto teh drugih postopkov?