Clasificación de burbujas

El algoritmo de ordenación de burbuja , también conocido como ordenación por hundimiento , es un algoritmo sencillo que recorre repetidamente la lista de entrada elemento por elemento, comparando el elemento actual con el siguiente e intercambiando sus valores si es necesario. Estas pasadas por la lista se repiten hasta que no sea necesario realizar ningún intercambio durante una pasada, lo que significa que la lista está completamente ordenada. El algoritmo, que es una ordenación por comparación , recibe su nombre por la forma en que los elementos más grandes "burbujean" hacia la parte superior de la lista.

Su rendimiento es deficiente en el uso real y se utiliza principalmente como herramienta educativa. Algoritmos más eficientes como quicksort , timsort o merge sort se utilizan en las bibliotecas de ordenación integradas en lenguajes de programación populares como Python y Java. ^{[ 2 ]}^{[ 3 ]}

Historia

La primera descripción del algoritmo de ordenación de burbuja se encuentra en un artículo de 1956 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.

Análisis

Un ejemplo de ordenación de burbuja. Comenzando desde el principio de la lista, se comparan todos los pares adyacentes, intercambiando su posición si no están en el orden correcto (el último es menor que el primero). Después de cada iteración , se compara un elemento menos (el último) hasta que no queden más elementos por comparar.

Actuación

El algoritmo de ordenación de burbuja tiene una complejidad promedio y en el peor de los casos de $O(n^{2})$ , dónde $n$ es el número de elementos que se están ordenando. La mayoría de los algoritmos de ordenación prácticos tienen una complejidad promedio o en el peor de los casos sustancialmente mejor, a menudo $O(n\log n)$ . Incluso otros $O(n^{2})$ Los algoritmos de ordenación, como el de inserción , suelen ser más rápidos que el de burbuja y no son más complejos. Por esta razón, el de burbuja rara vez se utiliza en la práctica.

Al igual que el ordenamiento por inserción , el ordenamiento de 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 donde la lista ya está mayormente ordenada (con un pequeño número de inversiones ), a pesar de que tiene una complejidad temporal promedio peor. Por ejemplo, el ordenamiento de burbuja es $O(n)$ en una lista que ya está ordenada, mientras que quicksort aún realizaría todo su proceso. $O(n\log n)$ proceso de clasificación.

Si bien se puede hacer cualquier algoritmo de ordenación $O(n)$ En una lista preordenada, simplemente comprobando la lista antes de que se ejecute el algoritmo, es más difícil replicar la mejora del rendimiento en listas casi ordenadas.

Conejos y tortugas

La distancia y la dirección en la que los elementos deben moverse durante la ordenación determinan el rendimiento del algoritmo de ordenación de burbuja, ya que 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 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, tardará más tiempo en moverse. $n-1$ pases para moverlo al principio. Esto ha llevado a que este tipo de elementos se denominen conejos y tortugas, respectivamente, en honor a los personajes de la fábula de Esopo La tortuga y la liebre .

Se han realizado varios esfuerzos para eliminar las tortugas y mejorar la velocidad del algoritmo de ordenación de burbuja. El algoritmo de ordenación de cóctel es un algoritmo de ordenación de burbuja bidireccional que va del principio al final y luego se invierte, yendo del final al principio. Puede mover las tortugas bastante bien, pero conserva $O(n^{2})$ Complejidad en el peor de los casos. El algoritmo de ordenación Comb compara elementos separados por grandes espacios y puede mover 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 la de algoritmos más rápidos como Quicksort .

Ejemplo paso a paso

Toma un arreglo de números "5 1 4 2 8" y ordénalo de menor a mayor usando el algoritmo de ordenación de burbuja. En cada paso, se comparan los elementos en negrita . Se requerirán tres pasadas:

