Hitro urejanje

Iz Wikipedije, proste enciklopedije

Hitro urejanje seznama naključnih števil. Vodoravne črte so delilni elementi (pivoti).

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 lahko uredimo vsak del posebej. To je možno, ker so v prvem delu tabele vsi elementi manjši od vseh elementov v drugem delu tabele. Za mejo se uporablja delilni element (pivot), katerega izberemo iz zaporedja. Poseben delilni element je mediana, ta je ravno v sredini med vsemi elementi.

[uredi] Izbiranje delilnega elementa

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

[uredi] Delovanje

Zaporedje pregledujemo z leve in desne strani. Levi indeks povečujemo, dokler ne naletimo na element, ki je večji ali enak od delilnega. Zatem zmanjšujemo desni indeks, dokler ne naletimo na element, ki je manjši ali enak od delilnega elementa. Ko naletimo na takšna elementa in se indeksa ne prekrižata, zamenjamo položaj teh dveh elementov. Kadar pa sta se prekrižala pa zamenjamo desni indeks z mejnim elementom in rekurzivno kličemo proceduro HitroUredi.

Nobeno od zaporedij ne vsebuje delilnega elementa, saj je le-ta že na pravilnem mestu.

[uredi] Zahtevnost

Časovna zahtevnost je v povprečju O(nlogn), v najslabšem primeru pa O(n²).

[uredi] 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))