Hitro urejanje

Hitro urejanje
Hitro urejanje seznama naključnih števil. Vodoravne črte so delilni elementi (pivoti).
Osnovni podatki
Vrsta:	algoritem za urejanje podatkov
Podatkovna struktura:	tabela
Časovna zahtevnost
Zgornja meja zahtevnosti:	O(n2)
Spodnja meja zahtevnosti:	O(n log n)
Pričakovana zahtevnost:	O(n log n)
Prostorska zahtevnost
Prostorska zahtevnost:	O(n)

Hitro urejanje ali urejanje s porazdelitvami (angleško 'QuickSort') je eden od najbolj znanih in uporabljanih algoritmov za urejanje podatkov; razvil ga je C. A. R. Hoare.

Algoritem razdeli zaporedje na dve podzaporedji tako, da so v prvem delu tabele vsi elementi manjši od elementov v drugem delu tabele. Enak postopek se nato izvede nad obema podzaporedjema, dokler po principu rekurzije ne pridemo do urejenega zaporedja.

Delovanje

Zaporedje razdelimo na podzaporedji tako, da izberemo nek delilni element (pivot) iz zaporedja, nato pa zaporedje pregledujemo z leve in desne strani. Levi indeks povečujemo, dokler ne naletimo na element, ki je večji ali enak delilnemu elementu. Zatem zmanjšujemo desni indeks, dokler ne naletimo na element, ki je manjši ali enak delilnemu elementu. Ko naletimo na takšna elementa in se levi in desni indeks še nista prekrižala, zamenjamo položaj teh dveh elementov. Kadar pa se indeksa prekrižata, zamenjamo desni indeks z mejnim elementom.

Postopek delitve nato rekurzivno ponovimo nad podzaporedjema, pri čemer podzaporedji ne vsebujeta delilnega elementa, saj je le-ta že na pravilnem mestu na sredini med njima. Ko pridemo do podzaporedij dolžine ena, je celotno zaporedje urejeno.

Izbira delilnega elementa

Z dobro izbiro delilnega elementa lahko preprečimo, da bi se zgodil najslabši primer in bi algoritem potreboval $O(n^{2})$ operacij.

Največkrat uporabljani delilni elementi so:

• prvi element
• zadnji element
• naključno izbran element
• sredinski element ali mediana

Zahtevnost

Časovna zahtevnost je v povprečju $O(n\log n)$, v najslabšem primeru pa $O(n^{2})$.

Psevdokoda

V preprosti psevdokodi lahko ta algoritem izrazimo takole:

 funkcija HitroUrejanje(q)
     var seznam manjši, pivotSeznam, večji
     če dolžina(q) ≤ 1
         vrni q
     izberi vrednost delilnega elementa pivot izmed q
     za vsak x v q
         če x < pivot potem dodaj x k manjši
         če x = pivot potem dodaj x k pivotSeznam
         če x > pivot potem dodaj x k večji
     vrni poveži(HitroUrejanje(manjši), pivotSeznam, HitroUrejanje(večji))