Pajac sortiranje
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.
 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 уреди
- 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.