Estoy haciendo mi revisión para el examen.Tipo de inserción mejor que Tipo de burbuja?
Me gustaría saber en qué condiciones la ordenación por inserción se comporta mejor que sort de burbuja dada la misma complejidad de caso promedio de O (N^2).
Encontré algunos artículos relacionados, pero no puedo entenderlos.
¿Alguien le importaría explicarlo de una manera simple?
supongo que la respuesta que está buscando es here:
ordenamiento de burbuja también puede ser utilizado eficientemente en una lista que ya está ordenados a excepción de un pequeño número de elementos. Por ejemplo, si solo un elemento no está en orden, la ordenación de burbuja tomará solo 2n de tiempo. Si dos elementos no están en orden, ordenamiento de burbuja va a tomar sólo como máximo tiempo ... 3n
y
La ordenación por inserción es un sencillo algoritmo de ordenación que es relativamente eficiente para pequeñas listas y en su mayoría ordenados listas, y se utiliza a menudo como parte de algoritmos más sofisticados
la ventaja de BubbleSort está en la velocidad de la detección de una ya sorte Lista D:
BubbleSort Mejor Caso Escenario: O (n)
Sin embargo, incluso en este caso la inserción especie mejoró mismo rendimiento /.
BubbleSort es, más o menos, sólo es bueno para la comprensión y/o enseñar el mecanismo de sortalgorithm, pero no encontrará un uso adecuado en la programación de estos días, debido a su complejidad
O (N ²)
significa que su eficacia disminuye drásticamente en listas de más de un pequeño número de elementos.
"bubblesort es solo bueno para comprender y/o enseñar el mecanismo del algoritmo de ordenación" - ni siquiera eso, diría yo. El tipo de inserción no es más difícil de entender y no es mucho más difícil de codificar. El tipo de burbuja tiene una ventaja muy específica, que es probablemente el más eficiente para un tipo particular de almacenamiento que no tiene acceso aleatorio. Almacenamiento del tambor, creo, donde el tambor gira a velocidad constante en una sola dirección. Luego supera la ordenación por inserción porque la ordenación por inserción necesita "mirar hacia atrás", lo cual es muy lento. ¡Esta ventaja rara vez es de uso práctico en estos días! –
Siguiendo las cosas vinieron a mi mente:
ordenamiento de burbuja siempre toma una más pase matriz para determinar si se trata de resolver el problema. Por otro lado, la ordenación por inserción no necesita esto: una vez que se inserta el último elemento, el algoritmo garantiza que la matriz esté ordenada.
Tipo de burbuja hace n comparaciones en cada pase. El tipo de inserción hace menos de n comparaciones: una vez que el algoritmo encuentra la posición donde insertar el elemento actual, deja de hacer comparaciones y toma el siguiente elemento.
Por último, cita de wikipedia artículo:
ordenamiento de burbuja también interactúa mal con el hardware de la CPU moderna. Es requiere al menos el doble de escrituras que la ordenación por inserción, dos veces como muchas omisiones de caché y asintóticamente más errores de predicción de ramas. Los experimentos realizados por Astrachan clasificación cadenas en Java muestran ordenamiento de burbuja a ser aproximadamente 5 veces más lenta que la ordenación por inserción y un 40% más lento que ordenación por selección
puede encontrar un enlace a trabajo de investigación original de allí.
gracias Victor. Encontré los primeros 2 puntos realmente útiles. Ahora entiendo que una diferencia fundamental entre los 2 algoritmos es el número de comparaciones requeridas. Cheers – Jonathan
El segundo punto parece ser incorrecto. Sí, algunos algoritmos hacen eso. Pero creo que en el algoritmo de ordenación de burbuja correcto, el ciclo interno ejecuta n-1, n-2, n-3 .... veces en cada iteración del ciclo externo. –
¿Podría proporcionar enlaces a los artículos relacionados que no comprende? No estoy seguro de qué aspectos podrían estar abordando. Aparte de eso, existe una diferencia teórica que podría ser que el ordenamiento de burbuja es más adecuado para colecciones representadas como matrices (que para aquellas representadas como listas vinculadas), mientras que el ordenamiento de inserción es adecuado para listas vinculadas.
El razonamiento sería que la ordenación de burbujas siempre intercambia dos elementos a la vez que son triviales tanto en matriz como en lista vinculada (más eficiente en matrices), mientras que la inserción ordena inserta en un lugar de una lista dada que es trivial para listas vinculadas, pero implica mover todos los elementos posteriores en una matriz a la derecha.
Dicho esto, tómelo con un grano de sal. En primer lugar, ordenar matrices es, en la práctica, casi siempre más rápido que ordenar listas vinculadas. Simplemente debido al hecho de que escanear la lista una vez ya tiene una enorme diferencia. Aparte de eso, mover n elementos de una matriz a la derecha es mucho más rápido que realizar n (o incluso n/2) intercambios. Esta es la razón por la que otras respuestas afirman correctamente que la ordenación por inserción es superior en general, y por qué realmente me pregunto acerca de los artículos que lees, porque no creo una manera simple de decir que esto sea mejor en los casos A, y eso es mejor en casos B.
El ordenamiento de burbuja puede ser más adecuado para las matrices que el ordenamiento de burbuja para las listas vinculadas, pero el ordenamiento de burbuja no es más apropiado para las matrices que la ordenación de inserción para las matrices. –
Sí, tal vez no estaba lo suficientemente claro en el último párrafo. La cuestión es que el tipo de burbuja es conceptualmente trivial en las matrices, mientras que la ordenación de inserción no lo es ("mover todo de x a la derecha"). Todavía es cierto, que esto no hace que las burbujas se clasifiquen más rápido. –
por lo que, por ejemplo, una lista ordenada en su mayoría: por ejemplo [2,3,4,5,1] clasificación de burbuja necesita 4 intercambios y 4 comparaciones La ordenación por inserción necesita 4 intercambios y 4 comparaciones también. ¿cuál es la diferencia? – Jonathan
en ese ejemplo particular no hay diferencia :) – MarcoS