Pajac sortiranje

Pajac sortiranje
Prikaz pajac sortiranja.
Класа	Algoritam za sortiranje
Структура података	Niz
Најгора перформанца	O(n^{log 3 /log 1.5})
Најгора просторна комплексност	O(n)

Pajac sortiranje je rekurzivan algoritam za sortiranje sa kompleksnošću O(nlog 3 / log 1.5 ) = O(n2.7095...). Njegova brzina je očigleno manja od nekih poznatijih algoritama kao što je sortiranje spajanjem, ali takođe je manja i od bablsorta, koji se smatra jednim od najgorih algoritama za sortiranje.

Algoritam je ovako definisan:

Ako je vrednost na kraju manja od vrednosti na početku, zameni ih
Ako ima 3 ili više elemanta u nizu, onda:
- Sortiraj ovim algoritmom početne 2/3 niza
- Sortiraj ovim algoritmom poslednje 2/3 niza
- Ponovo sortiraj prve 2/3 niza
Else: izlazi se iz procedure

Važno je da se dobije ceo broj u rekurzivnom pozivanju zaokruživanja gornje 2/3, npr. zaokruživanje 2/3 od 5 elemenata treba da bude 4, a ne 3, jer u suprotnom algoritam može da padne. Ali ako se kod napiše da se završava na baznom slučaju veličine 1, umesto da bude 1 ili 2, zaokruživanje 2/3 na gore daje beskonačan broj poziva.

Algoritam je dobio ime po emisiji u kojoj svaka luda udari drugu dvojicu.

Implementacija

 function stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if (j - i + 1) > 2 then
         t = (j - i + 1) / 3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

Literatura

Black, Paul E. „stooge sort”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Приступљено 18. 6. 2011.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „Problem 7-3”. Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. стр. 161—162. ISBN 0-262-03293-7.