Bogosort

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de mayo de 2021; las comprobaciones requieren 5 ediciones .

Bogosort  (de Amer. comp. slang. bogus - inoperable, no funcional, inútil) es un algoritmo de clasificación ineficiente que se usa solo con fines educativos y se opone a otros algoritmos más realistas.

Si se usa bogosort para clasificar una baraja de cartas , entonces primero en el algoritmo debe verificar si todas las cartas están en orden, y si no lo están, luego barájelas aleatoriamente, verifique si todas las cartas están ahora en orden, y repita el proceso hasta que la baraja esté ordenada.

Tiempo medio de ejecución del algoritmo.

Al iterar a través del ciclo una vez por segundo, la clasificación de la siguiente cantidad de elementos puede tomar, en promedio:

Número de elementos una 2 3 cuatro 5 6 7 ocho 9 diez once 12
Tiempo promedio 1 s 4 segundos 18s 96 segundos 10 minutos 1,2 horas 9,8 horas 3,7 días 37,8 días 1,15 años 13,9 años 182 años

Con un procesador de 4 núcleos funcionando a 2,4 GHz (9600 millones de operaciones por segundo):

Número de elementos diez once 12 13 catorce quince dieciséis 17 Dieciocho 19 veinte
Tiempo promedio 0,0037 s 0,045 s 0,59 s 8,4 s 2,1 minutos 33,6 minutos 9,7 horas 7,29 días 139 días 7,6 años 160 años

Una computadora ordenará una baraja de 32 cartas en promedio 2.7⋅10 19  años.

Ejemplo de implementación

#incluir <utilidad> bool correcto ( int * arr , tamaño int ) { mientras ( -- tamaño > 0 ) if ( arr [ tamaño - 1 ] > arr [ tamaño ]) devolver verdadero ; devolver falso ; } barajar vacío ( int * arr , tamaño int ) { para ( int i = 0 ; i < tamaño ; ++ i ) std :: swap ( arr [ i ], arr [( rand () % tamaño )]); } void bogoSort ( int * arr , tamaño int ) { while ( correcto ( arr , tamaño )) barajar ( arr , tamaño ); }

Véase también

Enlaces