Zapišimo postopek urejanja z izbiranjem še v pythonu.
(a) Dopolni funkcijo UrejanjeZIzbiranjem
tako, da na koncu vsake iteracije glavne zanke izpiše tabelo a
in pri tem z navpično črto loči urejeni del od neurejenega, podobno kot v našem primeru zgoraj.
(b) Preizkusi funkcijo na nekaj konkretnih primerih vhodne tabele a
.
(c) Izmeri čas izvajanja prvotne funkcije (brez izpisovanja tabele) na različno dolgih tabelah (do nekaj 100 elementov). Oceni njeno časovno zahtevnost.
(d) Kako na čas izvajanja vpliva začetno stanje tabele a
? Preizkusi funkcijo na nekaj tabelah, ki so vse enako dolge in vsebujejo enake elemente, vendar v različnih vrstnih redih.
Razmislimo še o časovni zahtevnosti tega postopka. Vidimo lahko, da ima po dve gnezdeni zanki; zunanja zanka (po k) ima približno n iteracij, notranja zanka (po i) pa ima pri vsakem k tudi do približno n iteracij. Tako se torej izvede največ n ⋅ n = n2 iteracij notranje zanke, v vsaki od njih pa imamo po eno primerjavo dveh elementov tabele; naš postopek torej izvede O(n2) primerjav. Poleg tega izvede tudi O(n) zamenjav po dveh elementih (pri vsakem k mora zamenjati k-ti element z najmanjšim elementom iz doslej neurejenega dela tabele). Trajanje posamezne primerjave (in tudi trajanje posamezne zamenjave) načeloma ni odvisno od n, tako da lahko zaključimo, da je časovna zahtevnost našega postopka O(n2), pri čemer največ časa porabimo za primerjave.
Kot zanimivost omenimo še naslednje. V učni enoti o porabi časa in časovni zahtevnosti smo videli, da če isti postopek zaženemo na različnih, vendar enako velikih primerkih problema, se lahko čas izvajanja od primerka do primerka zelo razlikuje. Pri urejanju z izbiranjem pa takih razlik ni; na vsaki tabeli dolžine n, ne glede na to, kako so na začetku urejeni ali premešani njeni elementi, se izvede enako število primerjav (ena za vsak par k in i) ter enako število zamenjav (ena za vsak k).