Orden de inserción frente a orden de selección

Estoy tratando de comprender las diferencias entre el ordenamiento por inserción y el ordenamiento por selección.

Ambos parecen tener dos componentes: una lista sin clasificar y una lista ordenada. Ambos parecen tomar un elemento de la lista sin clasificar y colocarlo en la lista ordenada en el lugar correcto. He visto algunos sitios / libros que dicen que el ordenamiento por selección hace esto intercambiando uno a la vez, mientras que el ordenamiento por inserción simplemente encuentra el lugar correcto y lo inserta. Sin embargo, he visto otros artículos decir algo, que dicen que el tipo de inserción también cambia. En consecuencia, estoy confundido. ¿Existe alguna fuente canónica?

Orden de selección:

Dada una lista, tome el elemento actual y cámbielo por el elemento más pequeño en el lado derecho del elemento actual.

Tipo de inserción:

Dada una lista, tome el elemento actual e insértelo en la posición apropiada de la lista, ajustando la lista cada vez que inserte. Es similar a ordenar las cartas en un juego de cartas.

La complejidad temporal del ordenamiento por selección es siempre n(n - 1)/2, mientras que el ordenamiento por inserción tiene una mayor complejidad temporal que su peor complejidad n(n - 1)/2. Por lo general, entonces se necesitarán comparaciones menores o iguales n(n - 1)/2.

Fuente: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Tanto la ordenación por inserción como la ordenación por selección tienen un bucle externo (sobre cada índice) y un bucle interno (sobre un subconjunto de índices). Cada pasada del bucle interno expande la región ordenada en un elemento, a expensas de la región no ordenada, hasta que se agotan los elementos no clasificados.

La diferencia está en lo que hace el bucle interno:

• En la ordenación por selección, el bucle interno se encuentra sobre los elementos no clasificados . Cada pasada selecciona un elemento y lo mueve a su ubicación final (en el extremo actual de la región ordenada).

• En la ordenación por inserción, cada pasada del bucle interno itera sobre los elementos ordenados . Los elementos ordenados se desplazan hasta que el bucle encuentra el lugar correcto para insertar el siguiente elemento sin clasificar.

Por lo tanto, en una ordenación por selección, los elementos ordenados se encuentran en el orden de salida y permanecen así una vez que se encuentran. Por el contrario, en una ordenación por inserción, los elementos no clasificados permanecen en su lugar hasta que se consumen en el orden de entrada, mientras que los elementos de la región ordenada siguen moviéndose.

En lo que respecta al intercambio: la clasificación por selección hace un intercambio por pasada del bucle interno. La ordenación por inserción generalmente guarda el elemento que se insertará como temp antes del bucle interno, dejando espacio para que el bucle interno cambie los elementos ordenados hacia arriba en uno y luego los copie tempen el punto de inserción.

CLASIFICACIÓN DE SELECCIÓN
Suponga que hay una matriz de números escritos de una manera particular / aleatoria y digamos que vamos a organizar en orden creciente ... así que, tome un número a la vez y reemplácelo con el no más pequeño. disponible en la lista. Al hacer este paso, finalmente obtendremos el resultado deseado.

CLASIFICACIÓN DE INSERCIÓN
Teniendo en cuenta la suposición similar, pero la única diferencia es que esta vez estamos seleccionando un número a la vez e insertándolo en la parte preclasificada, lo que reduce las comparaciones y, por lo tanto, es más eficiente.

Es posible que la confusión se deba a que está comparando una descripción de ordenar una lista vinculada con una descripción de ordenar una matriz . Pero no puedo estar seguro, ya que no citó sus fuentes.

La forma más fácil de entender los algoritmos de clasificación es a menudo obtener una descripción detallada del algoritmo (no cosas vagas como "este tipo usa intercambio. En algún lugar. No estoy diciendo dónde"), obtenga algunas cartas (5-10 debería ser suficiente para algoritmos de ordenación simples) y ejecute el algoritmo a mano.

Orden de selección: escanee los datos sin clasificar en busca del elemento restante más pequeño, luego cámbielo a la posición inmediatamente siguiente a los datos ordenados. Repite hasta terminar. Si ordena una lista, no necesita intercambiar el elemento más pequeño en su posición, puede eliminar el nodo de la lista de su posición anterior e insertarlo en la nueva.

Orden de inserción: tome el elemento que sigue inmediatamente a los datos ordenados, escanee los datos ordenados para encontrar el lugar donde colocarlo y colóquelo allí. Repite hasta terminar.

