Orden de inserción vs algoritmos de ordenación de burbujas

Estoy tratando de entender algunos algoritmos de clasificación, pero estoy luchando por ver la diferencia en el algoritmo de clasificación de burbujas y clasificación de inserción.

Sé que ambos son O (n ² ), pero me parece que la clasificación de burbujas solo burbujea el valor máximo de la matriz en la parte superior para cada pasada, mientras que la clasificación por inserción solo hunde el valor más bajo hacia la parte inferior en cada pasada. ¿No están haciendo exactamente lo mismo pero en diferentes direcciones?

Para la ordenación por inserción, el número de comparaciones / intercambios potenciales comienza en cero y aumenta cada vez (es decir, 0, 1, 2, 3, 4, ..., n) pero para la ordenación por burbujas ocurre el mismo comportamiento, pero al final de la clasificación (es decir, n, n-1, n-2, ... 0) porque la clasificación de burbujas ya no necesita comparar con los últimos elementos a medida que se ordenan.

Sin embargo, por todo esto, parece un consenso que el tipo de inserción es mejor en general. puede alguien decirme por que?

Editar: Estoy principalmente interesado en las diferencias en cómo funcionan los algoritmos, no tanto en su eficiencia o complejidad asintótica.

En la clasificación de burbujas en la iteración ith tiene iteraciones internas ni-1 (n ^ 2) / 2 en total, pero en la ordenación por inserción tiene iteraciones máximas en el paso i'th, pero i / 2 en promedio, ya que puede detener el bucle interno antes, después de encontrar la posición correcta para el elemento actual. Entonces tienes (suma de 0 an) / 2 que es (n ^ 2) / 4 total;

Es por eso que la ordenación por inserción es más rápida que la ordenación por burbujas.

Tipo de inserción

Después de i iteraciones , se ordenan los primeros i elementos.

En cada iteración, el siguiente elemento se burbujea a través de la sección ordenada hasta que llega al lugar correcto:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

El 4 se burbujea en la sección ordenada

Pseudocódigo:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Ordenamiento de burbuja

Después de i iteraciones, los últimos i elementos son los más grandes y están ordenados.

En cada iteración, revise la sección sin clasificar para encontrar el máximo.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

El 5 sale de la sección sin clasificar

Pseudocódigo:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Tenga en cuenta que las implementaciones típicas terminan antes si no se realizan intercambios durante una de las iteraciones del ciclo externo (ya que eso significa que la matriz está ordenada).

Diferencia

En la ordenación por inserción, los elementos se burbujean en la sección ordenada, mientras que en la ordenación por burbujas, los máximos se eliminan de la sección sin clasificar.

Otra diferencia, no vi aquí:

La clasificación de burbujas tiene 3 asignaciones de valor por intercambio : primero debe construir una variable temporal para guardar el valor que desea impulsar (número 1), luego debe escribir la otra variable de intercambio en el lugar donde acaba de guardar el valor de (n. ° 2) y luego debe escribir su variable temporal en el lugar otro lugar (n. ° 3). Tienes que hacer eso para cada lugar (quieres avanzar) para ordenar tu variable en el lugar correcto.

Con la ordenación por inserción , coloca su variable para ordenar en una variable temporal y luego coloca todas las variables delante de ese lugar 1 lugar al revés, siempre que llegue al lugar correcto para su variable. Eso hace 1 asignación de valor por lugar . Al final, escribe su variable temporal en el lugar.

Eso también hace asignaciones de mucho menos valor.

Este no es el mayor beneficio de velocidad, pero creo que se puede mencionar.

Espero, me expresé comprensible, si no, lo siento, no soy un nativo de Gran Bretaña

La principal ventaja de la ordenación por inserción es que es un algoritmo en línea. No es necesario que tenga todos los valores al principio. Esto puede resultar útil cuando se trata de datos procedentes de la red o de algún sensor.

Tengo la sensación de que esto sería más rápido que otros n log(n)algoritmos convencionales . Porque la complejidad sería, por n*(n log(n))ejemplo, leer / almacenar cada valor de stream ( O(n)) y luego ordenar todos los valores ( O(n log(n))) resultando enO(n^2 log(n))

