Hitro urejanje

Iz MaFiRaWiki

Vsebina


Hitro urejanje ali QuickSort je učinkovit algoritem za urejanje podatkov v tabeli. Je primer metode deli in vladaj, saj pri hitrem urejanju tabelo razdelimo na dve podtabeli, ki ju nato uredimo z enakim postopkom.

Algoritem sestoji iz treh korakov:

Izberemo delilni element, ki ga imenujemo pivot
Idealna izbira za pivot je mediana, to je tak element, da je ravno polovica elementov v tabeli manjša in polovica večja od njega. Ker pa mediane ne moremo poiskati v konstantnem času, ponavadi izberemo za pivot kar prvi element tabele ali naključni element tabele. Dobra izbira je tudi pivot, ki je mediana prvega, zadnjega in srednjega elementa tabele.
Elemente v tabeli premečemo
To naredimo tako, da so pred pivotom vsi elementi, ki so od njega manjši, in za njim vsi, ki so večji. Pri tem uporabimo Hoarov algoritem, ki potrebuje linearno število korakov. Glej funkcijo premeci v implementaciji.
Uredimo podtabeli elementov pred in za pivotom
Podtabeli uredimo z istim postopkom. Seveda tega ni treba početi na podtabeli velikosti 0 ali 1.

Algoritem zapišemo s psevdokodo:

 function hitro_uredi(q)
     spremenljivke manjsi, pivotSpr, vecji
     if dolzina(q) ≤ 1  
         vrni q  
     //premečemo elemente
     izberi vrednost pivota iz q
     za vsak x v q razen pivota
         ce x < pivot potem dodaj x k manjsim
         ce x ≥ pivot potem dodaj x k vecjim
     dodaj pivot v pivotSpr
     //uredimo manjše in večje, združevanje v praksi ni potrebno
     vrni zdruzi(hitro_uredi(manjsi), pivotSpr, hitro_uredi(vecji))
Stolpci predstavljajo elemente, rdeči stolpec je pivot.
Stolpci predstavljajo elemente, rdeči stolpec je pivot.


Optimizacija

Ker je hitro urejanje algoritem, ki uporablja rekurzijo, ga lahko še pospešimo, če z deljenjem na manjše probleme prenehamo že pri velikosti podproblema okoli 16 (točna meja je odvisna od procesorja, prevajalnika, ...), nato pa uporabimo urejanje z izbiranjem ali urejanje z vstavljanjem. V praksi je urejanje z vstavljanjem boljša izbira, saj ga ni potrebno izvajati sproti, ampak lahko na koncu z njim v linearnem času uredimo skoraj urejeno tabelo.

Časovna zahtevnost

Povprečna časovna zahtevnost hitrega urejanja je O(n \cdot \log(n)), v najslabšem primeru pa O(n2). Najslabši primer se pripeti, če urejamo urejeno tabelo, ali tabelo, ki je urejena v obtratnem vrstnem redu, in za pivot vedno izberemo prvi element.

Grafični prikaz

S pomočjo grafov prikažimo delovanje algoritma hitrega urejanja. Recimo, da ustavimo rekurzijo ko imamo v zaporedju še štiri elemente.

Na začetku imamo sledeče zaporedje:

Denimo, da na začetku naključno izberemo pivot 6, ter preuredimo tabelo

Nato, uredimo posebej del pred pivotom in del po pivotu

Ker smo predpostavili, da rekurzijo ustavimo, ko imamo še 4 elemente v zaporedju, sedaj lahko obe zaporedji samo še preuredimo in ju ponovno združimo(staknemo).

In tako dobimo

Implementacija

Glej tudi

Viri

Osebna orodja