Stupid Sort, en inglés también conocido como BogoSort[1][2] (o como slowsort[3][4]), es un algoritmo de búsqueda 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.
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), , 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.
Distintas implementaciones del algoritmo en Wikibooks (inglés)
Distintas implementaciones del algoritmo en RosettaCode.org (inglés)
Datos:Q762850
Junio 27, 2023
stupid, sort, stupid, sort, inglés, también, conocido, como, bogosort, como, slowsort, algoritmo, búsqueda, particularmente, inefectivo, basado, paradigma, ensayo, error, útil, para, ordenar, pero, puede, utilizado, propósitos, educativos, para, contrastarlo, . Stupid Sort en ingles tambien conocido como BogoSort 1 2 o como slowsort 3 4 es un algoritmo de busqueda particularmente inefectivo basado en el paradigma de ensayo y error No es util para ordenar pero puede ser utilizado con propositos educativos para contrastarlo con algoritmos mas efectivos Tambien ha sido usado como ejemplo en programacion logica 2 3 4 Si stupid sort fuera utilizado para ordenar un mazo de cartas consistiria en verificar primero si el mazo esta en orden y si no lo esta entonces deberiamos mezclar las cartas de forma aleatoria verificar de nuevo si estan ordenadas y asi sucesivamente hasta que por una mezcla al azar encontremos el mazo ordenado El nombre bogosort proviene de la palabra bogus 5 Indice 1 Complejidad y finalizacion 2 Referencias 3 Vease tambien 4 Enlaces externosComplejidad y finalizacion EditarEste algoritmo de ordenamiento es probabilistico por naturaleza Si se aplica a un arreglo donde todos los elementos son distintos el numero esperado de comparaciones es asintoticamente equivalente a e 1 n displaystyle e 1 n y el numero esperado de intercambios swaps en el caso promedio es igual a n 1 n displaystyle n 1 n En el peor caso el numero de comparaciones e intercambios no esta acotada Es decir no hay certeza de que el algoritmo termine El mejor caso es cuando la lista original esta ordenada entonces se realizan n 1 displaystyle n 1 comparaciones y ningun intercambio Referencias Editar 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 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 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 a b 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 Vease tambien EditarAlgoritmo de ordenamientoEnlaces externos EditarDistintas implementaciones del algoritmo en Wikibooks ingles Distintas implementaciones del algoritmo en RosettaCode org ingles Datos Q762850 Obtenido de https es wikipedia org w index php title Stupid sort amp oldid 150280572, wikipedia, wiki, leyendo, leer, libro, biblioteca,
