Burbuja

A pesar de que el ordenamiento de burbuja es uno de los algoritmos más sencillos de implementar, su orden O (n2) lo hace muy ineficiente para usar en listas que tengan más que un número reducido deelementos. Incluso entre los algoritmos de ordenamiento de orden O (n2), otros procedimientos como el ordenamiento por inserción son considerados más eficientes.

Dada su simplicidad, el ordenamientode burbuja es utilizado para introducir el concepto de algoritmo de ordenamiento para estudiantes de ciencias de la computación. A pesar de esto, algunos investigadores como Owen Astrachan hancriticado su popularidad en la enseñanza de ciencias de la computación, llegando a recomendar su eliminación de los planes de estudio.1

Sumado a esto, Jargon File, un libro ampliamente citado en lacultura hacker, lo denomina "el mal algoritmo genérico", y Donald Knuth, uno de los mayores expertos en ciencias de la computación, afirma que el ordenamiento de burbuja "no parece tener nada pararecomendar su uso, a excepción de un nombre pegajoso y el hecho de que conlleva a problemas teóricos interesantes".2

El ordenamiento de burbuja es asintóticamente equivalente en tiempos de ejecución con elordenamiento por inserción en el peor de los casos, pero ambos algoritmos difieren principalmente en la cantidad de intercambios que son necesarios. Resultados experimentales como los descubiertospor Astrachan han demostrado que el ordenamiento por inserción funcionan considerablemente mejor incluso con listas aleatorias. Por esta razón, muchos libros de algoritmos modernos evitan usar elordenamiento de burbuja, reemplazándolo por el ordenamiento por inserción.

El ordenamiento de burbuja interactúa vagamente con el hardware de las CPU modernas. Requiere al menos el doble de escriturasque el ordenamiento por inserción, el doble de pérdidas de cache, y asintóticamente más predicción de saltos. Varios experimentos de ordenamiento de cadenas en Java hechos por Astrachan muestran que...