 Visualización del tipo Stooge (solo muestra intercambios). | |
| Clase | Algoritmo de clasificación |
|---|---|
| Estructura de datos | Formación |
| Rendimiento en el peor de los casos | O ( n log 3 / log 1,5 ) |
| Complejidad espacial en el peor de los casos | O ( n ) |
Stooge sort es un algoritmo de clasificación recursivo . Es notable por su complejidad de tiempo excepcionalmente mala de O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ) . Por lo tanto, el tiempo de ejecución del algoritmo es más lento en comparación con los algoritmos de clasificación razonables, y es más lento que el tipo de burbuja , un ejemplo canónico de un tipo bastante ineficiente. Sin embargo, es más eficiente que Slowsort . El nombre proviene de The Three Stooges . [1]
El algoritmo se define de la siguiente manera:
- Si el valor al principio es mayor que el valor al final, cámbielos.
- Si hay 3 o más elementos en la lista, entonces:
- Stooge ordena los 2/3 iniciales de la lista
- Stooge ordena los 2/3 finales de la lista
- Stooge vuelve a ordenar los 2/3 iniciales de la lista
Es importante obtener el tamaño de clasificación de enteros utilizado en las llamadas recursivas redondeando 2/3 hacia arriba , por ejemplo, redondeando 2/3 de 5 debería dar 4 en lugar de 3, ya que de lo contrario la clasificación puede fallar en ciertos datos.
Implementación
función stoogesort ( matriz L , i = 0 , j = longitud ( L ) - 1 ) { si L [ i ] > L [ j ] entonces // Si el elemento más a la izquierda es más grande que el elemento más a la derecha L [ i ] ↔ L [ j ] // Intercambia el elemento más a la izquierda y el elemento más a la derecha si ( j - i + 1 ) > 2 then // Si hay al menos 3 elementos en la matriz t = floor (( j - i + 1 ) / 3 ) stoogesort ( L , i , j - t ) // Clasifica los primeros 2/3 de la matriz stoogesort ( L , i + t , j ) // Clasifica los últimos 2/3 de la matriz stoogesort ( L , i , j - t ) // Clasifica los primeros 2/3 de la matriz de nuevo volver L }Referencias
- ^ "CSE 373" (PDF) . cursos.cs.washington.edu . Consultado el 14 de septiembre de 2020 .
- ^ "Clasificación lenta: tipo Stooge y tipo Bogo" . YouTube . udiprod.
Fuentes
- Negro, Paul E. "tipo títere" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Consultado el 18 de junio de 2011 .
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "Problema 7-3". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 161-162. ISBN 0-262-03293-7.
Enlaces externos
- Algoritmos de clasificación (incluida la clasificación Stooge)
- Clasificación de Stooge: implementación y comparación
 | Este artículo de ciencias de la computación es un fragmento . Puedes ayudar a Wikipedia expandiéndolo . |