La ordenación por inserción puede usar swap durante su fase de "escaneo", pero no tiene por qué hacerlo y no es la forma más eficiente a menos que esté ordenando una matriz de un tipo de datos que: (a) no se puede mover, solo copiar o intercambiar; y (b) es más caro copiar que intercambiar. Si la ordenación por inserción usa swap, la forma en que funciona es que simultáneamente busca el lugar y coloca el nuevo elemento allí, intercambiando repetidamente el nuevo elemento con el elemento inmediatamente anterior, siempre que el elemento anterior sea más grande que eso. Una vez que llega a un elemento que no es más grande, ha encontrado la ubicación correcta y pasa al siguiente elemento nuevo.

La lógica de ambos algoritmos es bastante similar. Ambos tienen una submatriz parcialmente ordenada al principio de la matriz. La única diferencia es cómo buscan el siguiente elemento para colocarlo en la matriz ordenada.

• Orden de inserción : inserta el siguiente elemento en la posición correcta;

• Orden de selección : selecciona el elemento más pequeño y lo intercambia con el elemento actual;

Además, la ordenación por inserción es estable, a diferencia de la ordenación por selección .

Implementé ambos en Python, y vale la pena señalar lo similares que son:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Con un pequeño cambio es posible realizar el algoritmo de ordenación por selección.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

En pocas palabras, creo que la clasificación de selección busca primero el valor más pequeño en la matriz y luego realiza el intercambio, mientras que la clasificación de inserción toma un valor y lo compara con cada valor que le queda (detrás de él). Si el valor es menor, se intercambia. Luego, el mismo valor se compara nuevamente y si es menor que el que está detrás, se intercambia nuevamente. ¡Espero que tenga sentido!

En breve,

Orden de selección: seleccione el primer elemento de la matriz sin clasificar y compárelo con los elementos restantes sin clasificar. Es similar a la clasificación de burbujas, pero en lugar de intercambiar cada elemento más pequeño, mantiene actualizado el índice de elemento más pequeño y lo intercambia al final de cada ciclo .

Ordenación por inserción: es opuesta a la ordenación por selección, donde elige el primer elemento de la submatriz no ordenada y lo compara con la submatriz ordenada e inserta el elemento más pequeño donde se encuentra y desplaza todos los elementos ordenados de su derecha al primer elemento no ordenado.

Lo intentaré de nuevo: considere lo que sucede en el caso afortunado de una matriz casi ordenada.

Al ordenar, se puede pensar que la matriz tiene dos partes: lado izquierdo - ordenado, lado derecho - sin clasificar.

Ordenación por inserción: elija el primer elemento sin clasificar e intente encontrar un lugar para él entre la parte ya ordenada. Dado que busca de derecha a izquierda, es muy posible que el primer elemento ordenado con el que está comparando (el más grande, el más a la derecha en la parte izquierda) sea más pequeño que el elemento elegido, por lo que puede continuar inmediatamente con el siguiente elemento sin clasificar.

Orden de selección: elija el primer elemento sin clasificar e intente encontrar el elemento más pequeño de toda la parte sin clasificar, e intercambie esos dos si lo desea. El problema es que, dado que la parte correcta no está clasificada, debes pensar en todos los elementos cada vez, ya que no puedes estar seguro de si hay o no un elemento más pequeño que el elegido.

Por cierto, esto es exactamente lo que mejora heapsort en el ordenamiento por selección: es capaz de encontrar el elemento más pequeño mucho más rápidamente debido al montón .

Orden de selección: a medida que comienza a construir la sublista ordenada, el algoritmo asegura que la sublista ordenada esté siempre completamente ordenada, no solo en términos de sus propios elementos, sino también en términos de la matriz completa, es decir, tanto la sublista ordenada como la no ordenada. Por lo tanto, el nuevo elemento más pequeño, una vez encontrado en la sublista sin clasificar, se agregaría al final de la sublista ordenada.

Orden de inserción: el algoritmo vuelve a dividir la matriz en dos partes, pero aquí el elemento se selecciona de la segunda parte y se inserta en la posición correcta en la primera parte. Esto nunca garantiza que la primera parte esté ordenada en términos de la matriz completa, aunque, por supuesto, en la pasada final cada elemento está en su posición ordenada correcta.

Ambos algoritmos generalmente funcionan así

Paso 1: tome el siguiente elemento sin clasificar de la lista sin clasificar y luego

Paso 2: colóquelo en el lugar correcto de la lista ordenada.

