Tipo de inserción - Insertion sort

Tipo de inserción

Animación de ordenación por inserción
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\ Displaystyle O (n ^ {2})}$ comparaciones e intercambios
Rendimiento en el mejor de los casos	${\ Displaystyle O (n)}$comparaciones, intercambios${\ Displaystyle O (1)}$
Rendimiento medio	${\ Displaystyle O (n ^ {2})}$ comparaciones e intercambios
Complejidad espacial en el peor de los casos	${\ Displaystyle O (n)}$total, auxiliar${\ Displaystyle O (1)}$

La ordenación por inserción es un algoritmo de ordenación simple que crea la matriz (o lista) ordenada final un elemento a la vez. Es mucho menos eficiente en grandes listas que los algoritmos más avanzados, como la clasificación rápida , heapsort , o combinación de especie . Sin embargo, la ordenación por inserción ofrece varias ventajas:

• Implementación simple: Jon Bentley muestra una versión C de tres líneas y una versión optimizada de cinco líneas
• Eficiente para conjuntos de datos (bastante) pequeños, al igual que otros algoritmos de clasificación cuadrática
• Más eficiente en la práctica que la mayoría de los otros algoritmos cuadráticos simples (es decir, O ( n ² )) como el ordenamiento por selección o el ordenamiento por burbujas
• Adaptable , es decir, eficiente para conjuntos de datos que ya están sustancialmente ordenados: la complejidad temporal es O ( kn ) cuando cada elemento en la entrada no está a más de k lugares de su posición ordenada
• estable ; es decir, no cambia el orden relativo de los elementos con claves iguales
• En el lugar ; es decir, solo requiere una cantidad constante O (1) de espacio de memoria adicional
• En línea ; es decir, puede ordenar una lista a medida que la recibe

Cuando las personas clasifican manualmente las cartas en una mano de bridge , la mayoría usa un método similar al ordenamiento por inserción.

Algoritmo

Un ejemplo gráfico de ordenación por inserción. La lista ordenada parcial (negra) contiene inicialmente solo el primer elemento de la lista. Con cada iteración, se elimina un elemento (rojo) de los datos de entrada "aún no verificado para el pedido" y se inserta en el lugar en la lista ordenada.

La ordenación por inserción se repite , consume un elemento de entrada en cada repetición y aumenta una lista de salida ordenada. En cada iteración, la ordenación por inserción elimina un elemento de los datos de entrada, encuentra la ubicación a la que pertenece dentro de la lista ordenada y la inserta allí. Se repite hasta que no quedan elementos de entrada.

La clasificación se realiza normalmente en el lugar, iterando la matriz, aumentando la lista ordenada detrás de ella. En cada posición de la matriz, verifica el valor allí con el valor más grande en la lista ordenada (que pasa a estar junto a él, en la posición de la matriz verificada anteriormente). Si es más grande, deja el elemento en su lugar y pasa al siguiente. Si es más pequeño, encuentra la posición correcta dentro de la lista ordenada, desplaza todos los valores más grandes hacia arriba para hacer un espacio y los inserta en esa posición correcta.

La matriz resultante después de k iteraciones tiene la propiedad donde se ordenan las primeras k + 1 entradas ("+1" porque se omite la primera entrada). En cada iteración, se elimina la primera entrada restante de la entrada y se inserta en el resultado en la posición correcta, extendiendo así el resultado:

se convierte en

con cada elemento mayor que x copiado a la derecha al compararlo con x .

La variante más común de ordenación por inserción, que opera en matrices, se puede describir de la siguiente manera:

1. Suponga que existe una función llamada Insertar diseñada para insertar un valor en una secuencia ordenada al comienzo de una matriz. Opera comenzando al final de la secuencia y desplazando cada elemento un lugar hacia la derecha hasta que se encuentra una posición adecuada para el nuevo elemento. La función tiene el efecto secundario de sobrescribir el valor almacenado inmediatamente después de la secuencia ordenada en la matriz.
2. Para realizar una ordenación por inserción, comience en el elemento más a la izquierda de la matriz e invoque Insertar para insertar cada elemento encontrado en su posición correcta. La secuencia ordenada en la que se inserta el elemento se almacena al comienzo de la matriz en el conjunto de índices ya examinados. Cada inserción sobrescribe un valor único: el valor que se inserta.

