Stupid sort
Stupid Sort, en inglés también conocido como BogoSort[1][2] (o como slowsort[3][4]), es un algoritmo de ordenamiento particularmente inefectivo basado en el paradigma de ensayo y error. No es útil para ordenar, pero puede ser utilizado con propósitos educativos para contrastarlo con algoritmos más efectivos. También ha sido usado como ejemplo en programación lógica.[2][3][4]
Si stupid sort fuera utilizado para ordenar un mazo de cartas, consistiría en verificar primero si el mazo está en orden, y si no lo está, entonces deberíamos mezclar las cartas de forma aleatoria, verificar de nuevo si están ordenadas y así sucesivamente hasta que por una mezcla al azar encontremos el mazo ordenado. El nombre bogosort proviene de la palabra bogus.[5]
Complejidad y finalización
Este algoritmo de ordenamiento es probabilístico por naturaleza. Si se aplica a un arreglo donde todos los elementos son distintos, el número esperado de comparaciones es asintóticamente equivalente a , y el número esperado de intercambios (swaps) en el caso promedio es igual a .
En el peor caso el número de comparaciones e intercambios no está acotada. Es decir, no hay certeza de que el algoritmo termine. El mejor caso es cuando la lista original está ordenada, entonces se realizan comparaciones y ningún intercambio.