Urejanje z izbiranjem

Iz MaFiRaWiki

V podčlanku /Navadno izbiranje najdete tudi študentski prispevek na to temo,

ki ga želimo združiti s tem člankom.

Urejanje z izbiranjem je algoritem za urejanje podatkov v dani tabeli. Primerno je za manjše tabele, ker za večje tabele obstajajo bolj učinkoviti postopki. Časovna zahtevnost urejanja z izbiranjem je O(n2).

Dana je tabela podatkov

a_0, a_1, \ldots, a_{n-1},

ki jih znamo primerjati po velikosti, abecednem redu, ali kaki drugi linearni urejenosti. Urejanje z izbiranjem premeče elemente tabele tako, da so ti na koncu razporejeni po velikosti.

Tabela je med urejanjem razdeljena na urejeni del, ki mu sledi neurejeni del. Na začetku je urejeni del prazen in neurejeni del celotna tabela. Nas vsakem koraku urejeni del povečamo za en element tako, da poiščemo najmanjši element neurejenega dela in ga zamenjamo z elementom, ki je na začetku neurejenega dela.

Zgled

Slika:Izbira.jpg


Časovna zahtevnost

Urejanje z izbiranjem tabele z n elementi ima časovno zahtevnost O(n2), saj vedno opravi (n-1) + (n-2) + \cdots + 1 = n(n-1)/2 \in O(n^2) primerjav in n − 1 zamenjav.


Implementacija

Osebna orodja