Ordenamiento de burbuja - Bubble sort

Ordenamiento de burbuja
Bubblesort-edited-color.svg
Visualización estática de la clasificación de burbujas
Clase Algoritmo de clasificación
Estructura de datos Formación
Rendimiento en el peor de los casos comparaciones, intercambios
Rendimiento en el mejor de los casos comparaciones, intercambios
Rendimiento medio comparaciones, intercambios
Complejidad espacial en el peor de los casos total, auxiliar

La clasificación de burbujas , a veces denominada clasificación descendente , es un algoritmo de clasificación simple que recorre la lista repetidamente, compara elementos adyacentes y los intercambia si están en el orden incorrecto. El paso a través de la lista se repite hasta que se ordena la lista. El algoritmo, que es un tipo de comparación , recibe su nombre de la forma en que los elementos más pequeños o más grandes "burbujean" en la parte superior de la lista.

Este sencillo algoritmo funciona mal en el mundo real y se utiliza principalmente como herramienta educativa. Las bibliotecas de ordenación integradas en lenguajes de programación populares como Python y Java utilizan algoritmos más eficientes, como clasificación rápida , clasificación por tiempo o clasificación por combinación .

Análisis

Un ejemplo de clasificación de burbujas. Comenzando desde el principio de la lista, compare cada par adyacente, intercambie su posición si no están en el orden correcto (el último es más pequeño que el anterior). Después de cada iteración , se necesita comparar un elemento menos (el último) hasta que no queden más elementos para comparar.

Rendimiento

La clasificación de burbujas tiene una complejidad media y en el peor de los casos de О ( n 2 ), donde n es el número de elementos que se ordenan. 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 O ( n  log  n ). Incluso otros algoritmos de ordenación О ( n 2 ), como la ordenación por inserción , generalmente se ejecutan más rápido que la ordenación por burbujas y no son más complejos. Por lo tanto, la clasificación de burbujas no es un algoritmo de clasificación práctico.

La única ventaja significativa que tiene el ordenamiento por burbujas sobre la mayoría de los otros algoritmos, incluso el ordenamiento rápido , pero no el ordenamiento por inserción , es que la capacidad de detectar que la lista está ordenada de manera eficiente está integrada en el algoritmo. Cuando la lista ya está ordenada (en el mejor de los casos), la complejidad de la clasificación de burbujas es solo O ( n ). Por el contrario, la mayoría de los otros algoritmos, incluso aquellos con una mejor complejidad de casos promedio , realizan todo su proceso de clasificación en el conjunto y, por lo tanto, son más complejos. Sin embargo, la ordenación por inserción no solo comparte esta ventaja, sino que también se desempeña mejor en una lista que está sustancialmente ordenada (con una pequeña cantidad de inversiones ). Además, si se desea este comportamiento, se puede agregar trivialmente a cualquier otro algoritmo comprobando la lista antes de que se ejecute el algoritmo.

Conejos y tortugas

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 burbujas 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 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 n −1 pasadas para moverlo al principio. Esto ha llevado a que este tipo de elementos se denominen conejos y tortugas, respectivamente, por los personajes de la fábula de Esopo de La liebre y la tortuga .

Se han realizado varios esfuerzos para eliminar las tortugas para mejorar la velocidad de clasificación de las burbujas. El tipo de cóctel es un tipo de burbuja bidireccional que va de principio a fin, y luego se invierte, de principio a fin. Puede mover tortugas bastante bien, pero conserva la complejidad del peor de los casos O (n 2 ) . La clasificación por peine compara elementos separados por espacios grandes y puede mover a 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 .

Ejemplo paso a paso

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 mayor usando la clasificación de burbujas. En cada paso, se comparan los elementos escritos en negrita . Se requerirán tres pases;

Primer pase
( 5 1 4 2 8) → ( 1 5 4 2 8), aquí, el algoritmo compara los dos primeros elementos y los intercambia desde 5> 1.
(1 5 4 2 8) → (1 4 5 2 8), Intercambiar desde 5> 4
(1 4 5 2 8) → (1 4 2 5 8), Intercambiar desde 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 paso
( 1 4 2 5 8) → ( 1 4 2 5 8)
(1 4 2 5 8) → (1 2 4 5 8), Intercambiar desde 4> 2
(1 2 4 5 8) → (1 2 4 5 8)
(1 2 4 5 8 ) → (1 2 4 5 8 )

Ahora, la matriz ya está ordenada, pero el algoritmo no sabe si está completa. El algoritmo necesita una pasada completa adicional sin ningún cambio para saber que 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 de pseudocódigo

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

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Optimización de la clasificación de burbujas

El algoritmo de clasificación de burbujas se puede optimizar observando que el n -ésimo paso encuentra el n -ésimo elemento más grande y lo coloca en su lugar final. Por lo tanto, el bucle interno puede evitar mirar a la última n - 1 elementos cuando se ejecutan para el n tiempo -ésimo:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

De manera más general, 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 posteriores al último intercambio se ordenan y no es necesario volver a verificarlos. Esto 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 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:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        newn := 0
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                newn := i
            end if
        end for
        n := newn
    until n  1
end procedure

Las modificaciones alternativas, como el tipo de coctelera, intentan mejorar el rendimiento de clasificación de burbujas manteniendo la misma idea de comparar e intercambiar repetidamente elementos adyacentes.

Usar