Uno de los pasos es más fácil para un algoritmo y viceversa.

Ordenación por inserción : tomamos el primer elemento de la lista no ordenada, lo colocamos en la lista ordenada, en algún lugar . Sabemos dónde llevar el siguiente elemento (la primera posición en la lista sin clasificar), pero requiere algo de trabajo encontrar dónde colocarlo (en algún lugar ). El paso 1 es sencillo.

Orden de selección : tomamos el elemento en algún lugar de la lista no ordenada, luego lo colocamos en la última posición de la lista ordenada. Necesitamos encontrar el siguiente elemento (lo más probable es que no esté en la primera posición de la lista sin clasificar, sino en algún lugar ) y luego ponerlo al final de la lista ordenada. El paso 2 es fácil

El bucle interno del ordenamiento por inserción pasa por elementos ya ordenados (al contrario del ordenamiento por selección). Esto le permite abortar el bucle interno cuando se encuentra la posición correcta . Lo que significa que:

1. El bucle interno atravesará solo la mitad de sus elementos en un caso promedio.
2. El bucle interno se cancelará incluso antes si la matriz está casi ordenada.
3. El bucle interno abortará inmediatamente si la matriz ya está ordenada, haciendo que la complejidad de la ordenación por inserción sea lineal en este caso.

La clasificación por selección siempre tendrá que pasar por todos los elementos del bucle interno. Es por eso que la ordenación por inserción se prefiere principalmente a la ordenación por selección. Pero, por otro lado, la ordenación por selección realiza muchos menos intercambios de elementos, lo que podría ser más importante en algunos casos.

Básicamente, la ordenación por inserción funciona comparando dos elementos a la vez y la ordenación por selección selecciona el elemento mínimo de toda la matriz y lo ordena.

Conceptualmente, la ordenación por inserción sigue ordenando la sublista comparando dos elementos hasta que se ordena toda la matriz, mientras que la ordenación por selección selecciona el elemento mínimo y lo cambia a la primera posición, segundo elemento mínimo a la segunda posición y así sucesivamente.

El orden de inserción se puede mostrar como:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

El orden de selección se puede mostrar como:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

La elección de estos 2 algoritmos de clasificación se reduce a la estructura de datos utilizada.

Cuando esté usando matrices, use la ordenación por selección (aunque ¿por qué, cuando puede usar qsort?). Cuando utilice listas vinculadas, utilice la ordenación por inserción.

Esto es porque:

• El recorrido de lista enlazada es más caro que las matrices.
• La inserción de listas enlazadas es mucho más económica que las matrices.

La ordenación por inserción inyecta el nuevo valor en el medio del segmento ordenado. Por lo tanto, es necesario "rechazar" los datos. Sin embargo, cuando está utilizando una lista vinculada, al girar 2 punteros, efectivamente ha empujado la lista completa hacia atrás. En una matriz, debe realizar n - i intercambios para retroceder los valores, lo que puede ser muy costoso.

La ordenación por selección siempre se agrega al final, por lo que no tiene este problema al usar matrices. Por lo tanto, no es necesario "rechazar" los datos.

Una explicación simple podría ser la siguiente:

Dado : una matriz sin clasificar o una lista de números.

Planteamiento del problema : ordenar la lista / matriz de números en orden ascendente para comprender la diferencia entre el ordenamiento por selección y el ordenamiento por inserción.

Tipo de inserción:Verá la lista de arriba a abajo para una mejor comprensión. Consideramos el primer elemento como nuestro valor mínimo inicial. Ahora, la idea es que recorramos cada índice de esa lista / matriz linealmente para averiguar si hay algún otro elemento en cualquier índice que tenga un valor menor que el valor mínimo inicial. Si encontramos tal valor, simplemente intercambiamos los valores en sus índices, es decir, digamos que 15 fue el valor inicial mínimo en el índice 1 y durante el recorrido lineal de los índices, nos encontramos con un número con un valor menor, digamos 7 en el índice 9 Ahora, este valor 7 en el índice 9 se intercambia con el índice 1 que tiene 15 como valor. Este recorrido seguirá haciendo comparación con el valor del índice actual con los índices restantes para intercambiar por el valor más pequeño. Esto continúa hasta el penúltimo índice de la lista / matriz,

