Tipo de títere
Stooge sort (Clasificación por partes [1] , Wandering sort [2] ) es un algoritmo de clasificación recursivo con complejidad temporal . El tiempo de ejecución del algoritmo es, por lo tanto, extremadamente largo en comparación con los algoritmos de clasificación eficientes como Merge Sort .
El algoritmo para ordenar una lista de elementos es el siguiente:
- Si el valor del elemento al final de la lista es menor que el valor del elemento al principio, cámbielos.
- Si hay 3 o más elementos en el subconjunto actual de la lista, entonces:
- Llame recursivamente a la clasificación de Stooge en los primeros 2/3 de la lista
- Llame recursivamente a la clasificación de Stooge en los últimos 2/3 de la lista
- Llame recursivamente a Stooge sort en los primeros 2/3 de la lista nuevamente
- más: volver
Ejemplos de implementación
algoritmo stoogesort ( matriz L , i = 0 , j = longitud ( L ) - 1 ) si L [ j ] < L [ i ] entonces L [ i ] ↔ L [ j ] si j - i > 1 entonces t = ( j - i + 1 ) / 3 stoogesort ( L , i , j - t ) stoogesort ( L , i + t , j ) stoogesort ( L , i , j - t ) return LEjemplo en C
void stoogesort ( int * elemento , int izquierda , int derecha ) { registro int tmp , k ; if ( elemento [ izquierda ] > elemento [ derecha ]) { tmp = artículo [ izquierda ]; artículo [ izquierda ] = artículo [ derecha ]; artículo [ derecha ] = tmp ; } si (( izquierda + 1 ) >= derecha ) volver ; k = ( int )(( derecha - izquierda + 1 ) / 3 ); Stoogesort ( elemento , izquierda , derecha - k ); stoogesort ( elemento , izquierda + k , derecha ); Stoogesort ( elemento , izquierda , derecha - k ); }Ejemplo de JavaScript
función stoogesort ( elemento , izquierda , derecha ) { if ( izquierda === indefinido ) izquierda = 0 ; if ( derecho === indefinido ) derecho = artículo . longitud - 1 ; var tmp , k ; if ( elemento [ izquierda ] > elemento [ derecha ]) { tmp = elemento [ izquierda ]; artículo [ izquierda ] = artículo [ derecha ]; artículo [ derecha ] = tmp ; } if (( izquierda + 1 ) >= derecha ) return ; k = Matemáticas . piso (( derecha - izquierda + 1 ) / 3 ); Stoogesort ( elemento , izquierda , derecha - k ); stoogesort ( elemento , izquierda + k , derecha ); Stoogesort ( elemento , izquierda , derecha - k ); }Notas
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. Algorithms: construcción y análisis = Introducción a los algoritmos / Per. De inglés. edición A. Shen. — M. : MTsNMO, 2000. — 960 p. - ISBN 5-900916-37-5 .
- ↑ Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
Literatura
- Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capítulo 7. Quicksort // Algoritmos: construcción y análisis = Introducción a los Algoritmos. — 2ª edición. - M. : "Williams" , 2005. - ISBN 5-8459-0857-4 .
| Algoritmos de clasificación | |
|---|---|
| Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
| Intercambio | |
| Elección | |
| inserciones | |
| fusión | |
| sin comparaciones | |
| híbrido | |
| Otro | |
| poco práctico | |