Ordenamiento de burbuja. La lista se trazó en un sistema de coordenadas cartesianas, y cada punto ( x , y ) indica que el valor y se almacena en el índice x . Luego, la lista se ordenaría por clasificación de burbujas de acuerdo con el valor de cada píxel. Tenga en cuenta que el extremo más grande se ordena primero, y los elementos más pequeños tardan más en moverse a sus posiciones correctas.

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 drásticamente en listas de más de una pequeña cantidad de elementos. Incluso entre los algoritmos de ordenación O ( n 2 ) simples , los algoritmos como el ordenamiento 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 un algoritmo, o un algoritmo de clasificación, a los estudiantes de iniciación a la informática . Sin embargo, algunos investigadores como Owen Astrachan han hecho todo lo posible para desacreditar el tipo de burbujas y su continua popularidad en la educación en ciencias de la computación, recomendando que ya ni siquiera se enseñe.

El archivo de jerga , que llama a bogosort "el algoritmo arquetípico [sic] perversamente horrible", también llama a la clasificación de burbujas "el algoritmo genérico malo". Donald Knuth , en The Art of Computer Programming , concluyó que "el tipo de burbuja 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.

La clasificación de burbujas es asintóticamente equivalente en tiempo de ejecución a la clasificación de inserción en el peor de los casos, pero los dos algoritmos difieren mucho en el número 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 clasificación de burbujas en favor de la clasificació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 errores de predicción de rama . Los experimentos de Astrachan ordenando cadenas en Java muestran que la ordenación de burbujas es aproximadamente un quinto 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 .

En gráficos por computadora, la clasificación de burbujas es popular por su capacidad para detectar un error muy pequeño (como el intercambio de solo dos elementos) en arreglos casi ordenados y solucionarlo con una complejidad lineal (2 n ). Por ejemplo, se utiliza en un algoritmo de relleno de polígono, 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 con el incremento y su orden cambia (dos elementos se intercambian) solo en intersecciones de dos líneas. La clasificación de burbujas es un algoritmo de clasificación estable, como la clasificación por inserción.

Variaciones

  • El ordenamiento impar-par es una versión paralela del ordenamiento de burbujas, para sistemas de paso de mensajes.
  • Los pases pueden ser de derecha a izquierda, en lugar de de izquierda a derecha. Esto es más eficaz para listas con elementos sin clasificar agregados al final.
  • El tipo de coctelera alterna pases hacia la izquierda y hacia la derecha.

Debate sobre el nombre

En ocasiones, se ha hecho referencia al tipo de burbuja como "tipo que se hunde".

Por ejemplo, en The Art of Computer Programming , de Donald Knuth , Volumen 3: Clasificación y búsqueda , afirma en la sección 5.2.1 'Clasificación por inserción', que [el valor] "se asienta en su nivel adecuado" y que este método de clasificación tiene a veces se le ha llamado técnica de cribado 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:

  1. Los valores más grandes pueden considerarse más pesados y, por lo tanto, se puede ver que se hunden progresivamente hasta el final de la lista.
  2. Los valores más pequeños podrían considerarse más ligeros y, por lo tanto, aparecerán progresivamente hasta la parte superior de la lista.

En la cultura popular

En 2007, el ex director ejecutivo de Google, Eric Schmidt, le preguntó al entonces candidato presidencial Barack Obama durante una entrevista sobre la mejor manera de clasificar 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".

Notas

  1. ^ Cortesi, Aldo (27 de abril de 2007). "Visualización de algoritmos de clasificación" . Consultado el 16 de marzo de 2017 .
  2. ^ "[JDK-6804124] (coll) Reemplace" mergesort modificado "en java.util.Arrays.sort con timsort - Java Bug System" . bugs.openjdk.java.net . Consultado el 11 de enero de 2020 .
  3. Peters, Tim (20 de julio de 2002). "Clasificación [Python-Dev]" . Consultado el 11 de enero de 2020 .
  4. a b Astrachan, Owen (2003). "Bubble sort: un análisis algorítmico arqueológico" (PDF) . Boletín ACM SIGCSE . 35 (1): 1–5. doi : 10.1145 / 792548.611918 . ISSN  0097-8418 .
  5. ^ "jerga, nodo: bogo-sort" .
  6. ^ Donald Knuth . El arte de la programación informática , volumen 3: clasificación y búsqueda , segunda edición. Addison-Wesley, 1998. ISBN  0-201-89685-0 . Páginas 106–110 de la sección 5.2.2: Clasificación por intercambio. "[A] unque las técnicas utilizadas en los cálculos [para analizar la clasificación de burbujas] son ​​instructivas, los resultados son decepcionantes, ya que nos dicen que la clasificación de burbujas no es realmente muy buena. En comparación con la inserción directa […], la clasificación de burbujas requiere un programa más complicado y toma aproximadamente el doble de tiempo ". (Cita de la primera edición, 1973.)
  7. ^ Black, Paul E. (24 de agosto de 2009). "tipo burbuja" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Consultado el 1 de octubre de 2014 .
  8. Lai Stirland, Sarah (14 de noviembre de 2007). "Obama pasa su entrevista de Google" . Cableado . Consultado el 27 de octubre de 2020 .
  9. ^ Barack Obama, Eric Schmidt (14 de noviembre de 2007). Barack Obama | Candidatos en Google (Youtube). Mountain View, CA 94043 The Googleplex: Charlas en Google. El evento ocurre a las 23:20. Archivado desde el original (video) el 7 de septiembre de 2019 . Consultado el 18 de septiembre de 2019 .Mantenimiento de CS1: ubicación ( enlace )

Referencias

enlaces externos