La clasificación de burbujas , a veces denominada clasificación por hundimiento , es un algoritmo de clasificación simple que recorre repetidamente la lista de entrada elemento por elemento, comparando el elemento actual con el siguiente e intercambiando sus valores si es necesario. Estos pases por la lista se repiten hasta que no es necesario realizar intercambios durante un pase, lo que significa que la lista queda completamente ordenada. El algoritmo, que es una clasificación por comparación , recibe su nombre por la forma en que los elementos más grandes "burbujan" hasta la parte superior de la lista.
Este algoritmo simple funciona mal en el mundo real y se utiliza principalmente como herramienta educativa. Las bibliotecas de clasificación integradas en lenguajes de programación populares como Python y Java utilizan algoritmos más eficientes, como quicksort , timsort o merge sort . Sin embargo, si se permite el procesamiento paralelo, la clasificación por burbujas se realiza en tiempo O(n), lo que la hace considerablemente más rápida que las implementaciones paralelas de clasificación por inserción o selección que no se paralelizan con tanta eficacia. [2] [3]
La descripción más antigua del algoritmo de clasificación de burbujas se encuentra en un artículo de 1956 del matemático y actuario Edward Harry Friend, [4] Sorting on electronic computersystems , [5] publicado en el tercer número del tercer volumen del Journal of the Association for Computing. Maquinaria (ACM), como "Algoritmo de intercambio de clasificación". Friend describió los fundamentos del algoritmo y, aunque inicialmente su artículo pasó desapercibido, algunos años más tarde fue redescubierto por muchos científicos informáticos, incluido Kenneth E. Iverson , quien acuñó su nombre actual.
La clasificación de burbujas tiene una complejidad promedio y en el peor de los casos de , donde es la cantidad de elementos que se clasifican. La mayoría de los algoritmos de clasificación prácticos tienen una complejidad promedio o en el peor de los casos sustancialmente mejor, a menudo . Incluso otros algoritmos de clasificación, como la clasificación por inserción , generalmente se ejecutan más rápido que la clasificación por burbujas y no son más complejos. Por esta razón, la clasificación por burbujas rara vez se utiliza en la práctica.
Al igual que la ordenación por inserción , la ordenación por burbujas es adaptativa , lo que puede darle una ventaja sobre algoritmos como la ordenación rápida . Esto significa que puede superar a esos algoritmos en los casos en que la lista ya está en su mayor parte ordenada (con una pequeña cantidad de inversiones ), a pesar de que tiene una peor complejidad de tiempo promedio en los casos. Por ejemplo, la clasificación por burbujas está en una lista que ya está ordenada, mientras que la clasificación rápida aún realizaría todo el proceso de clasificación.
Si bien se puede crear cualquier algoritmo de clasificación en una lista preclasificada simplemente verificando la lista antes de ejecutar el algoritmo, el rendimiento mejorado en listas casi ordenadas es más difícil de replicar.
La distancia y la dirección en que los elementos deben moverse durante la clasificación determinan el rendimiento de la clasificación de burbujas porque los elementos se mueven en diferentes direcciones a diferentes velocidades. Un elemento que debe moverse hacia el final de la lista puede hacerlo rápidamente porque puede participar en sucesivos intercambios. Por ejemplo, el elemento más grande de la lista ganará cada intercambio, por lo que se mueve a su posición ordenada en la primera pasada incluso si comienza cerca del principio. Por otro lado, un elemento que debe moverse hacia el principio de la lista no puede moverse más rápido que un paso por pasada, por lo que los elementos se mueven hacia el principio muy lentamente. Si el elemento más pequeño está al final de la lista, se necesitarán pases para moverlo al principio. Esto ha llevado a que a este tipo de elementos se les denomine conejos y tortugas, respectivamente, en honor a los personajes de la fábula de Esopo La liebre y la tortuga .
Se han realizado varios esfuerzos para eliminar las tortugas y mejorar la velocidad de formación de burbujas. La clasificación de cócteles es una clasificación de burbujas bidireccional que va de principio a fin y luego se invierte, de un extremo a otro. Puede mover tortugas bastante bien, pero conserva la complejidad del peor de los casos. La clasificación en peine compara elementos separados por espacios grandes y puede mover las tortugas extremadamente rápido antes de pasar a espacios cada vez más pequeños para suavizar la lista. Su velocidad promedio es comparable a algoritmos más rápidos como Quicksort .
Tome una matriz de números "5 1 4 2 8" y ordene la matriz desde el número más bajo hasta el número más grande usando la clasificación de burbujas. En cada paso se comparan los elementos escritos en negrita . Se requerirán tres pases;
Ahora, la matriz ya está ordenada, pero el algoritmo no sabe si está completa. El algoritmo necesita una pasada completa adicional sin ningún intercambio para saber que está ordenado.
En pseudocódigo, el algoritmo se puede expresar como (matriz basada en 0):
procedimiento bubbleSort ( A : lista de elementos ordenables ) n : = longitud ( A ) repetición intercambiada := false for i := 1 an - 1 inclusive do { si este par está fuera de orden } if A [ i - 1 ] > A [ i ] luego {intercambiarlos y recordar que algo cambió} intercambiar ( A [ i - 1 ] , A [ i ]) intercambiado : = verdadero fin si fin para hasta que no se intercambie procedimiento final El algoritmo de clasificación de burbujas se puede optimizar observando que la enésima pasada encuentra el enésimo elemento más grande y lo coloca en su lugar final. Por lo tanto, el bucle interno puede evitar mirar los últimos n − 1 elementos cuando se ejecuta por enésima vez:
procedimiento bubbleSort ( A : lista de elementos ordenables ) n := longitud ( A ) repetir intercambiado := falso para i : = 1 an - 1 inclusive hacer si A [ i - 1 ] > A [ i ] luego intercambiar ( A [ i - 1 ] , A [ i ]) intercambiado := verdadero fin si finaliza para n := n - 1 hasta que no se intercambie fin del procedimiento De manera más general, puede suceder que más de un elemento sea colocado en su posición final en una sola pasada. En particular, después de cada pasada, todos los elementos después del último intercambio se ordenan y no es necesario volver a verificarlos. Esto nos permite omitir muchos elementos, lo que resulta en una mejora del 50 % en el peor de los casos en el recuento de comparación (aunque no hay mejora en el recuento de intercambio), y agrega muy poca complejidad porque el nuevo código incluye la variable "intercambiada":
Para lograr esto en pseudocódigo, se puede escribir lo siguiente:
procedimiento bubbleSort ( A : lista de elementos ordenables ) n : = longitud ( A ) repetir newn : = 0 para i : = 1 a n - 1 inclusive haga si A [ i - 1 ] > A [ i ] luego intercambie ( A [ i - 1 ] , A [ i ]) newn := i finalizo si finalizo para n := newn hasta n ≤ 1 finaliza el procedimiento Las modificaciones alternativas, como la clasificación de la coctelera, intentan mejorar el rendimiento de la clasificación de burbujas manteniendo la misma idea de comparar e intercambiar repetidamente elementos adyacentes.
Aunque la clasificación de burbujas es uno de los algoritmos de clasificación más simples de comprender e implementar, su complejidad O ( n 2 ) significa que su eficiencia disminuye dramáticamente en listas de más de una pequeña cantidad de elementos. Incluso entre los algoritmos de clasificación O ( n 2 ) simples, los algoritmos como la clasificación por inserción suelen ser considerablemente más eficientes.
Debido a su simplicidad, la clasificación de burbujas se utiliza a menudo para presentar el concepto de algoritmo, o algoritmo de clasificación, a los estudiantes de introducción a la informática . Sin embargo, algunos investigadores como Owen Astrachan han hecho todo lo posible para menospreciar el tipo de burbujas y su continua popularidad en la educación informática, recomendando que ni siquiera se enseñe más. [6]
The Jargon File , que llama a bogosort "el algoritmo arquetípico [sic] perversamente horrible", también llama a bubble sort "el algoritmo genérico malo". [7] Donald Knuth , en The Art of Computer Programming , concluyó que "el tipo burbuja parece no tener nada que lo recomiende, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes", algunos de los cuales luego analiza. . [8]
La ordenación por burbuja es asintóticamente equivalente en tiempo de ejecución a la ordenación por inserción en el peor de los casos, pero los dos algoritmos difieren mucho en la cantidad de intercambios necesarios. Los resultados experimentales como los de Astrachan también han demostrado que la ordenación por inserción funciona considerablemente mejor incluso en listas aleatorias. Por estas razones, muchos libros de texto de algoritmos modernos evitan el uso del algoritmo de ordenación por burbujas en favor de la ordenación por inserción.
La clasificación de burbujas también interactúa mal con el hardware de CPU moderno. Produce al menos el doble de escrituras que la ordenación por inserción, el doble de errores de caché y asintóticamente más predicciones erróneas de rama . [ cita necesaria ] Los experimentos realizados por Astrachan ordenando cadenas en Java muestran que la ordenación por burbujas es aproximadamente una quinta parte más rápida que una ordenación por inserción y un 70% más rápida que una ordenación por selección . [6]
En los gráficos por computadora, la clasificación de burbujas es popular por su capacidad de detectar un error muy pequeño (como el intercambio de solo dos elementos) en matrices casi ordenadas y solucionarlo con solo complejidad lineal (2 n ). Por ejemplo, se utiliza en un algoritmo de relleno de polígonos, donde las líneas delimitadoras se ordenan por su coordenada x en una línea de escaneo específica (una línea paralela al eje x ) y al incrementar y su orden cambia (se intercambian dos elementos) solo en intersecciones de dos rectas. La clasificación por burbujas es un algoritmo de clasificación estable, como la clasificación por inserción.
En ocasiones se ha hecho referencia a la clasificación por burbujas como "clasificación por hundimiento". [9]
Por ejemplo, Donald Knuth describe la inserción de valores en o hacia su ubicación deseada como permitir que "[el valor] se establezca en su nivel adecuado", y que "este método de clasificación a veces se ha denominado técnica de tamizado o hundimiento ".
Este debate se perpetúa por la facilidad con la que se puede considerar este algoritmo desde dos perspectivas diferentes pero igualmente válidas:
En 2007, el ex director ejecutivo de Google , Eric Schmidt, preguntó al entonces candidato presidencial Barack Obama durante una entrevista sobre la mejor manera de ordenar un millón de números enteros ; Obama hizo una pausa por un momento y respondió: "Creo que el tipo de burbuja sería el camino equivocado a seguir". [11] [12]
{{cite AV media}}: CS1 maint: location (link)