A continuación, se muestra el pseudocódigo del algoritmo completo, donde las matrices son de base cero :

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

El bucle exterior recorre todos los elementos excepto el primero, porque el prefijo de un solo elemento A[0:1]está clasificado trivialmente, por lo que el invariante de que ise ordenan las primeras entradas es verdadero desde el principio. El bucle interior mueve el elemento A[i]a su lugar correcto para que, después del bucle, se ordenen los primeros i+1elementos. Tenga en cuenta que el and-operador en la prueba debe usar la evaluación de cortocircuito , de lo contrario, la prueba podría dar como resultado un error de límites de matriz , cuando j=0e intenta evaluar A[j-1] > A[j](es decir, el acceso A[-1]falla).

Después de expandir la swapoperación en el lugar como x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x(donde xes una variable temporal), se puede producir una versión un poco más rápida que se mueve A[i]a su posición de una sola vez y solo realiza una asignación en el cuerpo del bucle interno:

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

El nuevo bucle interior desplaza elementos hacia la derecha para despejar un lugar x = A[i].

El algoritmo también se puede implementar de forma recursiva. La recursividad simplemente reemplaza el ciclo externo, llamándose a sí mismo y almacenando sucesivamente valores más pequeños de n en la pila hasta que n es igual a 0, donde la función luego regresa hacia arriba en la cadena de llamadas para ejecutar el código después de cada llamada recursiva comenzando con n igual a 1, con n aumentando en 1 a medida que cada instancia de la función vuelve a la instancia anterior. La llamada inicial sería insertionSortR (A, length (A) -1) .

function insertionSortR(array A, int n)
    if n > 0
        insertionSortR(A, n-1)
        x ← A[n]
        j ← n-1
        while j >= 0 and A[j] > x
            A[j+1] ← A[j]
            j ← j-1
        end while
        A[j+1] ← x
    end if
end function

No acorta el código, tampoco reduce el tiempo de ejecución, pero aumenta el consumo de memoria adicional de O (1) a O (N) (en el nivel más profundo de recursividad, la pila contiene N referencias al Amatriz, cada una con el valor de la variable nde acompañamiento desde N hasta 1).

Casos mejores, peores y promedio

La mejor entrada de caso es una matriz que ya está ordenada. En este caso, la ordenación por inserción tiene un tiempo de ejecución lineal (es decir, O ( n )). Durante cada iteración, el primer elemento restante de la entrada solo se compara con el elemento más a la derecha de la subsección ordenada de la matriz.

La entrada más simple en el peor de los casos es una matriz ordenada en orden inverso. El conjunto de todas las entradas del peor de los casos consta de todas las matrices donde cada elemento es el más pequeño o el segundo más pequeño de los elementos anteriores. En estos casos, cada iteración del bucle interno escaneará y desplazará toda la subsección ordenada de la matriz antes de insertar el siguiente elemento. Esto le da a la ordenación por inserción un tiempo de ejecución cuadrático (es decir, O ( n ² )).

El caso promedio también es cuadrático, lo que hace que la ordenación por inserción no sea práctica para ordenar matrices grandes. Sin embargo, la ordenación por inserción es uno de los algoritmos más rápidos para clasificar muy pequeñas matrices, incluso más rápido que la clasificación rápida ; de hecho, las buenas implementaciones de ordenación rápida utilizan ordenación por inserción para matrices más pequeñas que un cierto umbral, también cuando surgen como subproblemas; el umbral exacto debe determinarse experimentalmente y depende de la máquina, pero suele rondar los diez.

Ejemplo: la siguiente tabla muestra los pasos para ordenar la secuencia {3, 7, 4, 9, 5, 2, 6, 1}. En cada paso, se subraya la clave que se está considerando. La llave que se movió (o se dejó en su lugar porque era la más grande considerada) en el paso anterior está marcada con un asterisco.

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

Relación con otros algoritmos de clasificación

