bogosort

En informática , bogosort ^[1]^[2] (también conocido como ordenación por permutación y ordenación estúpida ^[3] ) es un algoritmo de clasificación basado en el paradigma de generación y prueba . La función genera sucesivamente permutaciones de su entrada hasta que encuentra una que esté ordenada. No se considera útil para ordenar, pero puede usarse con fines educativos, para contrastarlo con algoritmos más eficientes.

Existen dos versiones de este algoritmo: una versión determinista que enumera todas las permutaciones hasta encontrar 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. En el peor de los casos con esta versión, la fuente aleatoria es de baja calidad y hace que la permutación ordenada sea ilimitadamente improbable. El nombre del algoritmo es un acrónimo de las palabras falso y ordenar . ^[5]

Descripción del algoritmo

Pseudocódigo

La siguiente es una descripción del algoritmo aleatorio en pseudocódigo :

mientras no está ordenado (mazo): barajar (mazo)

do

Aquí hay una implementación en C:

#incluir <stdio.h> #incluir <stdlib.h> #incluir <hora.h> // ejecuta bogo sort in situ en una matriz determinadabogo_sort vacío estático ( int * a , tamaño int );     // devuelve 1 si la matriz dada está ordenada y 0 en caso contrariostatic int is_sorted ( int * a , int tamaño );     // baraja la matriz dada en un orden aleatoriobarajado vacío estático ( int * a , int tamaño );     void bogo_sort ( int * a , int tamaño ) {      mientras ( ! está_ordenado ( a , tamaño )) {    barajar ( a , tamaño );  }}int is_sorted ( int * a , int tamaño ) {      para ( int i = 0 ; i < tamaño -1 ; i ++ ) {          si ( a [ i ] > a [ i + 1 ]) {     devolver 0 ;  } } devolver 1 ; }barajar vacío ( int * a , tamaño int ) {      int temp , aleatorio ;   para ( int i = 0 ; i < tamaño ; i ++ ) {          aleatorio = ( int ) (( doble ) rand () / (( doble ) RAND_MAX + 1 ) * tamaño );            temperatura = a [ aleatorio ];   a [ aleatorio ] = a [ i ];   a [ i ] = temperatura ;   }}int principal () {   // ejemplo de uso entrada int [ ] = { 68 , 14 , 78 , 98 , 67 , 89 , 45 , 90 , 87 , 78 , 65 , 74 };                 int tamaño = tamaño de ( entrada ) / tamaño de ( * entrada );      // inicializa el generador de números pseudoaleatorios srand ( hora ( NULL )); bogo_sort ( entrada , tamaño );  // resultado ordenado: 14 45 65 67 68 74 78 78 87 89 90 98 printf ( "resultado ordenado:" ); para ( int i = 0 ; i < tamaño ; i ++ ) {          printf ( "%d" , entrada [ i ]);  } printf ( " \n " ); devolver 0 ; }

Pitón

Aquí está el pseudocódigo anterior reescrito en Python 3 :

importar  aleatoriamente# bogosort # lo que sucede es que hay una matriz aleatoria generada por la última función # la primera función verifica si la matriz está ordenada o no # la segunda función baraja repetidamente la matriz mientras permanezca sin ordenar # y eso es todo # codificación feliz =># esta función verifica si la matriz está ordenada o no def  is_sorted ( array_aleatorio ):  para  i  en  el rango ( 1 ,  len ( array_aleatorio )):  if  matriz_aleatoria [ i ]  <  matriz_aleatoria [ i  -  1 ]:  return  False  return  True# esta función mezcla repetidamente los elementos de la matriz hasta que estén ordenados def  bogo_sort ( array_aleatorio ):  mientras que  no  is_sorted ( array_aleatorio ):  aleatorio . barajar ( array_array )  devolver  matriz_aleatoria# esta función genera una matriz con valores enteros elegidos aleatoriamente def  generate_random_array ( tamaño ,  min_val ,  max_val ):  return  [ aleatorio . randint ( min_val ,  max_val )  para  _  dentro del  rango ( tamaño )]# el tamaño, valor mínimo y valor máximo de la matriz generada aleatoriamente size  =  10 min_val  =  1 max_val  =  100 random_array  =  generate_random_array ( size ,  min_val ,  max_val ) print ( "Matriz sin clasificar:" ,  random_array ) sorted_arr  =  bogo_sort ( random_array ) print ( "Matriz ordenada:" ,  sorted_arr )

Este código supone que datase trata de una estructura de datos simple, mutable y similar a una matriz, como la incorporada en Python, listcuyos elementos se pueden comparar sin problemas.

Duración y terminación

Tiempo de ejecución experimental de bogosort

Si todos los elementos a ordenar son distintos, el número esperado de comparaciones realizadas en el caso promedio mediante 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 solo 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 que al lanzar una moneda al aire puede salir cara cualquier número de veces seguidas.

El mejor caso ocurre si la lista proporcionada 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 : existe cierta probabilidad de obtener la permutación correcta, por lo que, dado un número ilimitado de intentos, es casi seguro que eventualmente lo hará. ser elegido.

Algoritmos relacionados

