Tipo títere

Algoritmo de ordenamiento recursivo ineficiente

Stooge sort es un algoritmo de ordenamiento recursivo . Se destaca por su complejidad temporal excepcionalmente mala de = El tiempo de ejecución del algoritmo es, por lo tanto, más lento en comparación con los algoritmos de ordenamiento razonables, y es más lento que el bubble sort , un ejemplo canónico de un ordenamiento bastante ineficiente. Sin embargo, es más eficiente que Slowsort . El nombre proviene de Los tres chiflados . ^[1] ${\displaystyle O(n^{\log 3/\log 1.5})}$ ${\displaystyle O(n^{2.7095...})}$

El algoritmo se define de la siguiente manera:

• Si el valor inicial es mayor que el valor final, intercámbielos.
• Si hay tres o más elementos en la lista, entonces:
  • Stooge clasifica los 2/3 iniciales de la lista
  • Stooge clasifica los últimos 2/3 de la lista
  • Stooge vuelve a ordenar los 2/3 iniciales de la lista.

Es importante obtener el tamaño de clasificación entero utilizado en las llamadas recursivas redondeando 2/3 hacia arriba , por ejemplo, redondear 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

Pseudocódigo

 function stoogesort ( array L , i = 0 , j = length ( L ) -1 ){ if L [ i ] > L [ j ] then // Si el elemento más a la izquierda es más grande que el elemento más a la derecha swap ( L [ i ], L [ j ]) // Entonces intercámbialos if ( j - i + 1 ) > 2 then // Si hay al menos 3 elementos en el array t = floor (( j - i + 1 ) / 3 ) stoogesort ( L , i , j - t ) // Ordena los primeros 2/3 del array stoogesort ( L , i + t , j ) // Ordena los últimos 2/3 del array stoogesort ( L , i , j - t ) // Ordena nuevamente los primeros 2/3 del array return L }                                                  

Haskell

--No es el mejor, pero es igual al anterior.ordenación de objetos :: ( Ord a ) => [ a ] ​​-> [ a ] ​​ordenación de objetos [] = [] ordenación de objetos src = innerStoogesort src 0 (( longitud src ) - 1 )                   innerStoogesort :: ( Ord a ) => [ a ] ​​-> Int -> Int -> [ a ] ​​innerStoogesort src i j | ( j - i + 1 ) > 2 = src'''' | de lo contrario = src' donde src' = swap src i j -- necesita cada llamada 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 ] ​​swap src i j | a > b = replaceAt ( replaceAt src j a ) i b | de lo contrario = src donde a = src !! i b = src !! j                                           replaceAt :: [ a ] ​​-> Int -> a -> [ a ] ​​replaceAt ( x : xs ) índice valor | índice == 0 = valor : xs | de lo contrario = x : replaceAt xs ( índice - 1 ) valor                              

Referencias

1. "CSE 373" (PDF) . courses.cs.washington.edu . Consultado el 14 de septiembre de 2020 .

Fuentes

• Black, Paul E. "Stooge sort". 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 ordenamiento (incluido el ordenamiento Stooge)
• Stooge sort: implementación y comparación