¿Cuáles son algunas aplicaciones del algoritmo de clasificación de burbujas?

Si tiene un conjunto de clasificación muy pequeño, entonces el O (n ^ 2) no hace mucho daño y desea minimizar el espacio de código, ya que los algoritmos de clasificación más sofisticados implican mucho más código. Un buen ejemplo sería un pequeño dispositivo integrado en el que desea mantener el tamaño del código lo más pequeño posible.

Encontré una aplicación no convencional del tipo burbuja en mi investigación una vez: el ordenamiento de operadores en la teoría cuántica de campos.

En la teoría cuántica de campos, con frecuencia encuentras cadenas de operadores:

[matemáticas] a ^ {\ daga} \ b ^ {\ daga} \ c ^ {\ daga} \ d ^ {\ daga} \ [/ matemática].

Un operador como [math] a ^ {\ dagger} [/ math] crea una partícula en el estado cuántico [math] | a \ rangle [/ math]. Cuando la partícula es un fermión (como un electrón), estos operadores tienen la propiedad de que el intercambio de dos operadores vecinos introduce un signo menos:

[matemáticas] a ^ {\ dagger} \ c ^ {\ dagger} \ b ^ {\ dagger} \ = – a ^ {\ dagger} \ b ^ {\ dagger} \ c ^ {\ dagger} \ [/ math ]

Nuestro grupo de investigación estaba trabajando en un método que generaba sumas de muchas permutaciones de los mismos operadores; es decir, cada término de la suma contenía el mismo conjunto de operadores en un orden diferente. Nuestra pregunta era: ¿se cancelan entre sí todos los términos de la suma o queda algo?

Por ejemplo,

[matemáticas] a ^ {\ dagger} \ c ^ {\ dagger} \ b ^ {\ dagger} + a ^ {\ dagger} \ b ^ {\ dagger} \ c ^ {\ dagger} \ = 0 [/ math ],

pero

[matemática] c ^ {\ dagger} \ a ^ {\ dagger} \ b ^ {\ dagger} + a ^ {\ dagger} \ b ^ {\ dagger} \ c ^ {\ dagger} \ = 2 \ cdot a ^ {\ dagger} \ b ^ {\ dagger} \ c ^ {\ dagger} \ [/ math].

Los términos en la primera suma difieren en un número impar de intercambios, pero los términos en la segunda suma difieren en un número par. Es bastante fácil calcular estas dos sumas a mano, pero si tiene una suma de 10,000 permutaciones de 100 operadores, el problema es un poco más difícil de resolver mediante inspección.

Una forma de resolver el problema es ordenar cada una de las permutaciones y realizar un seguimiento de la cantidad de veces que tuvimos que intercambiar operadores vecinos. Si se necesita un número par de intercambios para ordenar una permutación y un número impar para ordenar otra, esos dos términos de la suma se cancelan; de lo contrario, se suman.

El tipo de burbuja era ideal para nuestra tarea. Simplemente agregamos una variable a un algoritmo de clasificación de burbujas para realizar un seguimiento de si hubo un número par o impar de intercambios durante la clasificación. El valor de esta variable fue todo lo que necesitábamos para evaluar nuestras enormes sumas de productos de operador.

Podríamos haber implementado un algoritmo de clasificación más rápido, pero la sobrecarga habría sido mayor, habría llevado más tiempo implementarlo, y el aumento en la velocidad de clasificación no era importante. Como con la mayoría de las otras aplicaciones mencionadas en las otras respuestas, la clasificación de burbujas fue lo suficientemente rápida. Su simplicidad y estabilidad fueron más importantes que su rendimiento.

Respuesta corta: ninguna.
Más tiempo: si los elementos que se van a ordenar ya están ordenados, entonces Bubble Sort es tan eficiente como el método de inserción y más eficiente que la mayoría de los otros tipos. Sin embargo, ese es un nicho de mercado.
Sin embargo, si el conjunto de datos se ordena en orden inverso, entonces Bubble Sort no tiene nada que recomendar, ya que la mayoría de los otros tipos serán más rápidos.

En gráficos de computadora es popular por su capacidad de detectar un error muy pequeño (como el intercambio de solo dos elementos) en arreglos casi ordenados y arreglarlo con una complejidad lineal (2n). Por ejemplo, se usa en un algoritmo de relleno de polígonos, donde las líneas de delimitación 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 lineas. La ordenación de burbujas es un algoritmo de ordenación estable, como la ordenación por inserción.

1: Enseñar que no todos los algoritmos de clasificación son buenos.
2: Dé una introducción fácil a los algoritmos de clasificación.
3: Arte:

Suponga que tengo una lista de objetos para elegir en una pantalla, y tengo una funcionalidad para reordenar esa lista marcando un elemento y moviéndolo hacia arriba o hacia abajo haciendo clic en un botón “arriba” o “abajo”, la mejor manera de tenga en cuenta que es intercambiando ese elemento con su vecino superior o inferior. Si clasifico dicha lista manualmente usando estos widgets, esencialmente realizaré una clasificación de burbujas.

Es una técnica de clasificación fácil de aprender para ‘principiantes en la codificación’