Bogosort

En informática , bogosort ^[1]^[2] (también conocido como ordenamiento por permutación y ordenamiento estúpido ^[3] ) es un algoritmo de ordenamiento 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 se considera útil para el ordenamiento, 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 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 ordenar una baraja de cartas lanzándola al aire, recogiendo las cartas al azar y repitiendo el proceso hasta que la baraja esté ordenada. 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 de ocurrir. El nombre del algoritmo es una combinación de las palabras bogus y sort . ^[5]

Descripción del algoritmo

Pseudocódigo

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

mientras no esté ordenado(baraja): barajar (baraja)

do

Aquí hay una implementación en C:

#incluir <stdio.h> #incluir <stdlib.h> #include <tiempo.h> // ejecuta una ordenación bogo en el lugar en una matriz dadavoid estático bogo_sort ( int * a , int tamaño );     // devuelve 1 si la matriz dada está ordenada y 0 en caso contrarioint estático is_sorted ( int * a , int tamaño );     // baraja la matriz dada en un orden aleatoriovoid estático shuffle ( int * a , int tamaño );     void bogo_sort ( int * a , int tamaño ) {      mientras ( ! is_sorted ( 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 ]) {     devuelve 0 ;  } } devuelve 1 ; }void shuffle ( int * a , int tamaño ) {      int temp , aleatorio ;   para ( int i = 0 ; i < tamaño ; i ++ ) {          aleatorio = ( int ) (( doble ) rand () / (( doble ) RAND_MAX + 1 ) * tamaño );            temp = a [ aleatorio ];   a [ aleatorio ] = a [ i ];   a [ i ] = temperatura ;   }}int principal () {   // ejemplo de uso int entrada [] = { 68 , 14 , 78 , 98 , 67 , 89 , 45 , 90 , 87 , 78 , 65 , 74 };                 int tamaño = tamañode ( entrada ) / tamañode ( * entrada );      // inicializar generador de números pseudoaleatorios srand ( tiempo ( 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 " ); devuelve 0 ; }

Pitón

Aquí está el código Python anterior escrito en Python 3 :

importar  aleatorio# 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 la matriz repetidamente mientras permanezca sin ordenar # y eso es todo # feliz codificación =># esta función verifica si la matriz está ordenada o no def  is_sorted ( random_array ):  for  i  in  range ( 1 ,  len ( random_array )):  if  random_array [ i ]  <  random_array [ i  -  1 ]:  return  False  return  True# esta función baraja repetidamente los elementos de la matriz hasta que estén ordenados def  bogo_sort ( random_array ):  while  not  is_sorted ( random_array ):  random . shuffle ( random_array )  return  random_array# esta función genera una matriz con valores enteros elegidos aleatoriamente def  generate_random_array ( size ,  min_val ,  max_val ):  return  [ random . randint ( min_val ,  max_val )  for  _  in  range ( size )]# el tamaño, el valor mínimo y el 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 ordenar:" ,  random_array ) sorted_arr  =  bogo_sort ( random_array ) print ( "Matriz ordenada:" ,  sorted_arr )

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

Duración y terminación

Tiempo de ejecución experimental de bogosort

Si todos los elementos que se van a ordenar 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 intercambios 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 son ilimitados, por la misma razón que una moneda lanzada al aire puede dar 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 realizan intercambios en absoluto. ^[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 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 finalmente se elegirá.

Algoritmos relacionados

Gorosort: Un algoritmo de ordenamiento introducido en el Google Code Jam de 2011. ^[6] Mientras la lista no esté ordenada, se permuta aleatoriamente un subconjunto de todos los elementos. Si este subconjunto se elige de forma óptima cada vez que se realiza esta operación, el valor esperado del número total de veces que se debe realizar esta operación es igual al número de elementos mal ubicados.
Bogobogosort: Un algoritmo que recursivamente se llama a sí mismo con copias cada vez más pequeñas del comienzo 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, verifica si el orden de la copia coincide con la versión anterior y, de ser así, retorna. De lo contrario, reorganiza la copia actual de la lista y reinicia su verificación recursiva. ^[7]
Sorteo de bozo: Otro algoritmo de ordenación basado en números aleatorios. Si la lista no está ordenada, 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 se encuentran algunas estimaciones en el análisis de H. Gruber de algoritmos de ordenación aleatorios "perversamente horribles". ^{[1] Se encuentra que} $O(n!)$ es el caso promedio esperado.
Peor clasificación: Un algoritmo de ordenamiento pesimista 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 $worstsort$ se basa en un algoritmo de ordenamiento malo, $badsort$ . El algoritmo badsort acepta dos parámetros: $L$ , que es la lista que se va a ordenar, y $k$ , que es una profundidad de recursión. En el nivel de recursión $k = 0$ , $badsort$ simplemente utiliza un algoritmo de ordenamiento 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 de la $P$ ordenada . Para que $worstsort$ sea verdaderamente pésimo, $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 $worstsort($ $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$ iterado $m$ veces. Este algoritmo puede hacerse tan ineficiente como se desee eligiendo una función $f$ con un crecimiento lo 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 )!$
Ordenación lenta: Un algoritmo de clasificación humorístico diferente que emplea una estrategia equivocada de dividir y vencer para lograr una complejidad masiva.
Sorteo cuántico: Un algoritmo de ordenamiento hipotético basado en bogosort, creado como una broma interna entre científicos 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 cumple la interpretación de los múltiples mundos , el uso de este algoritmo dará como resultado al menos un universo sobreviviente en el que la entrada se ordenó correctamente en tiempo $O(n)$ . ^[9]
Clasificación milagrosa: Un algoritmo de ordenació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 ordenar eventos como milagros o alteraciones de un solo evento . Se debe tener especial cuidado en la implementación de este algoritmo, ya que los compiladores optimizadores pueden simplemente transformarlo en un bucle while(true) . Sin embargo, el mejor caso es $O (n)$ , que ocurre en una lista ordenada. Dado que solo hace comparaciones, es estrictamente in situ y estable.
Clasificación de Bozobogo: Un algoritmo de ordenación que sólo funciona si la lista ya está ordenada, de lo contrario, se aplican las condiciones del ordenamiento milagroso.

Véase también

Referencias

^ abcdef Gruber, H.; Holzer, M.; Ruepp, O. (2007), "Ordenar de forma lenta: un análisis de algoritmos de ordenamiento aleatorio perversamente espantosos", 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), "Backtracking, interleaving, and terminating monad transformers: (functional pearl)", Actas de la Décima Conferencia Internacional ACM SIGPLAN sobre Programación Funcional (ICFP '05) (PDF) , SIGPLAN Notices, pp. 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-sort". El nuevo diccionario del hacker . MIT Press, 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
^ El lugar de Bogobogo
^ Lerma, Miguel A. (2014). "¿Qué tan ineficiente puede ser un algoritmo de ordenamiento?". arXiv : 1406.1077 [cs.DS].
^ The Other Tree (23 de octubre de 2009). «Bogosort cuántico» (PDF) . MathNEWS . 111 (3): 13. Archivado (PDF) del original el 5 de julio de 2020. Consultado el 20 de marzo de 2022 .
^ "Miracle Sort". Manual de informática . Consultado el 9 de septiembre de 2022 .

Enlaces externos

El Wikilibro Implementación de algoritmos tiene una página sobre el tema: Bogosort

BogoSort en WikiWikiWeb
Algoritmos de ordenamiento 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 en C++ simples, pero perversas, del algoritmo bogosort.
Paquete NPM Bogosort: implementación de bogosort para el ecosistema Node.js.
Max Sherman: la clasificación Bogo es algo lenta, junio de 2013