Por el contrario, el uso de Insertar ordenación necesita O(n)leer valores de la secuencia y O(n)colocar el valor en el lugar correcto, por lo que es O(n^2)solo. Otra ventaja es que no necesita búferes para almacenar valores, los ordena en el destino final.

Bubble Sort no está en línea (no puede ordenar un flujo de entradas sin saber cuántos elementos habrá) porque realmente no realiza un seguimiento de un máximo global de elementos ordenados. Cuando se inserta un artículo, deberá comenzar a burbujear desde el principio

Bueno, la clasificación por burbujas es mejor que la clasificación por inserción solo cuando alguien está buscando los k elementos principales de una lista grande de números, es decir, en la clasificación por burbujas después de k iteraciones obtendrá los k elementos principales. Sin embargo, después de k iteraciones en la ordenación por inserción, solo asegura que esos k elementos estén ordenados.

Aunque ambos tipos son O (N ^ 2). Las constantes ocultas son mucho más pequeñas en el tipo de inserción. Las constantes ocultas se refieren al número real de operaciones primitivas realizadas.

¿Cuándo la ordenación por inserción tiene un mejor tiempo de ejecución?

1. La matriz está casi ordenada: observe que la ordenación por inserción realiza menos operaciones en este caso que la ordenación por burbujas.
2. La matriz es de tamaño relativamente pequeño: la ordenación por inserción mueve los elementos para colocar el elemento actual. Esto solo es mejor que la ordenación por burbujas si el número de elementos es reducido.

Tenga en cuenta que la ordenación por inserción no siempre es mejor que la ordenación por burbujas. Para obtener lo mejor de ambos mundos, puede usar la ordenación por inserción si la matriz es de tamaño pequeño, y probablemente fusionar ordenación (o ordenación rápida) para matrices más grandes.

La clasificación de burbujas es casi inútil en todas las circunstancias. En los casos de uso en los que el ordenamiento por inserción puede tener demasiados intercambios, se puede utilizar el ordenamiento por selección porque garantiza menos de N veces de intercambio. Dado que el ordenamiento por selección es mejor que el ordenamiento por burbujas, el ordenamiento por burbujas no tiene casos de uso.

Número de intercambio en cada iteración

• Insertion-sort hace como máximo 1 intercambio en cada iteración .
• Bubble-sort realiza intercambios de 0 an en cada iteración.

Acceder y cambiar la parte clasificada

• La ordenación por inserción accede (y cambia cuando es necesario) la parte ordenada para encontrar la posición correcta de un número en consideración.
• Cuando está optimizado, Bubble-sort no accede a lo que ya está ordenado.

En línea o no

• La ordenación por inserción está en línea. Eso significa que la ordenación por inserción toma una entrada a la vez antes de colocarla en la posición adecuada. No tiene por qué comparar solo adjacent-inputs.
• Bubble-sort no está en línea. No opera una entrada a la vez. Maneja un grupo de entradas (si no todas) en cada iteración. La clasificación de burbujas solo compara e intercambiaadjacent-inputs en cada iteración.

tipo de inserción:

1.En la clasificación de inserción no se requiere el intercambio.

2.La complejidad de tiempo de la ordenación por inserción es Ω (n) para el mejor de los casos y O (n ^ 2) para el peor de los casos.

3. menos complejo en comparación con el tipo de burbuja.

4.ejemplo: insertar libros en la biblioteca, ordenar tarjetas.

clasificación de burbujas: 1.Se requiere intercambio en la clasificación de burbujas.

2.La complejidad temporal de la clasificación de burbujas es Ω (n) para el mejor de los casos y O (n ^ 2) para el peor de los casos.

3.más complejo en comparación con el tipo de inserción.

La ordenación por inserción se puede reanudar como " Busque el elemento que debería estar en la primera posición (el mínimo), haga algo de espacio cambiando los elementos siguientes y colóquelo en la primera posición. Bien. Ahora mire el elemento que debería estar en la 2ª. ... "y así sucesivamente ...

La clasificación de burbujas funciona de manera diferente, lo que puede reanudarse como " Siempre que encuentre dos elementos adyacentes que estén en el orden incorrecto, los cambio ".