Clasificación de burbujas
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.
PerformanceEdit
La clasificación de burbujas tiene el peor de los casos y la complejidad media de О (n2), 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 clasificación О (n2), 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 lo tanto, la clasificación de burbujas no es un algoritmo de clasificación práctico.
La única ventaja significativa que la clasificación de burbujas tiene sobre la mayoría de los otros algoritmos, incluso la clasificación rápida, pero no la clasificación por inserción, es que la capacidad de detectar que la lista está ordenada está integrado de manera eficiente en el algoritmo. Cuando la lista ya está ordenada (en el mejor de los casos), la complejidad de la ordenació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.
Se debe evitar la clasificación de burbujas en el caso de colecciones grandes. No será eficiente en el caso de una colección en orden inverso.
Conejos y tortugasEditar
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 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 moverá 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 estos tipos de elementos se llamen conejos y tortugas, respectivamente, en honor a los personajes de la fábula de Esopo La tortuga y la liebre.
Varios Se han hecho esfuerzos para eliminar las tortugas para mejorar la velocidad de clasificación de 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 (n2). 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 pasoEditar
Tome una matriz de números «5 1 4 2 8» y ordene la matriz desde el más bajo número al mayor número utilizando la clasificación de burbujas. En cada paso, se comparan los elementos escritos en negrita. Se requerirán tres pasadas;
Primera pasada (5 1 4 2 8) → (1 5 4 2 8), aquí, el algoritmo compara los dos primeros elementos e 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), Swap since 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Ahora, dado que estos elementos ya están en orden (8 > 5), el algoritmo no los intercambia. Segunda pasada (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 sin ningún intercambio para saber que está ordenado.