Stooge sort
 Visualisering av Stooge-sort (visar endast byten).
| |
| Klass | Sorteringsalgoritm |
|---|---|
| Datastruktur | Array |
| Prestanda i värsta fall | O( n log 3/log 1,5 ) |
| Värsta tänkbara utrymmeskomplexitet | O( n ) |
Stooge sort är en rekursiv sorteringsalgoritm . Det är anmärkningsvärt för sin exceptionellt dåliga tidskomplexitet O ( n log 3 / log 1,5 ) = O( n 2,7095... ) . Algoritmens körtid är alltså långsammare jämfört med rimliga sorteringsalgoritmer och är långsammare än bubble sort , ett kanoniskt exempel på en ganska ineffektiv sort. Det är dock mer effektivt än Slowsort . Namnet kommer från The Three Stooges .
Algoritmen definieras enligt följande:
- Om värdet i början är större än värdet i slutet, byt ut dem.
- Om det finns 3 eller fler element i listan, då:
- Stooge sorterar de första 2/3 av listan
- Stooge sorterar de sista 2/3 av listan
- Stooge sorterar de första 2/3 av listan igen
Det är viktigt att få heltalssorteringsstorleken som används i de rekursiva anropen genom att avrunda 2/3 uppåt , t.ex. bör avrundning 2/3 av 5 ge 4 istället för 3, eftersom sorteringen annars kan misslyckas på vissa data.
Genomförande
0
function stoogesort ( array L , i = , j = length ( L ) - 1 ){ if L [ i ] > L [ j ] then // Om elementet längst till vänster är större än elementet längst till höger L [ i ] ↔ L [ j ] // Byt elementet längst till vänster och elementet längst till höger om ( j - i + 1 ) > 2 sedan // Om det finns minst 3 element i arrayen t = floor (( j - i + 1 ) / 3 ) // Avrundning nedåt stoogesort ( L , i , j - t ) // Sortera de första 2/3 av arrayen stoogesort ( L , i + t , j ) // Sortera de sista 2/3 av arrayen stoogesort ( L , i , j - t ) // Sortera de första 2/3 av arrayen igen return L }
0
0
-- Inte den bästa men lika med ovan stoogesort :: ( Ord a ) => [ a ] -> [ a ] stoogesort [] = [] stoogesort src = innerStoogesort src (( längd src ) - 1 ) innerStoogesort :: ( Ord a ) => [ a ] -> Int -> Int -> [ a ] innerStoogesort src i j | ( j - i + 1 ) > 2 = src'''' | annars = src' där src' = swap src i j -- behöver varje anrop t = floor ( fromIntegral ( j - i + 1 ) / 3.0 ) src'' = innerStoogesort src' i ( j - t ) src''' = innerStoogesort src'' ( i + t ) j src'''' = innerStoogesort src''' i ( j - t ) swap :: ( Ord a ) => [ a ] -> Int -> Int -> [ a ] byta src i j | a > b = replaceAt ( replaceAt src j a ) i b | annars = src där a = src !! i b = src !! j replaceAt :: [ a ] -> Int - > a - > [ a ] replaceAt ( x : xs ) indexvärde | index == = värde : xs | annars = x : ersätt Vid xs ( index - 1 ) värde
Källor
- Black, Paul E. "stooge sort" . Ordbok över algoritmer och datastrukturer . National Institute of Standards and Technology . Hämtad 18 juni 2011 .
- Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "Problem 7-3". Introduktion till algoritmer (2:a upplagan). MIT Press och McGraw-Hill. s. 161–162. ISBN 0-262-03293-7 .