Selekcioni algoritam

U informatici, selekcioni algoritam je algoritam koji pronalazi k-ti najmanji element u povezanoj listi ili nizu. Ovaj algoritam uključuje i slučajeve traženja najmanjeg elementa i najvećeg elementa, kao i medijane. Postoje algoritmi koji su vremenske složenosti O(n), a postoje i algoritmi sublinearne složenosti za posebne podatke (ekstremni slučaj, O(1) za sortirane podatke). Selekcija je podproblem kompleksnijih problema poput traženja najbližeg komšije i najkraćeg puta. Mnogi algoritmi za selekciuju su izvedeni iz algoritama sortiranja, ali i neki algoritmi za sortiranje se mogu implementirati ponavljanjem procesa selekcije.

Najjednostavniji algoritam za traženje k-tog elementa je traženje minimuma ili maksimuma, zatim u narednim iteracijama ponovno traženje minimuma odnosno maksimuma preostalih članova. U ovom slučaju je najteže naći medijanu, pošto je potrebno ponoviti ovaj proces n/2 puta. Ipak, postoji specijalni algoritam za selekciju medijane, koji se može koristi za generalni algoritam selekcije. Najkorišćeniji algoritam je kvikselekt, koji sličan algoritmu kviksortom. Poput kviksorta, asimptotski ima optimalne performanse, ali u najgorem slučaju ima loše, što se može modifikovati, tako da pruže optimalne performanse i u najgorem scenariju.

Selekcija sortiranjem

Traženje k-tog elementa niza ili povezane liste se može izvršiti tako što će se niz ili povezana lista sortirati, zatim izabrati željeni element. Ovaj način selektovanja se svodi na probleme sortiranja. Iako neefikasan za biranje jednog elementa, ovaj metod može biti efikasan ukoliko nam je potrebno da izaberemo više elemenata, tako što ćemo sortirati niz ili listu u složenosti O(n log n), zatim u vremenskoj složenosti O(1) izabrati svaki željeni element u nizu, odnosno O(n) za odabir svih željenih elemenata u povezanoj listi. Generalno, sortiranje se izvršava u složenosti (n log n), gde je n dužina niza, ali moguće je i sortiranje algoritmima koji ne koriste poređenje elemenata, poput radiks sortiranja i sortiranja prebrojavanjem.

Bolji način od sortiranja celog niza ili liste je parcijalno sortiranje najvećih ili najmanjih k elemenata. Posle sortiranja, elementima možemo pristupati u O(1) za svaki element u nizu, ili O(k), za sve elemente u listi. Za sortiranje niza ili liste na ovaj način je vremenski potrebno O(n + k log k), što je za malo k, velika ušteda u odnosu na sortiranje celog niza.

Neuređeno pracijalno sortiranje

Ukoliko primenimo algoritam parcijalnog sortiranja za k elemenata, ali ne poređamo elemente redom, oslobađamo se faktora O(k log k). Potom, traženje maksimuma u podnizu od k elemenata se može uraditi u O(k) vremenu. Kako je $k\leq n$ i za ovaj deo algoritma će nam asimptotski biti potrebno O(n) vremena.

Na lak način se mogu izdvojiti k najmanjih elemenata, tako što ćemo proći ceo niz ili listu, i obeležiti sve elemente elemente koji su manji od k-tog. Takđe, ovaj algoritam se izvršava u O(n) vremenu.

Izbor parcijalnim sortiranjem

Jednostavan primer izbora elemenata parcijalnim sortiranjem je samo korišćenje parcijalnog sortiranja selekcijom

Očigledan linearni algoritam za traženje minimuma/maksimuma, koji se svodi na prolaženje kroz svaki element niza ili liste i pamćenje minimuma/maksimuma koji se primenjuje u sortiranju selekcijom, može biti optimizovan algoritmima poput hip sorta.

Generalno, parcijalno sortiranje selekcijom se izvršava u vremenskoj složenosti O(kn). Asimptotski, ovaj algoritam je neefikasan, ali za malo k može biti efikasan i jednostavan je za implementaciju. Jednostavno, nađemo minimalan element i stavimo ga na početak. Ako proces ponovimo k puta, k-ti element u nizu ili listu će zaista biti k-ti element po veličini. Algoritam izgleda ovako:

 function select(lista[1..n], k)
     for i from 1 to k
         najmanjiIndeks = i
         najmanjaVrednost = lista[i]
         for j from i+1 to n
             if lista[j] < najmanjaVrednost
                 najmanjiIndeks = j
                 najmanjaVrednost = lista[j]
         swap lista[i] and lista[najmanjiIndeks]
     return lista[k]

