Kvikselekt

Kvikselekt

Namena selekcija Struktura podataka Niz Vremenska kompl. O(n) do O(n²) Stabilan ne

U računarstvu, kvikselekt je algoritam selekcije koji pronalazi k-ti najmanji element u neuređenom nizu. Usko je povezan sa Kviksort algoritmom za sortiranje. Oba su razvijena od strane Toni Hora, pa je algoritam poznat i kao Horov algoritam selekcije. Kao i kviksort, efikasan je u praksi i ima dobre performanse u opštem, ali loše u najgorem slučaju. Kvikselekt i njegove varijante su najčešće implementirani algoritmi selekcije u praksi i realnim aplikacijama.

Kvikselekt koristi sličan uopšten pristup kao kviksort, bira jedan element za pivovt i deli niz u dve particije elemenata koji su veći, odnosno manji od pivota. Međutim, umesto dva rekurzivna poziva nad svakom polovinom (kao kviksort) kvikselekt vriši rekurziju nad jednom stranom - onom koja sadrži element koji se traži. Ovaj postupak smanjuje prosečnu složenost sa O(n log n) na O(n).

Kao i kviksort, kvikselekt se obično implementira kao algoritam "u mestu", i pored nalaženja k-tog elementa delimično sortira niz. Više o ovom svojstvu pročitajte u članku o algoritmima selekcije.

Algoritam

U kviksort algoritmu obično postoji pomoćna funkcija particionisanje koja, u linearnom vremenu, grupiše elemente (u intervalu [levi do desni] na one koji su manji i one koji su veći ili jednaki od nekog datog elementa. Dat je pseudokod koji vrši particionisanje oko elementa niz[pivotIndeks]:

 function particionisanje(niz, levi, desni, pivotIndeks)
     pivot := niz[pivotIndeks]
     swap niz[pivotIndeks] and niz[desni]  // Pomeri pivot na kraj
     storeIndeks := levi
     for i from levi to desni-1
         if niz[i] < pivot
             swap niz[storeIndeks] and niz[i]
             increment storeIndeks
     swap niz[desni] and niz[storeIndeks]  // Postavi pivot na konacnu poziciju
     return storeIndeks

Kviksort algoritam rekurzivno sortira obe grane što daje složenost najboljeg slučaja Ω(n log n). Međutim, prilikom selekcije, već je poznato koji deo sadrži traženi element, jer se pivot nalazi na fiksnoj sortiranoj poziciji, sa svim elementima pre i posle njega u neuređenom poretku. Dovoljan je jedan rekurzivni poziv za pronalaženje traženog elementa i po ovom principu konstruišemo kvikselekt:

  // Vraca n-ti najmanji element niza iz intervala [levi..desni]
  // (odnosno vazi levi <= n <= desni).
  // Prostor pretrage u nizu se menja u svakom prolazu ali niz
  // i dalje ima istu velicinu, pa nije potrebno svaki put postavljati n
  function izaberi(niz, levi, desni, n)
     if levi = desni        // Ako niz sadrzi samo jedan element,
         return niz[levi]   // vrati taj element
     pivotIndeks  := ...     // izaberi pivotIndeks izmedju "levi" i "desni",
                            // odnosno, levi + floor(rand() % (desni - levi + 1))
     pivotIndeks  := particionisanje(niz, levi, desni, pivotIndeks)
     // Pivot je na konacnom sortiranom mestu
     if n = pivotIndeks
         return niz[n]
     else if n < pivotIndex
         return izaberi(niz, levi, pivotIndeks - 1, n)
     else
         return izaberi(niz, pivotIndeks + 1, desni, n)

---

Primetimo sličnost sa kviksort algoritmom: kao što je algoritam selekcije za nalaženje minimuma parcijalni algoritam sortiranja sekecijom, tako je i ovo parcijalni kviksort, generišući i deleći samo O(log n) od O(n) particija. Ova jednostavna procedura ima očekivanu linearnu složenost i, kao kviksort, dobre performase u praksi. Takođe spada u algoritme koji rade "u mestu", što zahteva samo konstantno memorijsko zauzeće, s obzirom da se repna rekurzija može eliminisati na sledeći način:

 function izaberi(niz, levi, desni, n)
     loop
         if levi = desni
             return niz[levi]
         pivotIndeks := ...     // izaberi pivotIndeks izmedju "levi" i "desni"
         pivotIndeks := particionisanje(niz, levi, desni, pivotIndeks)
         if n = pivotIndeks
             return niz[n]
         else if n < pivotIndeks
             desni := pivotIndeks - 1
         else
             levi := pivotIndeks + 1

Vremenska složenost

Kao i kviksort, kvikselekt ima dobre performase u prosečnom slučaju ali to u velikoj meri zavisi od izbora pivota. Ako je povoljno odabran pivot, odnosno element za koji se konzistentno smanjuje skup pretrage, tada se eksponencijalno smanjuje veličina skupa i po indukciji možemo zaključiti da je složenost linearna (jer je svaki korak linearne složenosti a ukopno vreme ta vrednost puta konstanta koja zavisi od toga kojom brzinom se smanjuje skup pretrage). Međutim, ako biramo loš pivot, tako da u svakom koraku odbacujemo po jedan element, tada je složenost najgoreg slučaja kvadratna: O(n²). Ovo se dešava, na primer, prilikom traženja maksimalnog elementa, kada se uvek za pivot bira prvi element, a podaci su već sortirani.

Varijante

Najlakše rešenje je izabrati slučajan pivot, koji skoro sigurno daje linearno vreme izvršavanja. Možemo deterministički odabrati srednju od tri vrednosti za pivot (kao kod kviksort algoritma), što daje linearne performanse nad parcijalno uređenim podacima, što je uobičajeno u realnim situacijama. Međutim, pogodno formiran niz i dalje može proizvesti složenost najgoreg slučaja; David Maser je opisao takav niz koji deluje protiv strategije izbora srednje vrednosti tri elementa što je poslužilo kao motivacija za Introselekt algoritam.

Moguće je obezbediti linearnu složenost, čak i u najgorem slučaju, izborom pogodne strategije za odabir pivota. Ovo je slučaj kod algoritma Srednja vrednost srednjih vrednosti. Međutim, cena izračunavanja pivota je prevelika pa se generalno ne upotrebljava u praksi. Možemo kombinovati osnovni kvikselekt i "Srednja vrednost srednjih vrednosti" kako bismo dobili brz algoritam u prosečnom slučaju i linearnu složenost u najgorem slučaju. Ovakav način određuje introselekt algoritam.

Preciznija izračunavanja prosečnog vremena daju u najgorem slučaju složenost $n(2+2\log 2+o(1))\leq 3.4n+o(n)$ za slučajno izabrane pivote (u slučaju srednjeg; ostalih k su nešto brži). Konstanta se može poboljšati na 3/2 izborom pivota nešto komplikovanijom strategijom, dajući Flojd-Rivest algoritam, koji ima prosečnu složenost $1.5n+O(n^{1/2})$ za srednji i nešto brže za k ostalih.