En informática , bogosort [1] [2] (también conocido como tipo de permutación , tipo estúpido , [3] o clasificación lenta [4] ) es un algoritmo de clasificación altamente ineficiente basado en el paradigma de generar y probar . La función genera sucesivamente permutaciones de su entrada hasta que encuentra una que está ordenada. No es útil para ordenar, pero puede usarse con fines educativos, para contrastarlo con algoritmos más eficientes.
Clase | Clasificación |
---|---|
Estructura de datos | Formación |
Rendimiento en el peor de los casos | Unbounded (versión aleatoria), O (( n +1)!) (Versión determinista) |
Rendimiento en el mejor de los casos | O ( n ) [1] |
Rendimiento medio | O (( n +1)!) [1] |
Complejidad espacial en el peor de los casos | O ( 1 ) |
Existen dos versiones de este algoritmo: una versión determinista que enumera todas las permutaciones hasta que llega a una ordenada, [2] [4] y una versión aleatoria que permuta aleatoriamente su entrada. Una analogía para el funcionamiento de la última versión es clasificar una baraja de cartas lanzándola al aire, recogiendo las cartas al azar y repitiendo el proceso hasta que se clasifique la baraja. Su nombre es un acrónimo de las palabras falso y especie . [5]
Descripción del algoritmo
La siguiente es una descripción del algoritmo aleatorio en pseudocódigo :
mientras que no isInOrder (cubierta): shuffle (mazo)
Pitón
Aquí está el pseudocódigo anterior reescrito en Python 3 :
de importación aleatoria aleatoria def is_sorted ( data ) -> bool : "" "Determina si los datos están ordenados." "" return all ( data [ i ] <= data [ i + 1 ] for i in range ( len ( data ) - 1 ))def bogosort ( datos ) -> lista : "" "Shuffle data hasta que se clasifiquen." "" mientras no está_sorted ( data ): shuffle ( data ) return data
Este código asume que los datos son un tipo de datos simple y mutable, como el integrado de Python, list
cuyos elementos se pueden comparar sin problemas.
ML estándar
Aquí hay una implementación en ML estándar :
fun rand a = Word . toInt ( MLton . Random . rand {}) mod 2 = 0 ;fun shuffle xs = Lista . revAppend ( Lista . partición rand xs );fun bogosort cmp = dejar divertido ordenado ( x :: y :: xs ) = cmp ( x , y ) y también ordenado ( y :: xs ) | ordenado _ = verdadero ; fun sort xs = si se ordena xs entonces xs else sort ( barajar xs ); en fin de especie ;
Duración y rescisión
Si todos los elementos que se van a clasificar son distintos, el número esperado de comparaciones realizadas en el caso promedio por bogosort aleatorio es asintóticamente equivalente a ( e - 1) n ! , y el número esperado de swaps en el caso promedio es igual a ( n - 1) n ! . [1] El número esperado de intercambios crece más rápido que el número esperado de comparaciones, porque si los elementos no están en orden, esto generalmente se descubrirá después de unas pocas comparaciones, sin importar cuántos elementos haya; pero el trabajo de barajar la colección es proporcional a su tamaño. En el peor de los casos, el número de comparaciones e intercambios es ilimitado, por la misma razón por la que una moneda lanzada al aire puede dar la cara cualquier número de veces seguidas.
El mejor caso ocurre si la lista dada ya está ordenada; en este caso, el número esperado de comparaciones es n - 1 y no se realiza ningún intercambio. [1]
Para cualquier colección de tamaño fijo, el tiempo de ejecución esperado del algoritmo es finito por la misma razón que se cumple el teorema del mono infinito : hay alguna probabilidad de obtener la permutación correcta, por lo que dado un número ilimitado de intentos, es casi seguro que eventualmente ser elegido.
Algoritmos relacionados
- Gorosort
- es un algoritmo de clasificación introducido en Google Code Jam de 2011 . [6] Siempre que la lista no esté en orden, se permuta aleatoriamente un subconjunto de todos los elementos. Si este subconjunto se elige de manera óptima cada vez que se realiza, el valor esperado del número total de veces que se debe realizar esta operación es igual al número de elementos fuera de lugar.
- Bogobogosort
- es un algoritmo que fue diseñado para no tener éxito antes de la muerte por calor del universo en cualquier lista considerable. Funciona llamándose a sí mismo de forma recursiva con copias cada vez más pequeñas del principio de la lista para ver si están ordenadas. El caso base es un solo elemento, que siempre está ordenado. Para otros casos, compara el último elemento con el elemento máximo de los elementos anteriores en la lista. Si el último elemento es mayor o igual, comprueba si el orden de la copia coincide con la versión anterior y, si es así, regresa. De lo contrario, reorganiza la copia actual de la lista y reinicia su verificación recursiva. [7]
- Bozosort
- es otro algoritmo de clasificación basado en números aleatorios. Si la lista no está en orden, elige dos elementos al azar y los intercambia, luego verifica si la lista está ordenada. El análisis del tiempo de ejecución de un bozosort es más difícil, pero algunas estimaciones se encuentran en el análisis de H. Gruber de los algoritmos de clasificación aleatoria "perversamente horribles". [1] Se encuentra que O ( n !) Es el caso promedio esperado.
- Worstsort
- es un algoritmo de clasificación pesimal [a] que se garantiza que se completará en un tiempo finito; sin embargo, no existe un límite computable para la ineficacia del algoritmo de clasificación y, por lo tanto, es más pesimista que los otros algoritmos descritos en este documento. El algoritmo de peor clasificación se basa en un algoritmo de clasificación incorrecto, badsort . El algoritmo badsort acepta dos parámetros: L , que es la lista que se va a ordenar, yk , que es una profundidad de recursividad. En el nivel de recursividad k = 0 , badsort simplemente usa un algoritmo de clasificación común, como bubblesort , para ordenar sus entradas y devolver la lista ordenada. Es decir, badsort ( L , 0) = bubblesort ( L ) . Por lo tanto, la complejidad del tiempo de badsort es O ( n 2 ) si k = 0 . Sin embargo, para cualquier k > 0 , badsort ( L , k ) genera primero P , la lista de todas las permutaciones de L . Luego, badsort calcula badsort ( P , k - 1) y devuelve el primer elemento de la P ordenada . Para hacer que el peor ordenamiento sea verdaderamente pesimal, se puede asignar k al valor de una función creciente computable como (por ejemplo, f ( n ) = A ( n , n ) , donde A es la función de Ackermann ). Ergo, para ordenar una lista arbitraria mal, tienes que ejecutar worstsort ( L , f ) = badsort ( L , f (longitud ( L ))) , donde la longitud ( L ) es el número de elementos en L . El algoritmo resultante tiene complejidad , dónde = factorial de n iterado m veces. Este algoritmo se puede hacer tan ineficiente como queramos eligiendo una función f de crecimiento lo suficientemente rápido . [8]
- Clasificación lenta
- Un algoritmo de clasificación humorístico diferente que emplea una estrategia equivocada de divide y vencerás para lograr una complejidad masiva.
Bogosort cuántico
Quantum bogosort es un algoritmo de clasificación hipotético basado en bogosort, creado como una broma entre los científicos informáticos. El algoritmo genera una permutación aleatoria de su entrada, verifica si la lista está ordenada y, si no lo está, destruye el universo. Suponiendo que la interpretación de muchos mundos sea cierta, el uso de este algoritmo dará como resultado la existencia de exactamente un universo superviviente donde la entrada se clasifica con éxito. [ cita requerida ]
Ver también
Notas
- ^ Lo contrario de "óptimo"
Referencias
- ↑ a b c d e f Gruber, H .; Holzer, M .; Ruepp, O., "Sorting the slow way: an analysis of perversamente horribles algoritmos de ordenación aleatorios", 4ta Conferencia Internacional sobre Diversión con Algoritmos, Castiglioncello, Italia, 2007 (PDF) , Lecture Notes in Computer Science, 4475 , Springer-Verlag, págs. 183–197, doi : 10.1007 / 978-3-540-72914-3_17.
- ^ a b Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P .; Sabry, Amr (2005), "Transformadores de mónada de retroceso, intercalación y terminación: (perla funcional)", Actas de la Décima Conferencia Internacional ACM SIGPLAN sobre Programación Funcional (ICFP '05) (PDF) , Avisos SIGPLAN, págs. 192– 203, doi : 10.1145 / 1086365.1086390 , S2CID 1435535 , archivado desde el original (PDF) el 26 de marzo de 2012 , consultado el 22 de junio de 2011
- ^ ES Raymond. "especie bogo". El diccionario del nuevo hacker . Prensa del MIT, 1996.
- ^ a b Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Actas de la Tercera Conferencia Internacional sobre Programación Lógica , Lecture Notes in Computer Science , 225 , Springer-Verlag, págs. 624–634, doi : 10.1007 / 3 -540-16492-8_111.
- ^ "bogosort" . xlinux.nist.gov . Consultado el 11 de noviembre de 2020 .
- ^ Google Code Jam 2011, rondas de calificación, problema D
- ^ Bogobogosort
- ^ Lerma, Miguel A. (2014). "¿Qué tan ineficiente puede ser un algoritmo de clasificación?". arXiv : 1406.1077 [ cs.DS ].
enlaces externos
- BogoSort en WikiWikiWeb
- Algoritmos de ordenación ineficaces
- Bogosort : una implementación que se ejecuta en sistemas similares a Unix, similar al programa de clasificación estándar .
- Bogosort y jmmcg :: bogosort [ enlace muerto permanente ] : implementaciones C ++ simples, pero perversas, del algoritmo bogosort.
- Paquete Bogosort NPM : implementación de bogosort para el ecosistema Node.js.
- Max Sherman Bogo-sort es algo lento , junio de 2013