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.
  1. 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.”*

  2. EQFitzgerald

    ¿Por qué no ordenaría? Parece el método que la mayoría de la gente usa para ordenar cosas manualmente.

  3. edflsafoiewq

    Anteriormente (2021): https://news.ycombinator.com/item?id=28758106

Más de este día

2026-11-16