Inserción

Ordenamiento por Inserción

El algoritmo consiste en realizar varias pasadas sobre el array. En cada pasada se analiza un elemento, y se intenta encontrar su orden relativo entre los analizados en pasadas anteriores. Con esto se logra ir manteniendo una lista ordenada constantemente. Cada elemento a analizar se desplaza por esa lista hasta encontrar su lugar. Cuando todos los elementos del array han sido analizados, la lista está completamente ordenada. Esa es una diferencia importante con BubbleSort y SelectionSort. En ellos, en cada pasada se colocaba una carta en su sitio definitivo. En InsertionSort, el array no está totalmente ordenado hasta que el algoritmo termina.

Ejemplo de ordenamiento por inserción ordenando una lista de números aleatorios.

EJEMPLO:

Supongamos que queremos ordenar estos valores con el algoritmo de selección directa: 45, 52, 21, 37, 49, 72, 14. Así pues, n=7

Empezamos a analizar el segundo elemento. El primero está en orden con respecto a sí mismo. Forma él solo una lista ordenada. Intentaremos mantener una lista ordenada al principio del array. Vamos a marcar el elemento a analizar en rojo y la lista ordenada en azul.

1ª pasada: El primer elemento forma la lista ordenada, y vamos a ver qué hacemos con el segundo.

45, 52, 21, 37, 49, 72, 14 → Comparamos 52 con el anterior. Como está en orden, paramos.
45, 52, 21, 37, 49, 72, 14 → 45 y 52 forman la lista ordenada ahora. (Sí, sí… están en orden entre ellos 45<52)

2ª pasada: Hay dos elementos en orden relativo entre ellos y vamos a ver qué hacemos con el tercero.

45, 52, 21, 37, 49, 72, 14 → Comparamos el 21 con el anterior (52). No están en orden, así que los intercambiamos.
45, 21, 52, 37, 49, 72, 14 → Comparamos el 21 con el anterior (45). No están en orden, así que los intercambiamos.
21, 45, 52, 37, 49, 72, 14 → Ya no hay más para comparar. El 21 está en su sitio con respecto a los otros de la lista.
21, 45, 52, 37, 49, 72, 14 → Ahora 21, 45 y 52 forman la lista ordenada.

3ª pasada: Hay tres elementos en orden relativo entre ellos y vamos a ver qué hacemos con el cuarto.

21, 45, 52, 37, 49, 72, 14 → Comparamos el 37 con el anterior (52). No están en orden, así que los intercambiamos.
21, 45, 37, 52, 49, 72, 14 → Comparamos el 37 con el anterior (45). No están en orden, así que los intercambiamos.
21, 37, 45, 52, 49, 72, 14 → Comparamos el 37 con el anterior (21). Sí están en orden, así que paramos.
21, 37, 45, 52, 49, 72, 14 → Ahora 21, 37, 45 y 52 forman la lista ordenada.

4ª pasada: Hay cuatro elementos en orden relativo entre ellos y vamos a ver qué hacemos con el quinto.

21, 37, 45, 52, 49, 72, 14 → Comparamos el 49 con el anterior (52). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 52, 72, 14 → Comparamos el 49 con el anterior (45). sí están en orden, así que paramos.
21, 37, 45, 49, 52, 72, 14 → Ahora 21, 37, 45, 49 y 52 forman la lista ordenada.

5ª pasada: Hay cinco elementos en orden relativo entre ellos y vamos a ver qué hacemos con el sexto.

21, 37, 45, 49, 52, 72, 14 → Comparamos el 72 con el anterior (52). Sí están en orden, así que paramos.
21, 37, 45, 49, 52, 72, 14 → Ahora 21, 37, 45, 49, 52 y 72 forman la lista ordenada.

6ª y última pasada: Hay seis elementos en orden relativo entre ellos y vamos a ver qué hacemos con el séptimo.

21, 37, 45, 49, 52, 72, 14 → Comparamos el 14 con el anterior (72). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 52, 14, 72 → Comparamos el 14 con el anterior (52). No están en orden, así que los intercambiamos.
21, 37, 45, 49, 14, 52, 72 → Comparamos el 14 con el anterior (49). No están en orden, así que los intercambiamos.
21, 37, 45, 14, 49, 52, 72 → Comparamos el 14 con el anterior (45). No están en orden, así que los intercambiamos.
21, 37, 14, 45, 49, 52, 72 → Comparamos el 14 con el anterior (37). No están en orden, así que los intercambiamos.
21, 14, 37, 45, 49, 52, 72 → Comparamos el 14 con el anterior (21). No están en orden, así que los intercambiamos.
14, 21, 37, 45, 49, 52, 72 → Comparamos el 14 con el anterior (21). No están en orden, así que los intercambiamos.
14, 21, 37, 45, 49, 52, 72 → Ya no hay más para comparar, así que el 14 está en su sitio.

Ya no quedan elementos a anailizar al final del array, así que hemos terminado y el array está ordenado.

Análisis del algoritmo:

Número de comparaciones: n(n-1)/2 lo que implica un T(n) = O(n2 ). La ordenación por inserción utiliza aproximadamente n2/4 comparaciones  y n2/8 intercambios en el caso medio y dos veces más en el peor de los casos. La ordenación por inserción es lineal para los archivos casi ordenados.

Mejor Caso: O(n)
Peor Caso: O(n^2)
Caso Promedio: O(n^2)