ORDENAMIENTO POR INSERCIÓN DIRECTA

Uno de los métodos de ordenamiento más sencillos es el ordenamiento por inserción directa. Se tiene una secuencia de números x1, x2,..., xn. Los números se recorren de izquierda a derecha y se escribe x¡ a la izquierda de x¡-1 si x¡ es menor que xi-1. En otras palabras, desplazamos a x¡ de manera continua hacia la izquierda hasta que los números a su izquierda sean menores que o iguales a él.

Algoritmo

for (i=0; i<R, i++)

{

i=j-1;

x= xj;

while((x<xi) & (i >0))

{

xi+1 = xi;

i = i-1;

}

xi+1 =x;

}

Ejemplo: Considere la secuencia de entrada 7,5,1,4,3,2,6. El ordenamiento por inserción directa produce la secuencia ordenada siguiente:

7
5,7
1,5,7
1,4,5,7
1,3,4,5,7
1,2,3,4,5,7
1,2,3,4,5,6,7.

En nuestro análisis, como medida de la complejidad temporal del algoritmo se usará el número de intercambios de datos x = xj, xi+1 = xi y xi+1 = x. En este algoritmo hay dos ciclos: uno exterior (for) y otro interior (while). Para el ciclo exterior siempre se ejecutan dos operaciones de intercambio de datos; a saber, x = xj y xi+1= x. Debido a que el ciclo interior puede o no ser ejecutado, el número de intercambios de datos realizados para x¡ en el ciclo interior se denotará por d¡. Así, evidentemente, el número total de movimientos de datos para el ordenamiento por inserción directa es

Esto ocurre cuando los datos de entrada ya están ordenados.

Peor caso: El peor caso ocurre cuando los datos de entrada están ordenados a la inversa. En este caso,

d2 =1, d3=2, ..., dn=n-1. De este modo,

Caso promedio: Cuando se está considerando x¡, ya se han ordenado (i — 1) datos. Si x¡ es el más grande de todos los i números, entonces el ciclo interior no se ejecuta y dentro de este ciclo interior no hay en absoluto ningún movimiento de datos. Si x¡ es el segundo más grande de todos los i números, habrá un intercambio de datos, y así sucesivamente. La probabilidad de que x¡ sea el más grande es 1/i. Esta también es la probabilidad de que x¡ sea el j-ésimo más grande para 1 <= j<= i. En consecuencia, el promedio (2 + d¡) es:
La complejidad temporal media para el ordenamiento por inserción directa es:
En resumen, la complejidad temporal del ordenamiento por inserción directa para cada caso es:

Mejor caso: 2(n — 1) = O(n).
Caso promedio: 1/4 (n + 8)(n - 1) = O(n^2).
Peor caso: 1/2 (n - 1)(n + 4) = O(n^2).