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.
Algoritmos de clasificación | |
---|---|
Teoría | Complejidad O notación relación de orden Ordenar tipos sostenible Interno Externo |
Intercambio | |
Elección | |
inserciones | |
fusión | |
sin comparaciones | |
híbrido | |
Otro | |
poco práctico |