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

Referencias

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..
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.
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..
Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne..
«Bogosort». The Jargon File 4.4.8. 2003. Consultado el 11 de abril de 2013.

Véase también

Algoritmo de ordenamiento

Enlaces externos

Datos: Q762850

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[Fun07-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..

[KSFS-2] 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.

[Naish86-3] 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..

[Naish95-4] 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.