La ordenación por inserción es muy similar a la ordenación por selección . Como en el ordenamiento por selección, después de que k pasa a través de la matriz, los primeros k elementos están ordenados. Sin embargo, la diferencia fundamental entre los dos algoritmos es que el ordenamiento por inserción escanea hacia atrás desde la clave actual, mientras que el ordenamiento por selección busca hacia adelante. Esto da como resultado una ordenación por selección que hace que los primeros k elementos sean los k elementos más pequeños de la entrada no ordenada, mientras que en la ordenación por inserción son simplemente los primeros k elementos de la entrada.

La principal ventaja del ordenamiento por inserción sobre el ordenamiento por selección es que el ordenamiento por selección siempre debe escanear todos los elementos restantes para encontrar el elemento más pequeño absoluto en la parte no ordenada de la lista, mientras que el ordenamiento por inserción requiere solo una comparación cuando el ( k  + 1) -st elemento es mayor que el k -ésimo elemento; cuando esto es frecuentemente cierto (como si la matriz de entrada ya está ordenada o parcialmente ordenada), la ordenación por inserción es claramente más eficiente en comparación con la ordenación por selección. En promedio (asumiendo que el rango del ( k  + 1) -st elemento rango es aleatorio), la ordenación por inserción requerirá comparar y cambiar la mitad de los k elementos anteriores , lo que significa que la ordenación por inserción realizará aproximadamente la mitad de comparaciones que la ordenación por selección en promedio.

En el peor de los casos para la ordenación por inserción (cuando la matriz de entrada está ordenada al revés), la ordenación por inserción realiza tantas comparaciones como la ordenación por selección. Sin embargo, una desventaja de la ordenación por inserción sobre la ordenación por selección es que requiere más escrituras debido al hecho de que, en cada iteración, insertar el elemento ( k  + 1) -st en la parte ordenada de la matriz requiere muchos intercambios de elementos para cambiar todo de los siguientes elementos, mientras que solo se requiere un único intercambio para cada iteración del ordenamiento de selección. En general, la ordenación por inserción escribirá en la matriz O ( n ² ) veces, mientras que la ordenación por selección escribirá solo O ( n ) veces. Por esta razón, la clasificación por selección puede ser preferible en los casos en los que escribir en la memoria es significativamente más caro que leer, como con EEPROM o memoria flash .

Si bien algunos algoritmos de dividir y conquistar , como la ordenación rápida y la ordenación por fusión, superan la ordenación por inserción para matrices más grandes, los algoritmos de ordenación no recursiva como la ordenación por inserción o la ordenación por selección son generalmente más rápidos para matrices muy pequeñas (el tamaño exacto varía según el entorno y la implementación, pero es típicamente entre 7 y 50 elementos). Por lo tanto, una optimización útil en la implementación de esos algoritmos es un enfoque híbrido, utilizando el algoritmo más simple cuando la matriz se ha dividido en un tamaño pequeño.

Variantes

DL Shell realizó mejoras sustanciales en el algoritmo; la versión modificada se llama Orden de Shell . El algoritmo de clasificación compara elementos separados por una distancia que disminuye en cada pasada. La clasificación de conchas ha mejorado notablemente los tiempos de ejecución en el trabajo práctico, con dos variantes simples que requieren un tiempo de ejecución O ( n ^3/2 ) y O ( n ^4/3 ).

Si el costo de las comparaciones excede el costo de los intercambios, como es el caso, por ejemplo, con las claves de cadena almacenadas por referencia o con la interacción humana (como elegir una de un par que se muestra una al lado de la otra), entonces el uso de la ordenación por inserción binaria puede producir mejor presentación. La clasificación de inserción binaria emplea una búsqueda binaria para determinar la ubicación correcta para insertar nuevos elementos y, por lo tanto, realiza comparaciones ⌈log ₂  n ⌉ en el peor de los casos. Cuando se busca e inserta cada elemento de la matriz, este es O ( n  log  n ). El algoritmo en su conjunto todavía tiene un tiempo de ejecución de O ( n ² ) en promedio debido a la serie de intercambios requeridos para cada inserción.

