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.

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

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

уреди

Spoljašnje veze

уреди