Urejanje z izbiranjem

Zapišimo postopek urejanja z izbiranjem še v pythonu.

Izvedi Počisti



					

Vaja

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).