El algoritmo de ordenación que parece no funcionar pero ordena
I Can't Believe It Can Sort
El algoritmo "I Can't Believe It Can Sort" es un método de ordenación simple e ineficiente que, a simple vista, parece no poder ordenar. Su pseudocódigo, extraído del artículo de Stanley P. Y. Fung, usa dos bucles anidados que comparan e intercambian elementos hasta ordenar el array. Con complejidad O(n²), es mucho menos eficiente que quicksort o mergesort, pero sorprende que funcione.
El motivo de su nombre es que si miras el pseudocódigo, no pensarás que puede ordenar, pero lo hace.
- Someone
Artículo sobre esto con prueba de cómo/por qué funciona: https://arxiv.org/pdf/2110.01111, que dice:
“No hay nada bueno en este algoritmo. Es lento – el algoritmo obviamente se ejecuta en tiempo Θ(n2), ya sea en el peor caso, caso promedio o mejor caso. Compara innecesariamente todos los pares de posiciones, dos veces (pero véase la Sección 3). Parece no haber intuición detrás de él, y su corrección no es del todo obvia. Ciertamente no querrías usarlo como primer ejemplo para introducir a los estudiantes a los algoritmos de ordenación. No es estable, no funciona bien para ordenación externa, no puede ordenar entradas que llegan en línea, y no se beneficia de entradas parcialmente ordenadas. Su único atractivo puede ser su simplicidad, en términos de líneas de código y la “simetría” de los dos bucles.”*
- EQFitzgerald
¿Por qué no ordenaría? Parece el método que la mayoría de la gente usa para ordenar cosas manualmente.
- edflsafoiewq
Anteriormente (2021): https://news.ycombinator.com/item?id=28758106