Odabir elemenata baziran na particiji

Linearne performanse se mogu dostići korišćenjem algoritma kvikselekt. Kvikselekt je modifikacija algoritma kviksort. U oba algoritma se bira pivot i zatim se prema njemu deli na particije. Dok kviksort obrađuje obe particije, kvikselekt obrađuje samo stranu gde se željeni k-ti element nalazi. kvikselekt ovom optimizacijom ima prosečnu složenost O(n). Za pivot se obično bira prvi element, što u najvećem broju slučaja daje rezultate u složenosti O(n). Problem se javlja kod već sortiranih nizova, gde se može iskoristiti nasumičan odabir pivota. Takođe, postoje kombinovane metode algoritama, koji rade u prosečnom vremenu za oba slučaja.

Algoritmi bazirani na particiji se generalno izvršavaju u mestu (u memorijskoj složenosti O(1)) i svojim izvršavanjem parcijalno sortiraju podatke. Ukoliko se algoritam ne izvršava u mestu, potrebno je obezbediti još O(n) memorijskog prostora.

Strategija biranja medijane za pivot

Algoritmi za selekciju mogu biti realizovani preko modifikacije kvikselekta ili kviksorta, tako što će se za pivot uvek uzimati element čija je vrednost medijana posmatranog skupa. Ukoliko je izbor pivota aimptotski optimalan (u linearnom vremenu), onda je i selekcija i sortiranje takođe optimalno. U praksi se ova tehnika ne koristi, ali je od teorijskog značaja.

Ukoliko se ovaj algoritam za biranje pivota iskoristi u algoritmu kvikselekt i traženje medijane bude optimalno, i sam kvikselekt će se izvršavati u optimalnom (linearnom) vremenu, odnosno O(n). Razlog za to je činjenica da algoritam kvikselekt pripada grupi algoritama podeli pa vladaj, i korišćenje medijane kao pivota će dovesti do toga da se posmatrani skup uvek prepolovi, pa će broj koraka predstavljati geometrijsku progresiju.

Slično, ovaj pristup se može iskoristiti u algoritmu kviksort. Ukoliko izaveremo medijanu za pivot u svakom koraku u optimalnom vremenu O(n), ceo algoritam će imati vremensku složenost O(n log n). Medijana je najbolji pivot za sortiranje, zato što deli skup na podjednake delove, i time garantuje optimalno sortiranje, pretpostavljajući da je algoritam za selekciju medijane optimalan.

Inkrementalno sortiranje selekcijom

Konverzija algoritma za selekciju u algoritam za soritranje se može uraditi jednostavnim njegovim ponavljanjem. Sam algoritam vraća jedan član niza ili liste (k-ti element), ali u praksi algoritam često sortira deo niza (odnosno sve pivote pre k - tog elementa po veličini.) Elementi između 2 pivota su i po vrednosti između njih, ali ne poređani redom.

Činjenica da sortiramo do nza može biti od značaja ukoliko radimo sa istim podacima. U ekstremnom slučaju kada nam je niz sortiran, elementu možemo pristupiti u O(1).

Kod parcijalno sortiranih nizova, ukoliko tražimo j-ti po redu, gde je j manje ili jednako k, j-tom elementu možemo pristupiti takođe u vremenskoj složenosti O(1). Ukoliko je j veće od k, samo je potrebno sortirati elemente veće od k-tog.

Ukoliko smo element našli algoritmom kvikselekt i potrebno nam je da posle toga nađemo novi k-ti po redu, dovoljno je da posmatramo elemente dva pivota.

Korišćenje struktura podataka za selekciju u sublinearnom vremenu

Za neuređenu listu podataka, minimalni element se može naći u linearnom vremenu (Ω(n)), jer se mora proći kroz svaki element (u suprotnom bismo ga mogli propustiti). Ako uredimo listu, npr. da bude uvek sortirana, onda je izbor k-tog najvećeg elementa trivijalan, ali tada umetanje zahteva linearno vreme, kao i ostale operacije kao što je spajanje dve liste.

Strategija za postizanje sublinearnog vremena je da se skladište podaci na organizovan način koristeći odgovarajuće strukture podataka koje olakšavaju selekciju. Dve takve strukture podataka su stabla i tabele učestalosti.