Primer pase: ( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Aquí, el algoritmo compara los dos primeros elementos y los intercambia ya que 5 > 1.; ( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Intercambiar ya que 5 > 4; ( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Intercambiar ya que 5 > 2; ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Ahora, como estos elementos ya están en orden (8 > 5), el algoritmo no los intercambia.
Segundo pase: ( 1 4 2 5 8 ) → ( 1 4 2 5 8 ); ( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Intercambiar ya que 4 > 2; ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Ahora bien, el arreglo ya está ordenado, pero el algoritmo no sabe si está completo. El algoritmo necesita una pasada completa adicional sin intercambios para saber si está ordenado.

Tercer pase: ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 ); ( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Implementación

Implementación en pseudocódigo

En pseudocódigo, el algoritmo se puede expresar como (matriz de base 0):

procedimiento bubbleSort ( A : lista de elementos ordenables ) n := longitud ( A ) repetir intercambiado := falso para i := 1 a n - 1 inclusive hacer { si este par está fuera de orden } si A [ i - 1 ] > A [ i ] entonces { intercambiarlos y recordar que algo cambió } intercambiar ( A [ i - 1 ] , A [ i ]) intercambiado := verdadero fin si fin para hasta que no se intercambie fin procedimiento

Optimización del ordenamiento de burbuja

Ordenación de burbujas paso a paso

Reiniciar Siguiente paso

4 4

3

7

1

Comparando Ay AIntercambiando desde

>

Continuando desde

≯La lista está ordenada

0

El algoritmo de ordenación de burbuja se puede optimizar observando que en la n -ésima pasada se encuentra el n -ésimo elemento más grande y se coloca en su posición final. Por lo tanto, el bucle interno puede evitar examinar los últimos n -1 elementos al ejecutarse por n -ésima vez:

procedimiento bubbleSort ( A : lista de elementos ordenables ) n := longitud ( A ) repetir intercambiado := falso para i := 1 a n - 1 inclusive hacer si A [ i - 1 ] > A [ i ] entonces intercambiar ( A [ i - 1 ] , A [ i ]) intercambiado := verdadero fin si fin para n := n - 1 hasta que no se intercambie fin procedimiento

En términos más generales, puede ocurrir 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 posteriores al último intercambio se ordenan y no es necesario volver a comprobarlos. Esto nos permite omitir muchos elementos, lo que resulta en una mejora de aproximadamente el 50 % en el recuento de comparaciones en el peor de los casos (aunque sin mejora en el recuento de intercambios), y añade muy poca complejidad porque el nuevo código engloba la swappedvariable:

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 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

Otras modificaciones, como la ordenación por agitación, intentan mejorar el rendimiento de la ordenación de burbuja manteniendo la misma idea de comparar e intercambiar repetidamente elementos adyacentes.

Usar

Ordenación de burbuja. La lista se representó en un sistema de coordenadas cartesianas, donde cada punto ( x , y ) indica que el valor y se almacena en el índice x . A continuación, la lista se ordena mediante el algoritmo de burbuja según el valor de cada píxel. Cabe destacar que los elementos más grandes se ordenan primero, y los más pequeños tardan más en llegar a sus posiciones correctas.

Aunque el algoritmo de ordenación de burbuja es uno de los más sencillos de entender e implementar, su complejidad O ( n² ⁾ implica que su eficiencia disminuye drásticamente en listas con un número considerable de elementos. Incluso entre los algoritmos de ordenación O ( n² ⁾ más sencillos , algoritmos como el de inserción suelen ser mucho más eficientes.

Debido a su simplicidad, el algoritmo de ordenación de burbuja se utiliza a menudo para introducir el concepto de algoritmo, o algoritmo de ordenación, a estudiantes de informática de nivel introductorio . Sin embargo, algunos educadores, como Owen Astrachan, se han esforzado por desacreditar el algoritmo de ordenación de burbuja y su continua popularidad en la enseñanza de la informática, recomendando incluso que deje de enseñarse. ^{[ 6 ]}

The Jargon File , que se hizo famoso por llamar a bogosort "el algoritmo arquetípico perversamente horrible", también llama a bubble sort "el algoritmo genérico malo". ^{[ 7 ]} Donald Knuth , en The Art of Computer Programming , concluyó que "bubble sort parece no tener nada recomendable, excepto un nombre pegadizo y el hecho de que conduce a algunos problemas teóricos interesantes", algunos de los cuales luego analiza. ^{[ 8 ]}

El algoritmo de ordenación de burbuja es asintóticamente equivalente en tiempo de ejecución a la ordenación por inserción en el peor de los casos, pero difieren enormemente en el número de intercambios necesarios. Resultados experimentales como los de Astrachan también han demostrado que la ordenación por inserción funciona considerablemente mejor incluso con listas aleatorias. Por estas razones, muchos libros de texto de algoritmos modernos evitan usar el algoritmo de ordenación de burbuja y prefieren la ordenación por inserción.

El algoritmo de ordenación de burbuja también presenta un mal funcionamiento con el hardware de CPU moderno. Produce al menos el doble de escrituras que la ordenación por inserción, el doble de fallos de caché y, asintóticamente, más predicciones erróneas de bifurcación . Los experimentos de Astrachan ordenando cadenas en Java muestran que la ordenación de burbuja es aproximadamente una quinta parte de rápida que la ordenación por inserción y un 70 % de rápida que la ordenación por selección . ^[⁶^]

En gráficos por computadora, el algoritmo de ordenación de burbuja es popular por su capacidad para detectar errores muy pequeños (como el intercambio de solo dos elementos) en arreglos casi ordenados y corregirlos con una complejidad lineal (2ⁿ ) . Por ejemplo, se utiliza en un algoritmo de relleno de polígonos, donde las líneas delimitadoras se ordenan según 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 las intersecciones de dos líneas. El algoritmo de ordenación de burbuja es un algoritmo de ordenación estable, como el de inserción.

Variaciones

El algoritmo de ordenación par-impar es una versión paralela del algoritmo de ordenación de burbuja, para sistemas de paso de mensajes.
Las pasadas pueden ser de derecha a izquierda, en lugar de izquierda a derecha. Esto es más eficiente para listas con elementos sin ordenar añadidos al final.
La coctelera alterna pases hacia la izquierda y hacia la derecha.
El algoritmo de ordenación Comb es una modificación del algoritmo de ordenación Bubble, del mismo modo que el algoritmo de ordenación Shell modifica el algoritmo de ordenación Insertion.

Debate sobre el nombre

El algoritmo de ordenación de burbuja se ha denominado ocasionalmente "ordenación descendente". ^{[ 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 técnica de tamizado o hundimiento . ^{[ 10 ]}

Este debate se perpetúa por la facilidad con la que se puede considerar este algoritmo desde dos perspectivas diferentes pero igualmente válidas:

Los valores más grandes podrían considerarse más pesados y, por lo tanto, se vería que se hunden progresivamente hasta el final de la lista.
Los valores más pequeños podrían considerarse más ligeros y, por lo tanto, tenderían a ascender progresivamente hasta la parte superior de la lista.

En la cultura popular

En una entrevista de 2007, el ex director ejecutivo de Google, Eric Schmidt, le preguntó al entonces candidato presidencial Barack Obama 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 algoritmo de ordenación de burbuja no sería la forma correcta de hacerlo". ^{[ 11 ]}^{[ 12 ]}

Notas

↑ Cortesi, Aldo (27 de abril de 2007). "Visualización de algoritmos de ordenación" . Recuperado el 16 de marzo de 2017 .
↑ " [ JDK-6804124 ] (coll) Reemplazar "modified mergesort" en java.util.Arrays.sort con timsort - Java Bug System" . bugs.openjdk.java.net . Consultado el 11 de enero de 2020 .
↑ Peters, Tim (2002-07-20). " [ Python-Dev ] Ordenación" . Recuperado el 2020-01-11 .
↑ "Obituario de Edward Friends (2019) - Washington, DC - The Washington Post" . Legacy.com .
↑ Friend, Edward H. (1956). "Clasificación en sistemas informáticos electrónicos" . Journal of the ACM . 3 (3): 134– 168. doi : 10.1145/320831.320833 . S2CID 16071355 .
1 2 Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF) . ACM SIGCSE Bulletin . 35 (1): 1– 5. doi : 10.1145/792548.611918 . ISSN 0097-8418 .
↑ "jerga, nodo: bogo-sort" . www.jargon.net .
↑ Donald Knuth . El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998. ISBN 0-201-89685-0Páginas 106-110 de la sección 5.2.2: Ordenación por intercambio. «Aunque las técnicas empleadas en los cálculos [para analizar el algoritmo de ordenación de burbuja] son instructivas, los resultados son decepcionantes, ya que indican que este algoritmo no es realmente muy bueno. En comparación con la inserción directa […], la ordenación de burbuja requiere un programa más complejo y tarda aproximadamente el doble de tiempo». (Cita de la primera edición, 1973).
↑ Black, Paul E. (24 de agosto de 2009). "ordenación de burbuja" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Recuperado el 1 de octubre de 2014 .
↑ Knuth, Donald (1997). El arte de la programación informática: Volumen 3: Búsqueda y ordenación . Addison-Wesley. pág. 80. ISBN 0201896850.
↑ Lai Stirland, Sarah (14 de noviembre de 2007). "Obama supera su entrevista con Google" . Wired . Consultado el 27 de octubre de 2020 .
↑ Barack Obama, Eric Schmidt (14 de noviembre de 2007). Barack Obama | Candidatos en Google (Video) (YouTube). Mountain View, CA 94043 The Googleplex: Charlas en Google. El evento tiene lugar a las 23:20. Archivado del original el 7 de septiembre de 2019. Recuperado el 18 de septiembre de 2019 .{{cite AV media}}: CS1 mantenimiento: ubicación ( enlace )

Referencias

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7Problema 2-2, pág. 40.
Clasificación en presencia de predicción de ramificaciones y cachés
Fundamentos de estructuras de datos por Ellis Horowitz, Sartaj Sahni y Susan Anderson-Freed ISBN 81-7371-605-6
Owen Astrachan . Ordenación de burbuja: un análisis algorítmico arqueológico.

Enlaces externos

Martin, David R. (2007). "Algoritmos de ordenación animados: ordenación de burbuja" . Archivado del original el 3 de marzo de 2015.– demostración gráfica
"Ordenación de burbuja de Lafore" . Archivado del original el 19 de enero de 2008. Consultado el 25 de febrero de 2006 .(Animación de applet de Java)
Secuencia OEIS A008302 (Tabla (estadísticas) del número de permutaciones de [n] que necesitan k intercambios de pares durante la clasificación)

[1] Cortesi, Aldo (27 de abril de 2007). "Visualización de algoritmos de ordenación" . Recuperado el 16 de marzo de 2017 .

[2] " [ JDK-6804124 ] (coll) Reemplazar "modified mergesort" en java.util.Arrays.sort con timsort - Java Bug System" . bugs.openjdk.java.net . Consultado el 11 de enero de 2020 .

[3] Peters, Tim (2002-07-20). " [ Python-Dev ] Ordenación" . Recuperado el 2020-01-11 .

[4] "Obituario de Edward Friends (2019) - Washington, DC - The Washington Post" . Legacy.com .

[5] Friend, Edward H. (1956). "Clasificación en sistemas informáticos electrónicos" . Journal of the ACM . 3 (3): 134– 168. doi : 10.1145/320831.320833 . S2CID 16071355 .

[Astrachan2003-6] 1 2 Astrachan, Owen (2003). "Bubble sort: an archaeological algorithmic analysis" (PDF) . ACM SIGCSE Bulletin . 35 (1): 1– 5. doi : 10.1145/792548.611918 . ISSN 0097-8418 .

[7] "jerga, nodo: bogo-sort" . www.jargon.net .

[Knuth-8] Donald Knuth . El arte de la programación informática , Volumen 3: Ordenación y búsqueda , Segunda edición. Addison-Wesley, 1998. ISBN 0-201-89685-0Páginas 106-110 de la sección 5.2.2: Ordenación por intercambio. «Aunque las técnicas empleadas en los cálculos [para analizar el algoritmo de ordenación de burbuja] son instructivas, los resultados son decepcionantes, ya que indican que este algoritmo no es realmente muy bueno. En comparación con la inserción directa […], la ordenación de burbuja requiere un programa más complejo y tarda aproximadamente el doble de tiempo». (Cita de la primera edición, 1973).

[9] Black, Paul E. (24 de agosto de 2009). "ordenación de burbuja" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Recuperado el 1 de octubre de 2014 .

[10] Knuth, Donald (1997). El arte de la programación informática: Volumen 3: Búsqueda y ordenación . Addison-Wesley. pág. 80. ISBN 0201896850.

[11] Lai Stirland, Sarah (14 de noviembre de 2007). "Obama supera su entrevista con Google" . Wired . Consultado el 27 de octubre de 2020 .

[12] Barack Obama, Eric Schmidt (14 de noviembre de 2007). Barack Obama | Candidatos en Google (Video) (YouTube). Mountain View, CA 94043 The Googleplex: Charlas en Google. El evento tiene lugar a las 23:20. Archivado del original el 7 de septiembre de 2019. Recuperado el 18 de septiembre de 2019 .{{cite AV media}}: CS1 mantenimiento: ubicación ( enlace )

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]