Orden de selección:Supongamos que el primer elemento de índice de la lista / matriz está ordenado. Ahora, desde el elemento en el segundo índice, lo comparamos con su índice anterior para ver si el valor es menor. El recorrido se puede visualizar en dos partes, clasificadas y sin clasificar. Uno estaría visualizando una verificación de comparación desde el no clasificado hacia el ordenado para un índice dado en la lista / matriz. Digamos que tiene el valor 19 en el índice 1 y el valor 10 en el índice 3. Consideramos el recorrido desde el no clasificado al ordenado, es decir, de derecha a izquierda. Entonces, digamos que tenemos que ordenar en el índice 3. Vemos que tiene un valor menor que el índice 1 cuando lo comparamos de derecha a izquierda. Una vez identificado, simplemente colocamos este número 10 del índice 3 en el lugar del índice 1 que tiene el valor 19. El valor original 19 en el índice 1 se desplaza un lugar a la derecha.

No he agregado ningún código, ya que la pregunta parece sobre la comprensión del concepto del método de recorrido.

La ordenación por inserción no intercambia cosas. A pesar de que hace uso de una variable temporal, el objetivo de hacer uso de la variable temporal es cuando encontramos que un valor en un índice es menor en comparación con el valor de su índice anterior, cambiamos el valor mayor al lugar del valor menor. índice que sobreescribiría cosas. Luego usamos la var temp para ser sustituida en el índice anterior. Ejemplo: 10, 20, 30, 50, 40. iteración 1:10, 20, 30, 50, 50. [temp = 40] iteración 2: 10,20, 30, 40 (valor de temperatura), 50. Entonces, simplemente inserte un valor en la posición deseada de alguna variable.

Pero cuando consideramos la clasificación por selección, primero encontramos que el índice tiene un valor más bajo e intercambiamos ese valor con el valor del primer índice y seguimos intercambiando repetidamente hasta que todos los índices se clasifiquen. Esto es exactamente lo mismo que el intercambio tradicional de dos números. Ejemplo: 30, 20, 10, 40, 50. Iteración 1: 10, 20, 30, 40, 50. Aquí temp var se usa exclusivamente para intercambiar.

La ordenación por inserción cambia mucho más esa selección. Aquí hay un ejemplo:

Lo que ambos tienen en común es que ambos usan una partición para diferenciar entre la parte ordenada de la matriz y la no ordenada.

La diferencia es que con la ordenación por selección se le garantiza que la parte ordenada de la matriz no cambiará al agregar elementos a la partición ordenada.

La razón es que la selección busca el mínimo del conjunto sin clasificar y lo agrega justo después del último elemento del conjunto ordenado, aumentando así el conjunto ordenado en 1.

La inserción, por otro lado, solo se preocupa por el siguiente elemento que se encuentra, que es el primer elemento de la parte sin clasificar de la matriz. Tomará este elemento y simplemente lo colocará en su lugar adecuado en el conjunto ordenado.

Normalmente, la ordenación por inserción siempre será un mejor candidato para las matrices que solo se ordenan parcialmente porque está desperdiciando operaciones para encontrar el mínimo.

Conclusión:

La ordenación por selección agrega de forma incremental un elemento al final al encontrar el elemento mínimo en la sección sin clasificar.

La ordenación por inserción propaga el primer elemento que se encuentra en la sección no ordenada a cualquier lugar de la sección ordenada.

Aunque la complejidad de tiempo de la ordenación por selección y la ordenación por inserción es la misma, es n (n - 1) / 2. El tipo de inserción de rendimiento medio es mejor. Probado en mi cpu i5 con 30000 enteros aleatorios, la clasificación por selección tomó 1,5 segundos en promedio, mientras que la clasificación por inserción tomó 0,6 segundos en promedio.

En términos sencillos, (y probablemente la forma más fácil de lograr un alto nivel de comprensión del problema)

La clasificación de burbujas es similar a pararse en una fila y tratar de clasificarse por altura. Sigues cambiando con la persona que está a tu lado hasta que estés en el lugar correcto. Esto tiene lugar desde la izquierda (o la derecha según la implementación) y sigue cambiando hasta que todos estén ordenados.

Sin embargo, en la ordenación por selección, lo que está haciendo es similar a organizar una mano de cartas. Miras las cartas, tomas la más pequeña, la colocas completamente a la izquierda, y así sucesivamente.

selección: seleccionar un elemento en particular (el más bajo) y cambiarlo con el elemento i (no de iteración). (es decir, primero, segundo, tercero .......) por lo tanto, haciendo la lista ordenada en un lado.

inserción: comparar primero con segundo comparar tercero con segundo y primero comparar cuarto con tercero, segundo y primero ...

un enlace donde se comparan todas las clasificaciones