Hitro urejanje
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.
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) |
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
urediZaporedje 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
urediZ dobro izbiro delilnega elementa lahko preprečimo, da bi se zgodil najslabši primer in bi algoritem potreboval operacij.
Največkrat uporabljani delilni elementi so:
- prvi element
- zadnji element
- naključno izbran element
- sredinski element ali mediana
Zahtevnost
urediČasovna zahtevnost je v povprečju , v najslabšem primeru pa .
Psevdokoda
urediV 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))