Gorosort: Un algoritmo de clasificación introducido en Google Code Jam de 2011 . ^[6] Mientras la lista no esté en orden, un subconjunto de todos los elementos se permuta aleatoriamente. Si este subconjunto se elige de manera óptima cada vez que se realiza, el valor esperado del número total de veces que es necesario realizar esta operación es igual al número de elementos mal colocados.
Bogobogosort: Un algoritmo que se llama a sí mismo de forma recursiva con copias cada vez más pequeñas del comienzo de la lista para ver si están ordenadas. El caso base es un elemento único, que siempre está ordenado. Para otros casos, compara el último elemento con el elemento máximo de los elementos anteriores de la lista. Si el último elemento es mayor o igual, verifica si el orden de la copia coincide con la versión anterior y, de ser así, regresa. De lo contrario, reorganiza la copia actual de la lista y reinicia su verificación recursiva. ^[7]
bozosort: Otro algoritmo de clasificación basado en números aleatorios. Si la lista no está en orden, selecciona 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 se encuentran algunas estimaciones en el análisis de H. Gruber de algoritmos de clasificación aleatorios "perversamente horribles". ^{[1] Se encuentra que} $O(n!)$ es el caso promedio esperado.
Peor tipo: Un algoritmo de clasificación pesimal que se garantiza que se completará en un tiempo finito; sin embargo, su eficiencia puede ser arbitrariamente mala, dependiendo de su configuración. 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 a ordenar, y $k$ , que es la 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 temporal de badsort es $O(n 2)$ si $k = 0$ . Sin embargo, para cualquier $k > 0$ , $badsort(L, k)$ primero genera $P$ , la lista de todas las permutaciones de $L$ . Luego, $badsort$ calcula $badsort(P, k - 1)$ y devuelve el primer elemento del $P$ ordenado . Para hacer que $el peor tipo$ sea verdaderamente pesimal, $k$ puede asignarse al valor de una función creciente computable como (por ejemplo, $f$ $($ $n$ $) =$ $A$ $($ $n$ $,$ $n$ $)$ , donde $A$ es la función de Ackermann ). Por lo tanto, para ordenar una lista arbitrariamente mal, se ejecutaría $peor sort($ $L$ $,$ $f$ $) = badsort($ $L$ $,$ $f$ $(length($ $L$ $)))$ , donde $length($ $L$ $)$ es el número de elementos en $L$ . El algoritmo resultante tiene complejidad , donde = factorial de $n$ iterados $m$ veces. Este algoritmo puede volverse tan ineficiente como se desee eligiendo una función $f$ de crecimiento suficientemente rápido . ^[8] $f\colon \mathbb {N} \to \mathbb {N}$ ${\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}$ $n!^{(m)}=(\dotso ((n!)!)!\dotso )!$
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: Un algoritmo de clasificación hipotético basado en bogosort, creado como una broma entre informáticos. El algoritmo genera una permutación aleatoria de su entrada utilizando una fuente cuántica de entropía, verifica si la lista está ordenada y, si no lo está, destruye el universo. Suponiendo que se mantenga la interpretación de muchos mundos , el uso de este algoritmo dará como resultado al menos un universo sobreviviente donde la entrada se clasificó exitosamente en tiempo $O(n) .$ ^[9]
tipo milagroso: Un algoritmo de clasificación que comprueba si la matriz está ordenada hasta que ocurre un milagro . Comprueba continuamente la matriz hasta que esté ordenada, sin cambiar nunca el orden de la matriz. ^[10] Debido a que el orden nunca se altera, el algoritmo tiene una complejidad temporal hipotética de $O (\infty)$ , pero aún puede clasificar eventos como milagros o trastornos de un solo evento . Se debe tener especial cuidado en la implementación de este algoritmo, ya que la optimización de los compiladores puede simplemente transformarlo en un bucle while (verdadero) . Sin embargo, el mejor caso es $O (n)$ , que ocurre en una lista ordenada. Dado que sólo hace comparaciones, está estrictamente en el lugar y es estable.
tipo bozobogo: Un algoritmo de clasificación que solo funciona si la lista ya está en orden; de lo contrario, se aplican las condiciones de clasificación milagrosa.

Ver también

Referencias

^ abcdefGruber , H.; Holzer, M.; Ruepp, O. (2007), "Clasificación de forma lenta: un análisis de algoritmos de clasificación aleatorios perversamente horribles", 4ª Conferencia Internacional sobre Diversión con Algoritmos, Castiglioncello, Italia, 2007 (PDF) , Lecture Notes in Computer Science, vol. 4475, Springer-Verlag, págs. 183-197, doi :10.1007/978-3-540-72914-3_17, ISBN 978-3-540-72913-6.
^ ab Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), "Transformadores de mónadas de retroceso, entrelazado 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. "bogo-ordenar". El diccionario del nuevo hacker . Prensa del MIT, 1996.
^ Naish, Lee (1986), "Negación y cuantificadores en NU-Prolog", Actas de la Tercera Conferencia Internacional sobre Programación Lógica , Lecture Notes in Computer Science , vol. 225, Springer-Verlag, págs. 624–634, doi :10.1007/3-540-16492-8_111, ISBN 978-3-540-16492-0.
^ "bogosort". xlinux.nist.gov . Consultado el 11 de noviembre de 2020 .
^ Google Code Jam 2011, rondas de clasificación, problema D
^ Bogobogosort
↑ Lerma, Miguel A. (2014). "¿Qué tan ineficiente puede ser un algoritmo de clasificación?". arXiv : 1406.1077 [cs.DS].
^ El otro árbol (23 de octubre de 2009). "Bogosort cuántico" (PDF) . MatemáticasNOTICIAS . 111 (3): 13. Archivado (PDF) desde el original el 5 de julio de 2020 . Consultado el 20 de marzo de 2022 .
^ "Clasificación milagrosa". El manual de informática . Consultado el 9 de septiembre de 2022 .

Enlaces externos

La implementación del algoritmo Wikibook tiene una página sobre el tema: Bogosort

BogoOrt en WikiWikiWeb
Algoritmos de clasificación ineficientes
Bogosort: una implementación que se ejecuta en sistemas tipo 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