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
Spoljašnje veze Everything2.com – Stooge sort Sorting Algorithms (including Stooge sort) Stooge sort – implementation and comparison
Категорија:Сортирање поређењем Категорија:Алгоритми сортирања