algorithm - metodos - ordenamiento burbuja python

Clasificación de inserción vs Algoritmos de clasificación de burbujas (10)

Estoy tratando de entender algunos algoritmos de ordenamiento, pero estoy luchando para ver la diferencia en el algoritmo de ordenación de inserción y tipo de burbuja.

Sé que ambos son O (n ² ), pero me parece que el tipo burbuja simplemente hace burbujear el valor máximo de la matriz en la parte superior de cada pasada, mientras que la ordenación de inserción simplemente baja el valor más bajo al final de cada pase. ¿No están haciendo exactamente lo mismo pero en diferentes direcciones?

Para el ordenamiento por inserción, el número de comparaciones / swaps potenciales comienza en cero y aumenta cada vez (es decir, 0, 1, 2, 3, 4, ..., n), pero para la clasificación de burbujas ocurre el mismo comportamiento, pero al final de la ordenación (es decir, n, n-1, n-2, ... 0) porque el ordenamiento 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 género de inserción es mejor en general. puede alguien decirme por que?

Editar: estoy interesado principalmente en las diferencias en el funcionamiento de los algoritmos, no tanto en su eficacia o complejidad asintótica.

Número de intercambio en cada iteración

Insertion-sort hace como máximo 1 intercambio en cada iteración .
Bubble-sort hace 0 a n swaps en cada iteración.

Acceder y cambiar la parte ordenada

Inserción: ordena los accesos (y cambia cuando sea 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

Insertion-sort está en línea. Eso significa que Insertion-sort toma una entrada a la vez antes de colocarla en la posición adecuada. No tiene que 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. Bubble-sort solo compara y intercambia adjacent-inputs en cada iteración.

Tipo de inserción

Después de iteraciones, los primeros i elementos están ordenados.

En cada iteración, el siguiente elemento se burbujea a través de la sección ordenada hasta que alcanza el 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 iteraciones, los últimos i elementos son los más grandes y ordenados.

En cada iteración, revisa 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 se bordea 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 finalizan anticipadamente 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 inserción, los elementos de clasificación se burbujean en la sección ordenada, mientras que en la ordenación de burbuja, los máximos se eliminan de la sección sin clasificar.

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

Cuando la ordenación por inserción tiene un mejor tiempo de ejecución?

La matriz está casi ordenada: observe que la ordenación de inserción hace menos operaciones en este caso, que sort de burbuja.
La matriz es de un tamaño relativamente pequeño: la ordenación por inserción mueve los elementos alrededor, para poner el elemento actual. Esto es solo mejor que la ordenación de burbuja si la cantidad de elementos es poca.

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 de inserción si la matriz es de pequeño tamaño, y probablemente fusione la ordenación (o vía rápida) para matrices más grandes.

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

El tipo de inserción se puede reanudar como " Busque el elemento que debe estar en la primera posición (el mínimo), haga un poco de espacio desplazando los siguientes elementos y colóquelo en la primera posición. Bien. Ahora mire el elemento que debería estar en 2da. ... "y así sucesivamente ...

La clasificación de las burbujas funciona de manera diferente, y se puede reanudar como " Siempre que encuentre dos elementos adyacentes que están en el orden incorrecto, los cambio ".

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

Es por eso que el ordenamiento por inserción es más rápido que el tipo de burbuja.

La clasificación de burbujas es casi inútil en cualquier circunstancia. En los casos de uso cuando la ordenación por inserción puede tener demasiados cambios, se puede utilizar la ordenación por selección porque garantiza menos de N veces de intercambio. Debido a que la ordenación por selección es mejor que la clasificación por burbuja, la clasificación por burbuja no tiene casos de uso.

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

La principal ventaja del tipo insertar es que es un algoritmo en línea. No necesita tener todos los valores al inicio. Esto podría ser útil cuando se trata de datos provenientes de la red o de algún sensor.

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

Por el contrario, utilizar Insert Sort necesita O(n) para leer los valores de la secuencia y O(n) para poner el valor en el lugar correcto, por lo tanto, es O(n^2) solamente. Otra ventaja es que no necesita almacenamientos intermedios para almacenar valores, sino que los ordena en el destino final.

Otra diferencia, no he visto aquí:

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

Con la ordenación por inserción , coloque su variable en una variable temporal y luego coloque todas las variables delante de ese punto 1 hacia atrás, siempre y cuando llegue al lugar correcto para su variable. Eso hace 1 asignación de valor por punto . Al final, escribe tu variable temporal en el lugar.

Eso hace asignaciones de valor mucho menos, también.

Este no es el beneficio de velocidad más fuerte, pero creo que se puede mencionar.

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