Stooge sort
Stooge sort (Sortering efter dele [1] , Vandrende sortering [2] ) er en rekursiv sorteringsalgoritme med tidskompleksitet . Algoritmens køretid er således ekstremt lang sammenlignet med effektive sorteringsalgoritmer som Merge Sort .
Algoritmen til at sortere en liste over elementer er som følger:
- Hvis værdien af elementet i slutningen af listen er mindre end værdien af elementet i begyndelsen, skal du bytte dem.
- Hvis der er 3 eller flere elementer i den aktuelle delmængde af listen, så:
- Kald rekursivt Stooge sort på den første 2/3 af listen
- Kald rekursivt Stooge sort på de sidste 2/3 af listen
- Kald rekursivt Stooge sort på den første 2/3 af listen igen
- Ellers: vende tilbage
Implementeringseksempler
algoritme stoogesort ( array L , i = 0 , j = længde ( L ) - 1 ) hvis L [ j ] < L [ i ] så L [ i ] ↔ L [ j ] hvis j - i > 1 så t = ( j - i + 1 ) / 3 stoogesort ( L , i , j - t ) stoogesort ( L , i + t , j ) stoogesort ( L , i , j - t ) retur LEksempel i C
void stoogesort ( int * item , int left , int right ) { register int tmp , k ; if ( element [ venstre ] > element [ højre ]) { tmp = element [ venstre ]; item [ venstre ] = vare [ højre ]; item [ højre ] = tmp ; } hvis (( venstre + 1 ) >= højre ) returnere ; k = ( int )(( højre - venstre + 1 ) / 3 ); stoogesort ( item , venstre , højre - k ); stoogesort ( item , venstre + k , højre ); stoogesort ( item , venstre , højre - k ); }JavaScript-eksempel
funktion stoogesort ( emne , venstre , højre ) { if ( venstre === udefineret ) venstre = 0 ; hvis ( højre === udefineret ) højre = element . længde - 1 ; var tmp , k ; if ( item [ venstre ] > item [ højre ]) { tmp = item [ venstre ]; item [ venstre ] = vare [ højre ]; item [ højre ] = tmp ; } if (( venstre + 1 ) >= højre ) return ; k = Matematik . gulv (( højre - venstre + 1 ) / 3 ); stoogesort ( item , venstre , højre - k ); stoogesort ( item , venstre + k , højre ); stoogesort ( item , venstre , højre - k ); }Noter
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Pr. fra engelsk. udg. A. Shen. — M. : MTsNMO, 2000. — 960 s. - ISBN 5-900916-37-5 .
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Litteratur
- Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 7. Quicksort // Algoritmer: konstruktion og analyse = Introduktion til algoritmer. — 2. udgave. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
| Sorteringsalgoritmer | |
|---|---|
| Teori | Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern |
| Udveksling | |
| Valg | |
| indsætter | |
| fusion | |
| Ingen sammenligninger | |
| hybrid | |
| Andet | |
| upraktisk | |