El ordenamiento de burbuja , a veces denominado ordenamiento por hundimiento , es un algoritmo de ordenamiento 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 recorridos por la lista se repiten hasta que no es necesario realizar ningún intercambio durante un recorrido, lo que significa que la lista se ha ordenado por completo. El algoritmo, que es un ordenamiento por comparación , recibe su nombre por la forma en que los elementos más grandes "burbujean" hasta la parte superior de la lista.
Este algoritmo simple tiene un rendimiento deficiente en el uso en el mundo real y se utiliza principalmente como una herramienta educativa. Las bibliotecas de ordenamiento integradas en lenguajes de programación populares como Python y Java utilizan algoritmos más eficientes como quicksort , timsort o merge sort . [2] [3] Sin embargo, si se permite el procesamiento en paralelo, el ordenamiento por burbuja ordena en tiempo O(n), lo que lo hace considerablemente más rápido que las implementaciones paralelas de ordenamiento por inserción o por selección que no paralelizan de manera tan efectiva. [ cita requerida ]
La primera descripción del algoritmo Bubble sort se publicó en 1956 en un artículo del matemático y actuario Edward Harry Friend, [4] Sorting on electronic computer systems , [5] publicado en el tercer número del tercer volumen del Journal of the Association for Computing Machinery (ACM), como un "algoritmo de intercambio de ordenación". Friend describió los fundamentos del algoritmo y, aunque inicialmente su artículo pasó desapercibido, algunos años después fue redescubierto por muchos científicos informáticos, incluido Kenneth E. Iverson, quien acuñó su nombre actual.
El ordenamiento de burbuja tiene una complejidad promedio y en el peor de los casos de , donde es la cantidad de elementos que se ordenan. La mayoría de los algoritmos de ordenamiento prácticos tienen una complejidad promedio o en el peor de los casos sustancialmente mejor, a menudo . Incluso otros algoritmos de ordenamiento, como el ordenamiento por inserción , generalmente se ejecutan más rápido que el ordenamiento de burbuja y no son más complejos. Por esta razón, el ordenamiento de burbuja rara vez se usa en la práctica.
Al igual que el ordenamiento por inserción , el ordenamiento por burbuja es adaptativo , lo que puede darle una ventaja sobre algoritmos como el ordenamiento rápido . Esto significa que puede superar a esos algoritmos en casos en los que la lista ya está mayoritariamente ordenada (con una pequeña cantidad de inversiones ), a pesar del hecho de que tiene una peor complejidad temporal de caso promedio. Por ejemplo, el ordenamiento por burbuja se realiza en una lista que ya está ordenada, mientras que el ordenamiento rápido aún realizaría todo su proceso de ordenamiento.
Si bien cualquier algoritmo de clasificación se puede realizar en una lista preordenada simplemente verificando la lista antes de que se ejecute el algoritmo, es más difícil replicar un rendimiento mejorado en listas casi ordenadas.
La distancia y la dirección en la que los elementos deben moverse durante la clasificación determinan el rendimiento de la clasificación de burbuja porque los elementos se mueven en diferentes direcciones a diferentes velocidades. Un elemento que debe moverse hacia el final de la lista puede moverse rápidamente porque puede participar en intercambios sucesivos. Por ejemplo, el elemento más grande de la lista ganará cada intercambio, por lo que se mueve a su posición ordenada en el primer paso 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 paso, 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 estos tipos de elementos se denominen conejos y tortugas, respectivamente, en honor a los personajes de la fábula de Esopo La liebre y la tortuga .
Se han hecho varios esfuerzos para eliminar las tortugas y mejorar la velocidad de la ordenación de burbuja. La ordenación de cóctel es una ordenación de burbuja bidireccional que va de principio a fin y luego se invierte, yendo de principio a fin. Puede mover las tortugas bastante bien, pero conserva la complejidad del peor de los casos. La ordenación de peine compara elementos separados por grandes espacios y puede mover las tortugas extremadamente rápido antes de proceder 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 alto utilizando el método de clasificación de burbuja. En cada paso, se comparan los elementos escritos en negrita . Se requerirán tres pasos;
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 si está ordenada.
En pseudocódigo, el algoritmo se puede expresar como (matriz basada en 0):
procedimiento bubbleSort ( A : lista de elementos ordenables ) n := length ( A ) repetir swapped := false for i := 1 to n - 1 inclusive hacer { si este par está fuera de orden } si A [ i - 1 ] > A [ i ] entonces { intercambiarlos y recordar que algo cambió } swap ( A [ i - 1 ] , A [ i ]) swapped := true fin si fin para hasta que no se haya intercambiado fin del procedimiento El algoritmo de ordenamiento de burbuja se puede optimizar observando que el paso n -ésimo encuentra el elemento n -ésimo más grande y lo coloca en su lugar final. De esta manera, el bucle interno puede evitar mirar los últimos n − 1 elementos cuando se ejecuta por n -ésima vez:
procedimiento bubbleSort ( A : lista de elementos ordenables ) n := length ( A ) repetir swapped := false for i := 1 to n - 1 inclusive hacer if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) swapped := true fin if fin for n := n - 1 hasta que no se swapped fin procedimiento En términos más generales, puede suceder que más de un elemento se coloque 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 comprobarlos. Esto nos permite omitir muchos elementos, lo que da como resultado una mejora de aproximadamente el 50 % en el recuento de comparación en el peor de los casos (aunque no hay mejora en el recuento de intercambios) 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 := length ( A ) repetir newn := 0 para i := 1 a n - 1 inclusive hacer si A [ i - 1 ] > A [ i ] entonces intercambiar ( A [ i - 1 ] , A [ i ]) newn := i fin si fin para n := newn hasta que n ≤ 1 fin procedimiento Modificaciones alternativas, como la clasificación con coctelera, intentan mejorar el rendimiento de la clasificación con burbuja, manteniendo al mismo tiempo la misma idea de comparar e intercambiar repetidamente elementos adyacentes.
Aunque el ordenamiento de burbuja es uno de los algoritmos de ordenamiento más sencillos de entender e implementar, su complejidad O ( n 2 ) significa que su eficiencia disminuye drásticamente en listas de más de un pequeño número de elementos. Incluso entre los algoritmos de ordenamiento O ( n 2 ) simples , los algoritmos como el ordenamiento por inserción suelen ser considerablemente más eficientes.
Debido a su simplicidad, el método de ordenación por burbuja se utiliza a menudo para introducir el concepto de algoritmo, o algoritmo de ordenación, a los estudiantes de informática básica . Sin embargo, algunos investigadores como Owen Astrachan han hecho todo lo posible para desprestigiar el método de ordenación por burbuja y su continua popularidad en la enseñanza de la informática, recomendando que ya no se enseñe. [6]
El Jargon File , que llama al bogosort "el algoritmo arquetípico [sic] perversamente terrible", también llama al bubble sort "el algoritmo genérico malo". [7] Donald Knuth , en The Art of Computer Programming , concluyó que "el bubble sort no parece 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]
En el peor de los casos, el ordenamiento por burbuja es asintóticamente equivalente en tiempo de ejecución al ordenamiento por inserción, pero los dos algoritmos difieren en gran medida en el número de intercambios necesarios. Los resultados experimentales, como los de Astrachan, también han demostrado que el ordenamiento por inserción funciona considerablemente mejor incluso en listas aleatorias. Por estas razones, muchos libros de texto de algoritmos modernos evitan utilizar el algoritmo de ordenamiento por burbuja en favor del ordenamiento por inserción.
El ordenamiento de burbuja también interactúa mal con el hardware de CPU moderno. Produce al menos el doble de escrituras que el ordenamiento por inserción, el doble de errores de caché y, asintóticamente, más predicciones erróneas de bifurcación . [ cita requerida ] Los experimentos de Astrachan con cadenas de ordenamiento en Java muestran que el ordenamiento de burbuja es aproximadamente una quinta parte de rápido que un ordenamiento por inserción y un 70% de rápido que un ordenamiento por selección . [6]
En el campo de los gráficos por ordenador, el método de ordenación por burbuja es popular por su capacidad de detectar un error muy pequeño (como el intercambio de tan solo dos elementos) en matrices casi ordenadas y solucionarlo con una 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 exploración específica (una línea paralela al eje x ) y, al incrementar y, su orden cambia (se intercambian dos elementos) solo en las intersecciones de dos líneas. El método de ordenación por burbuja es un algoritmo de ordenación estable, como el método de ordenación por inserción.
En ocasiones se ha hecho referencia al método de clasificación por burbuja como "clasificación por hundimiento". [9]
Por ejemplo, Donald Knuth describe la inserción de valores en o hacia su ubicación deseada como dejar que "[el valor] se asiente en su nivel adecuado", y que "este método de clasificación a veces se ha llamado la técnica de tamizado o hundimiento ". [10]
Este debate se perpetúa por la facilidad con que se puede considerar este algoritmo desde dos perspectivas diferentes pero igualmente válidas:
En una entrevista de 2007, el ex director ejecutivo de Google , Eric Schmidt, le preguntó al entonces candidato presidencial Barack Obama cuál era la mejor manera de ordenar un millón de números enteros ; Obama hizo una pausa por un momento y respondió: "Creo que la clasificación de burbuja sería el camino equivocado". [11] [12]
{{cite AV media}}: Mantenimiento de CS1: ubicación ( enlace )