Kada se traži samo minimum (ili maksimum), dobar pristup je korišćenje hipa koji nalazi minimalni (ili maksimalni) element u konstantnom vremenu, dok su sve ostale operacije, uključujući umetanje, O(log n) složenosti ili efikasnije. Uopšteno govoreći, samobalansirajuće binarno stablo pretrage se može nadograditi tako da omogući umetanje elementa kao i pronalaženje k-tog najvećeg elementa u O(log n) vremenu. Jednostavno u svakom čvoru čuvamo broj njegovih potomaka i koristimo ovo da odredimo kojim putem ćemo se dalje kretati. Brojač se efikasno može ažurirati jer dodavanje čvora utiče samo na O(log n) njegovih predaka, a rotacije stabla utiču samo na brojače čvorova koji su rotirani.

Još jedna jednostavna strategija je korišćenje heš tabela. Kada unapred znamo opseg vrednosti, možemo podeliti taj opseg na h podintervala i dodeliti im h polja. Kada umećemo element, upisujemo ga u polje koje odgovara intervalu u koji taj element pada. Da bismo pronašli minimalni ili maksimalni element, u tabeli tražimo od početka ili od kraja prvo neprazno polje i tražimo minimalni ili maksimalni element u njemu. Generalno, za pronalaženje k-tog elementa, pamtimo broj elemenata u svakom polju i onda pretražujemo polja sleva nadesno sabirajući brojače dok ne stignemo do polja koje sadrži traženi element. Željeni element se u tom polju može pronaći za očekivano linearno vreme.

Ako izaberemo h da bude približno √n, za ulaz koji je približno ravnomerno raspoređen, ovaj algoritam može da izvršava selekcije u očekivanom O(√n) vremenu. Nažalost, ova strategija je osetljiva na grupisanje elemenata u uske intervale, što može dovesti do ćelija sa velikim brojem elemenata (grupisanje se može eliminisati odabirom dobre heš funkcije, ali pronalaženje elementa sa k-tom najvećom heš vrednošću nije veoma korisno). Dodatno, kao i heš tabele, ova struktura zahteva promenu veličine tabele kako bi se održala efikasnost u slučajevima kada n postane mnogo veće od h².

Donje ograničenje

U knjizi Umetnost računarskog programiranja (engl. The Art of Computer Programming), Donald Knut raspravlja o izvesnom broju donjih ograničenja za broj upoređivanja potrebnih za lociranje t najmanjih unetih podataka neuređene list od n elemenata (koristeći samo upoređivanja). Postoji trivijalno donje ograničenje od n - 1 za minimalni ili maksimalni unos. Da bi se ovo videlo, razmotrimo takmičenje u kojem svaka igra predstavlja jedno poređenje. Kako svaki igrač, osim pobednika takmičenja, mora izgubiti jednu igru pre nego što saznamo pobednika, imamo donju granicu od n - 1 poređenja.

Priča postaje složenija za druge indekse. Definišimo $W_{t}(n)$ kao minimalni broj poređenja potrebnih da se pronađe t najmanjih vrednosti. Knut upućuje na rad S. S. Kislicina (engl. S. S. Kislitsyn) koji pokazuje gornje ograničenje ove vrednosti:

$W_{t}(n)\leq n-t+\sum _{n+1-t<j\leq n}\lceil {\log _{2}\,j}\rceil$ za $n\geq t$

Ova granica se postiže za t = 2, ali se bolja i složenija ograničenja postižu za veće vrednosti t.

Prostorna složenost

Lako se vidi da je prostorna složenost selekcionog algoritma k + O(1) (ili n - k ako je k > n/2), a algoritmi u mestu mogu da izaberu za O(1) dodatnog prostora. Prostor za k elemenata je neophodan što se lako pokazuje: počinjemo sa 1,2, ..., k, zatim nastavljamo sa k + 1, k + 1, ..., k + 1, i konačno završavamo sa j kopija 0, gde se j kreće od 0 do k - 1. U ovom slučaju, k-ti najmanji element je jedan od 1, 2, ..., k, u zavisnosti od broja 0, što se može zaključiti tek na kraju. Inicijalnih k elemenata se moraju čuvati skoro do samog kraja jer ne možemo smanjiti broj mogućih elemenata manjih od najmanjih k vrednosti sve dok nam ne ostane manje od k elemenata. Primetimo da je pronalaženje minimuma (ili maksimuma) traženjem tekućeg minimuma specijalan slučaj kada je k = 1.

Ova prostorna složenost je postignuta korišćenjem progresivnog delimičnog sortiranja - traženje sortirane liste trenutnih najmanjih k elemenata. Primetimo, međutim, da selekcija parcijalnim sortiranjem, iako prostorno efikasna, ima superlinearnu vremensku složenost i da vremenski efikasni selekcioni algoritmi bazirani na particionisanju zahtevaju O(n) prostora.

