Stupid sort

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

Este algoritmo de búsqueda 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[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, http://www.hermann-gruber.com/data/fun07-final.pdf .
  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, http://www.dicta.org.uk/programming/LogicT.pdf 
  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, Plantilla:Citeseerx .
  5. «Bogosort». The Jargon File 4.4.8 (2003). Consultado el 11 de abril de 2013.

Véase también[editar]

Enlaces externos[editar]