El número de intercambios se puede reducir calculando la posición de varios elementos antes de moverlos. Por ejemplo, si la posición de destino de dos elementos se calcula antes de que se muevan a la posición adecuada, el número de intercambios se puede reducir en aproximadamente un 25% para datos aleatorios. En el caso extremo, esta variante funciona de manera similar a la ordenación por combinación .

Una variante denominada ordenación por combinación binaria utiliza una ordenación por inserción binaria para ordenar grupos de 32 elementos, seguida de una ordenación final mediante ordenación por combinación . Combina la velocidad de ordenación por inserción en conjuntos de datos pequeños con la velocidad de ordenación por fusión en conjuntos de datos grandes.

Para evitar tener que hacer una serie de intercambios para cada inserción, la entrada podría almacenarse en una lista vinculada , lo que permite que los elementos se empalmen dentro o fuera de la lista en un tiempo constante cuando se conoce la posición en la lista. Sin embargo, la búsqueda en una lista vinculada requiere seguir secuencialmente los vínculos a la posición deseada: una lista vinculada no tiene acceso aleatorio, por lo que no puede utilizar un método más rápido como la búsqueda binaria. Por lo tanto, el tiempo de ejecución requerido para la búsqueda es O ( n ) y el tiempo de clasificación es O ( n ² ). Si se utiliza una estructura de datos más sofisticada (por ejemplo, un montón o un árbol binario ), el tiempo necesario para la búsqueda y la inserción se puede reducir significativamente; esta es la esencia de la ordenación del montón y la ordenación del árbol binario .

En 2006, Bender, Martin Farach-Colton y Mosteiro publicaron una nueva variante de ordenación por inserción llamada ordenación por biblioteca o ordenación por inserción con huecos que deja una pequeña cantidad de espacios no utilizados (es decir, "huecos") repartidos por toda la matriz. El beneficio es que las inserciones solo necesitan cambiar elementos hasta que se alcanza un espacio. Los autores muestran que este algoritmo de clasificación se ejecuta con alta probabilidad en el tiempo O ( n  log  n ).

Si se utiliza una lista de omisión , el tiempo de inserción se reduce a O (log  n ) y no se necesitan intercambios porque la lista de omisión se implementa en una estructura de lista vinculada. El tiempo de ejecución final para la inserción sería O ( n  log  n ).

El ordenamiento por inserción de lista es una variante del ordenamiento por inserción. Reduce el número de movimientos.

Listar el código de clasificación de inserción en C

Si los elementos se almacenan en una lista vinculada, la lista se puede ordenar con O (1) espacio adicional. El algoritmo comienza con una lista inicialmente vacía (y por lo tanto ordenada trivialmente). Los elementos de entrada se quitan de la lista uno a la vez y luego se insertan en el lugar adecuado en la lista ordenada. Cuando la lista de entrada está vacía, la lista ordenada tiene el resultado deseado.

struct LIST * SortList1(struct LIST * pList) 
{
    // zero or one element in list
    if (pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while (pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if (head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while (p != NULL) {
                if (p->pNext == NULL || // last element of the sorted list
                    current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

El siguiente algoritmo utiliza un puntero final para la inserción en la lista ordenada. Un método recursivo más simple reconstruye la lista cada vez (en lugar de empalmar) y puede usar el espacio de pila O ( n ).

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL) {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}

Referencias

Otras lecturas

• Knuth, Donald (1998), "5.2.1: Clasificación por inserción", El arte de la programación informática , 3. Clasificación y búsqueda (segunda ed.), Addison-Wesley, págs. 80-105, ISBN 0-201-89685-0.

enlaces externos

• Algoritmos de clasificación animados: clasificación por inserción en la Wayback Machine (archivado el 8 de marzo de 2015) - demostración gráfica
• Adamovsky, John Paul, Orden de inserción binaria - Cuadro de indicadores - Investigación completa e implementación de C , Pathcom.
• Ordenación por inserción: una comparación con otros algoritmos de ordenación O (n ² ) , Reino Unido : Core war.
• Ordenación por inserción (C) (wiki), Programas alfabetizados - implementaciones de ordenación por inserción en C y varios otros lenguajes de programación