Ordenamiento por Inserción

Ordenamiento por Inserción: Supóngase que se desea ordenar los siguientes claves del arreglo (A) utilizando el método de inserción directa el cual consiste en insertar un elemento del arreglo en la parte izquierda del mismo que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-esimo elemento.

INSERCION (A,N), Algoritmo

Insercion(A,N)
{El algoritmo ordena los elementos del arreglo utlizando el método de inserción directa A es un arreglo de N elementos} {I, aux y k son variables de tipo entero}
1.- Repetir con I desde 2 hasta N Hacer aux<- A[I] y k<- I-1
a. Repetir mientras(aux < [k]) y (k > 1) , Hacer A[k+1]<- A[k] y k<-- k-1
b. {fin del ciclo del paso 1.1}
c. Si a[k]<=aux Entonces: Hacer A[k+1]<-aux
Si no Hacer A[k+1]<- A[k], A[k]<-A[k]
d. { fin del condicional del paso 1.3}
2. {fin del condicional del paso1}

Prueba de escritorio:

Si A= 15, 67, 08, 16, 44, 27, 12, 35
1ª pasada 08, 67, 15, 16, 44, 27, 12, 35
2ª pasada 08, 15, 67, 16, 44, 27, 12, 35
3ª pasada 08, 15, 16, 67, 44, 27, 12, 35
4ª pasada 08, 15, 16, 44, 67, 27, 12, 35
5ª pasada 08, 15, 16, 44, 27, 67, 12, 35
6ª pasada 08, 15, 16, 44, 27, 12, 67, 35
7ª pasada 08, 15, 16, 44, 27, 12, 35, 67

ANALISIS DE EFICIENCIA DEL METODO DE INSERCION DIRECTA

En general afirmar que si el arreglo se encuentra ordenado se efectúan como máximo n-1 comparaciones y o movimientos entre elementos Cmin = n-1.

El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden inverso
Cmax = 1+2+3+............+(n-1) = n*(n-1)/2
Cmax= (n2-n)/2

El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
Respecto al número de movimientos Knuth obtiene los siguiente:
Mmin = 0
Mmed = (n2-n)/4
Mmax = (n2-n)/2

El tiempo necesario para ejecutar el algoritmo

El tiempo necesario para ejecutar el algoritmo es proporcionar a n2, O(n2).
A pesar de ser un método ineficiente y recomendable solo cuando n es pequeña, el método de inserción directa se comporta mejor que el método de intercambio directo.

Fuentes

• http://latecladeescape.com/con-nombre-propio/ordenacion-por-insercion-directa-insertionsort.html
  
• http://www.mitecnologico.com/Main/OrdenamientoPorInsercion
  
• http://snippets-tricks.org/ordenacion-insercion/