Ir al contenido

Stupid sort

De Wikipedia, la enciclopedia libre
(Redirigido desde «Bogosort»)
Con una Stupid Sort, una sola mezcla puede bastar para clasificar los elementos. Sin embargo, esta probabilidad es muy baja.

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

[editar]

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.

Véase también

[editar]

Referencias

[editar]
  1. Gruber, H.; Holzer, M.; Ruepp, O., «Sorting the slow way: an analysis of perversely awful randomized sorting algorithms», 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, Springer-Verlag, pp. 183-197, doi:10.1007/978-3-540-72914-3_17 ..
  2. a b Kiselyov, Oleg; Shan, Chung-chieh; Friedman, Daniel P.; Sabry, Amr (2005), «Backtracking, interleaving, and terminating monad transformers: (functional pearl)», Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05), SIGPLAN Notices, pp. 192-203, doi:10.1145/1086365.1086390, archivado desde el original el 26 de marzo de 2012, consultado el 2 de agosto de 2013 .
  3. a b Naish, Lee (1986), «Negation and quantifiers in NU-Prolog», Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science 225, Springer-Verlag, pp. 624-634, doi:10.1007/3-540-16492-8_111 ..
  4. a b Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne ..
  5. «Bogosort». The Jargon File 4.4.8. 2003. Consultado el 11 de abril de 2013. 

Enlaces externos

[editar]