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]

Con una Stupid Sort, una sola mezcla puede bastar para clasificar los elementos. Sin embargo, esta probabilidad es muy baja.

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 ${\displaystyle (e-1)n!}$, y el número esperado de intercambios (swaps) en el caso promedio es igual a ${\displaystyle (n-1)n!}$.

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 ${\displaystyle n-1}$ comparaciones y ningún intercambio.

Véase también

• Algoritmo de ordenamiento