Metodo de incersion directa

El método de inserción directa es el que generalmente utilizan los jugadores de cartas cuando ordenan éstas, de ahí que tambien se conozca con el nombre de método de la baraja.
La idea central deeste algoritmo 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.
Ejemplo:Se desean ordenarse las siguientes clave del arreglo A: 15, 67, 08, 16, 44, 27, 12, 35

Primera pasada
A[2] < A[1] 67 < 15 No hay intercambio

A: 15, 67, 08, 16, 44, 27, 12, 35

Segundapasada
A[3] < A[2] 08 < 67 Si hay intercambio
A[2] < A[1] 08 < 15 Si hay

A: 15, 08, 67, 16, 44, 27, 12, 35

Tercera pasada
A[4] < A[3] 08 < 15 Si hay intercambio
A[3] <A[2] 08 < 15 Si hay intercambio

A= 08, 15, 67, 16, 44, 27, 12, 35

Hasta la septima pasada el arreglo queda ordenado: 08, 12, 15, 16, 27, 35, 44, 67

ANALISIS DE EFICIENCIA DEL METODO DEINSERCION DIRECTA

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
Elnú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 siguientes:
Mmin = 0 Mmed = (n2-n)/4 Mmax = (n2-n)/2

Eltiempo 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 queel método de intercambio directo analizado anteriormente.

El método de ordenación por inserción es similar al proceso típico de ordenar tarjetas de nombres
(cartas de una baraja) por orden...