Ovo prostorno ograničenje objašnjava usku povezanost između biranja k-tog elementa i biranja (neuređenih) k najmanjih elemenata, jer se vidi da efektivni odabir k-tog elementa zahteva biranje najmanjih k elemenata kao među-korak.

Prostorna složenost može postati problem kada je k fiksni deo od k, naročito kod izračunavanja medijane, gde je k = n/2, kao i kod onlajn algoritama. Prostorna složenost se može poboljšati po cenu dobijanja delimičnog odgovora ili tačnog odgovora određene verovatnoće. O ovome će biti više reči u nastavku.

Onlajn selekcioni algoritam

Onlajn selekcija se može usko odnositi na računanje k-tog najmanjeg elementa toka, u čijem slučaju se mogu koristiti parcijalno sortirajući algoritmi (sa k + O(1) prostora za trenutnih k najmanjih elemenata), ali algoritmi bazirani na particiji ne mogu.

Alternativno, može biti neophodno da sama selekcija bude onlajn, tj. elementi mogu biti izabrani iz sekvencijalnog ulaza u trenutku posmatranja i svaki izbor, odnosno odbacivanje, je neopozivo. Problem je izabrati, pod ovim ograničenjima, tačan element iz ulaznog niza (npr. najveće ili najmanje vrednosti) sa najvećom verovatnoćom.

Najjednostavniji primer je problem sekretara u kojem se traži maksimum sa najvećom verovatnoćom, u čijem slučaju je optimalna strategija (na slučajnom ulazu) pronaći maksimum od prvih n/e elemenata, i potom izabrati prvi element koji je veći od tog maksimuma.

Jezička podrška

Veoma mali broj jezika ima ugrađene funkcije za generalne selekcije, iako većina obezbeđuje funkcije za pronalaženje najmanjeg ili najvećeg elementa u povezanoj listi. Značajan izuzetak je programski jezik C++, koji obezbeđuje šablonsku metodu nth_element (n-ti element) koja garantuje linearnu vremensku složenost, a takođe i deli ulazni podatak zahtevajući da n-ti element bude sortiran na svoje odgovarajuće mesto, odnosno da su elementi pre n-tog elementa manji od njega, a elementi posle n-tog elementa veći od njega. Poželjno je, ali ne i obavezno, da podela ulaznog podatka bude zasnovana na Horovom algoritmu (ili nekoj njegovoj varijaciji) koji ima prosečnu linearnu vremensku složenost.

C++ takođe obezbeđuje i nth_element (n-ti element) ugrađenu funkciju koja rešava problem pronalaženja najmanjeg k-tog elementa u linearnom vremenu, istovremeno preuređujući ulazni podatak. Ona se može iskoristiti i za rešavanje problema pronalaženja najvećeg k-tog elementa u linearnom vremenu, preuređujući u obrnutom poretku.

Standardna biblioteka programskog jezika Pajton (od 2.4) uključuje heapq.nsmallest() i nlargest() funkcije koje vraćaju sortirane liste, za O(n log k) vremensku složenost.

S obzirom da je jezička podrška za sortiranje sve više prisutna, pojednostavljeni pristup sortiranju koje je praćeno indeksiranjem je poželjno u mnogim okruženjima uprkos svom nedostatku u brzini.

Literatura

• Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (1973). „Time bounds for selection” (PDF). Journal of Computer and System Sciences. 7 (4): 448—461. doi:10.1016/S0022-0000(73)80033-9. 
• Floyd, R. W.; Rivest, R. L. (1975). „Expected time bounds for selection”. Communications of the ACM. 18 (3): 165—172. doi:10.1145/360680.360691. 
• Kiwiel, K. C. (2005). „On Floyd and Rivest's SELECT algorithm”. Theoretical Computer Science. 347: 214—238. doi:10.1016/j.tcs.2005.06.032. 
• Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison-Wesley. ISBN 978-0-201-89685-5.  Section 5.3.3: Minimum-Comparison Selection. str. 207—219.
• Thomas H. Cormen; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.  Chapter 9: Medians and Order Statistics. str. 183—196. Section 14.1: Dynamic order statistics. str. 302—308.
• Paul E. Black, Select at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.

Spoljašnje veze

• "Lecture notes for January 25, 1996: Selection and order statistics", ICS 161: Design and Analysis of Algorithms, David Eppstein