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?