algorithm - ¿Para qué sirve una burbuja?
language-agnostic sorting (16)
¿Los géneros de burbujas tienen un uso real? Cada vez que veo uno mencionado, siempre es:
- Un algoritmo de clasificación para aprender.
- Un ejemplo de algoritmo de clasificación que no se debe usar.
Creo que es un buen algoritmo de "enseñanza" porque es muy fácil de comprender e implementar. También puede ser útil para pequeños conjuntos de datos por la misma razón (aunque algunos de los algoritmos O (n lg n) también son bastante fáciles de implementar).
Depende de la forma en que se distribuyan sus datos, si puede hacer algunas suposiciones.
Uno de los mejores enlaces que he encontrado para entender cuándo usar una ordenación de burbujas - o de algún otro tipo, es esta - una vista animada de los algoritmos de clasificación:
El tipo de burbuja es (probablemente) el tipo más rápido disponible en circunstancias muy específicas. Originalmente se hizo conocido principalmente porque era uno de los primeros algoritmos (de cualquier tipo) que se analizaba rigurosamente, y se encontró la prueba de que era óptimo bajo sus circunstancias limitadas.
Considere un archivo almacenado en una unidad de cinta y tan poca memoria de acceso aleatorio (o teclas tan grandes) que solo puede cargar dos registros en la memoria en un momento dado. El rebobinado de la cinta es lo suficientemente lento como para hacer acceso aleatorio dentro del archivo, por lo general, no es práctico; si es posible, desea procesar registros secuencialmente, no más de dos a la vez.
Cuando las unidades de cinta eran comunes, y las máquinas con solo unos pocos miles (palabras | bytes) de RAM (de cualquier tipo) eran comunes, eso era lo suficientemente realista como para merecer la pena estudiar. Esa circunstancia es ahora rara, por lo que estudiar sortear burbujas tiene poco sentido, pero lo que es peor, las circunstancias en las que es óptimo no se enseñan de todos modos, por lo tanto, incluso si surgiera la situación correcta, casi nadie se daría cuenta .
En cuanto a ser el más rápido en un conjunto de datos extremadamente pequeño y / o casi clasificado, mientras que eso puede encubrir la debilidad del tipo de burbuja (al menos hasta cierto punto), una ordenación por inserción esencialmente siempre será mejor para cualquiera de los dos aquellos.
Encontré un gran uso en una anécdota de optimización recientemente. Un programa necesitaba un conjunto de sprites ordenados en profundidad para cada cuadro. El orden de los spites no cambiaría mucho entre fotogramas, por lo que, como optimización, se sortearon con una sola pasada en cada fotograma. Esto se hizo en ambas direcciones (de arriba a abajo y de abajo hacia arriba). Por lo tanto, los sprites siempre estaban casi clasificados con un algoritmo O (N) muy eficiente.
Es bueno para pequeños conjuntos de datos, razón por la cual algunas implementaciones de qsort cambian a él cuando el tamaño de la partición es pequeño. Pero la ordenación por inserción es aún más rápida, por lo que no hay una buena razón para usarla, excepto como ayuda para la enseñanza.
Es el tipo que uso más a menudo en realidad. (En nuestro proyecto, no podemos usar ninguna biblioteca externa).
Es útil cuando sé con certeza que el conjunto de datos es realmente pequeño, por lo que no me importa un poco la velocidad y quiero el código más corto y simple.
La burbuja no es lo más bajo que puedes ir. Recientemente, estaba en una situación en la que necesitaba ordenar exactamente tres elementos. Escribí algo como esto:
// Use sort of stooge to sort the three elements by cpFirst
SwapElementsIfNeeded(&elementTop, &elementBottom);
SwapElementsIfNeeded(&elementTop, &elementMiddle);
SwapElementsIfNeeded(&elementMiddle, &elementBottom);
*pelement1 = elementTop;
*pelement2 = elementMiddle;
*pelement3 = elementBottom;
Es rápido y fácil de codificar y (casi imposible de hacer mal). Tiene su lugar si no está haciendo trabajos pesados y no hay soporte de clasificación de bibliotecas.
Mayormente nada . Use QuickSort o SelectionSort en su lugar ...!
No puedo resistirme a responder a cualquier comentario sobre sortear burbuja mencionando el más rápido (parece ser O (nlogn), pero esto no está realmente probado) Comb Sort . Tenga en cuenta que Comb sort es un poco más rápido si usa una tabla precalculada. Comb sort es exactamente igual a sort de burbuja, excepto que inicialmente no comienza intercambiando elementos adyacentes. Es casi tan fácil de implementar / entender como sort de burbuja.
No se usa mucho en el mundo real. Es una buena herramienta de aprendizaje porque es fácil de entender y rápida de implementar . Tiene un mal (O (n ^ 2)) peor caso y un rendimiento promedio. Tiene un buen rendimiento en el mejor de los casos cuando sabes que los datos están casi ordenados, pero hay muchos otros algoritmos que tienen esta propiedad, con el mejor peor rendimiento y el peor de los casos.
Oh sí, es un buen mecanismo de selección. Si lo encuentras en un código escrito por alguien, no lo contratas.
Probablemente sea el más rápido para conjuntos pequeños .
Hablando de educación. Un enlace a la última escena de clasificación , es increíble. Debes verlo.
Solía usarlo en algunos casos para N pequeña en el modelo 1 de TRS-80. Utilizando un bucle for, se podía implementar la ordenación completa en una línea de programa.
Aparte de eso, es bueno para la enseñanza, y a veces para las listas que están casi en orden ordenado.
Una vez lo usé para un caso en el que la gran mayoría de las veces sería ordenar dos elementos.
La próxima vez que vi ese código, alguien lo reemplazó con el tipo de biblioteca. ¡Espero que lo hayan comparado primero!
La clasificación de burbujas es fácil de implementar y es lo suficientemente rápida cuando tienes pequeños conjuntos de datos.
La clasificación de burbujas es lo suficientemente rápida cuando el conjunto está casi ordenado (por ejemplo, uno o varios elementos no están en las posiciones correctas), en este caso es mejor entrelazar los traverses del índice 0 al índice n y del índice n al índice 0 . El uso de C ++ se puede implementar de la siguiente manera:
void bubbleSort(vector<int>& v) { // sort in ascending order
bool go = true;
while (go) {
go = false;
for (int i = 0; i+1 < v.size(); ++i)
if (v[i] > v[i+1]) {
swap(v[i], v[j]);
go = true;
}
for (int i = (int)v.size()-1; i > 0; --i)
if (v[i-1] > v[i]) {
swap(v[i-1], v[i]);
go = true;
}
}
}
Puede ser bueno si el intercambio de dos elementos adyacentes es un chip y el intercambio de elementos arbitrarios es costoso.
Dado que este algoritmo es fácil de implementar, es fácil de admitir, y es importante en el ciclo de vida real de la aplicación reducir el esfuerzo de soporte.
Recientemente utilizamos bubblesort en una prueba de optimalidad para un algoritmo. Tuvimos que transformar una solución óptima arbitraria representada por una secuencia de objetos en una solución que fue encontrada por nuestro algoritmo. Debido a que nuestro algoritmo era solo "Ordenar por este criterio", tuvimos que demostrar que podemos ordenar una solución óptima sin empeorarla. En este caso, sort de burbuja fue un muy buen algoritmo para usar, porque tiene la buena invariante de simplemente intercambiar dos elementos que están uno al lado del otro y están en el orden incorrecto. Usando algoritmos más complicados, habría derretido cerebros, creo.
Saludos.