Квикселект
 | ||||||||
|
У рачунарству, квикселект је алгоритам селекције који проналази k-ти најмањи елемент у неуређеном низу. Уско је повезан са Квиксорт алгоритмом за сортирање. Оба су развијена од стране Тони Хора, па је алгоритам познат и као Хоров алгоритам селекције.[1] Као и квиксорт, ефикасан је у пракси и има добре перформансе у општем, али лоше у најгорем случају. Квикселект и његове варијанте су најчешће имплементирани алгоритми селекције у пракси и реалним апликацијама.
Квикселект користи сличан уопштен приступ као квиксорт, бира један елемент за пивовт и дели низ у две партиције елемената који су већи, односно мањи од пивота. Међутим, уместо два рекурзивна позива над сваком половином (као квиксорт) квикселект вриши рекурзију над једном страном - оном која садржи елемент који се тражи. Овај поступак смањује просечну сложеност са O(n log n) на O(n).
Као и квиксорт, квикселект се обично имплементира као алгоритам "у месту", и поред налажења k-тог елемента делимично сортира низ. Више о овом својству прочитајте у чланку о алгоритмима селекције.
Алгоритам[уреди | уреди извор]
У квиксорт алгоритму обично постоји помоћна функција particionisanje која, у линеарном времену, групише елементе (у интервалу [levi до desni] на оне који су мањи и оне који су већи или једнаки од неког датог елемента. Дат је псеудокод који врши партиционисање око елемента 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
Квиксорт алгоритам рекурзивно сортира обе гране што даје сложеност најбољег случаја Ω(n log n). Међутим, приликом селекције, већ је познато који део садржи тражени елемент, јер се пивот налази на фиксној сортираној позицији, са свим елементима пре и после њега у неуређеном поретку. Довољан је један рекурзивни позив за проналажење траженог елемента и по овом принципу конструишемо квикселект:
// 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)
Приметимо сличност са квиксорт алгоритмом: као што је алгоритам селекције за налажење минимума парцијални алгоритам сортирања секецијом, тако је и ово парцијални квиксорт, генеришући и делећи само O(log n) од O(n) партиција. Ова једноставна процедура има очекивану линеарну сложеност и, као квиксорт, добре перформасе у пракси. Такође спада у алгоритме који раде "у месту", што захтева само константно меморијско заузеће, с обзиром да се репна рекурзија може елиминисати на следећи начин:
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
Временска сложеност[уреди | уреди извор]
Као и квиксорт, квикселект има добре перформасе у просечном случају али то у великој мери зависи од избора пивота. Ако је повољно одабран пивот, односно елемент за који се конзистентно смањује скуп претраге, тада се експоненцијално смањује величина скупа и по индукцији можемо закључити да је сложеност линеарна (јер је сваки корак линеарне сложености а укопно време та вредност пута константа која зависи од тога којом брзином се смањује скуп претраге). Међутим, ако бирамо лош пивот, тако да у сваком кораку одбацујемо по један елемент, тада је сложеност најгорег случаја квадратна: O(n2). Ово се дешава, на пример, приликом тражења максималног елемента, када се увек за пивот бира први елемент, а подаци су већ сортирани.
Варијанте[уреди | уреди извор]
Најлакше решење је изабрати случајан пивот, који скоро сигурно даје линеарно време извршавања. Можемо детерминистички одабрати средњу од три вредности за пивот (као код квиксорт алгоритма), што даје линеарне перформансе над парцијално уређеним подацима, што је уобичајено у реалним ситуацијама. Међутим, погодно формиран низ и даље може произвести сложеност најгорег случаја; Давид Масер је описао такав низ који делује против стратегије избора средње вредности три елемента што је послужило као мотивација за Интроселект алгоритам.
Могуће је обезбедити линеарну сложеност, чак и у најгорем случају, избором погодне стратегије за одабир пивота. Ово је случај код алгоритма Средња вредност средњих вредности. Међутим, цена израчунавања пивота је превелика па се генерално не употребљава у пракси. Можемо комбиновати основни квикселект и "Средња вредност средњих вредности" како бисмо добили брз алгоритам у просечном случају и линеарну сложеност у најгорем случају. Овакав начин одређује интроселект алгоритам.
Прецизнија израчунавања просечног времена дају у најгорем случају сложеност за случајно изабране пивоте (у случају средњег; осталих k су нешто бржи).[2] Константа се може побољшати на 3/2 избором пивота нешто компликованијом стратегијом, дајући Флојд-Ривест алгоритам, који има просечну сложеност за средњи и нешто брже за k осталих.
Референце[уреди | уреди извор]
- ^ Hoare, C. A. R. (1961). „Algorithm 65: Find”. Comm. ACM. 4 (7): 321—322. doi:10.1145/366622.366647.
- ^ Blum-style analysis of Quickselect Архивирано на сајту Wayback Machine (9. јануар 2014), David Eppstein, October 9, 2007.