Stooge fajta
A Stooge rendezés (Részek szerinti rendezés [1] , Vándorrendezés [2] ) egy rekurzív rendezési algoritmus időbonyolultsággal . Az algoritmus futási ideje így rendkívül hosszú az olyan hatékony rendezési algoritmusokhoz képest, mint a Merge Sort .
Az elemlista rendezésének algoritmusa a következő:
- Ha a lista végén lévő elem értéke kisebb, mint az elején lévő elem értéke, akkor cserélje fel őket.
- Ha 3 vagy több elem van a lista aktuális részhalmazában, akkor:
- Rekurzívan hívja a Stooge sort a lista első 2/3-án
- Rekurzívan hívja a Stooge sort a lista utolsó 2/3-án
- Rekurzívan hívja újra a Stooge sort a lista első 2/3-án
- Egyéb: vissza
Megvalósítási példák
stoogesort algoritmus ( L tömb , i = 0 , j = hosszúság ( L ) - 1 ) ha L [ j ] < L [ i ] akkor L [ i ] ↔ L [ j ] ha j - i > 1 akkor t = ( j ) i + 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _Példa a C-ben
void stoogesort ( int * elem , int balra , int jobbra ) { regiszter int tmp , k ; if ( elem [ balra ] > elem [ jobbra ]) { tmp = elem [ balra ]; item [ left ] = item [ right ]; item [ jobbra ] = tmp ; } if (( bal + 1 ) >= jobb ) visszatérés ; k = ( int )(( jobb - bal + 1 ) / 3 ); stoogesort ( elem , bal , jobb - k ); stoogesort ( elem , bal + k , jobb ); stoogesort ( elem , bal , jobb - k ); }JavaScript példa
function stoogesort ( item , left , right ) { if ( left === undefined ) left = 0 ; if ( jobb === undefined ) right = item . hossza - 1 ; var tmp , k ; if ( item [ left ] > item [ right ]) { tmp = item [ left ]; item [ left ] = item [ right ]; item [ jobbra ] = tmp ; } if (( bal + 1 ) >= jobb ) return ; k = matematika . emelet (( jobb - bal + 1 ) / 3 ); stoogesort ( elem , bal , jobb - k ); stoogesort ( elem , bal + k , jobb ); stoogesort ( elem , bal , jobb - k ); }Jegyzetek
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. Algoritmusok: konstrukció és elemzés = Introduction to Algorithms / Per. angolról. szerk. A. Shen. — M. : MTsNMO, 2000. — 960 p. - ISBN 5-900916-37-5 .
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Szerk. I. V. Krasikova. - 2. kiadás - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
Irodalom
- Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 7. fejezet Gyors rendezés // Algoritmusok: szerkesztés és elemzés = Bevezetés az algoritmusokba. — 2. kiadás. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
| Rendezési algoritmusok | |
|---|---|
| Elmélet | Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső |
| Csere | |
| Választás | |
| Betétek | |
| egyesülés | |
| Nincs összehasonlítás | |
| hibrid | |
| Egyéb | |
| nem praktikus | |