Ordenación por insercion

DEFINICIÓN

Este método consiste en insertar un elemento en el vector es una parte ya ordenada de este vector y comizas de nuevo con los elementos restantes. por ser utilizado generalmente por los jugadores de cartas se le conoce también por el nombre de método de baraja.
A si por ejemplo, suponga que tiene la lista desordenada.

para insertar el elemento 45, habrá que insertarlo entre 43 y 65, lo que supone desplazar a la derecha todos aquellos números de valor superiora 45, es decir, saltar sobre 65 y 84.

El metido se basa en comparaciones y desplazamientos sucesivos. el algoritmo de clasificación de un vector X para N elementos se realiza con un recorrido de todo el vector y la inserción del elemento correspondiente en el lugar adecuado. el recorrido se realiza desde el segundo elemento al n-ésimo.

CARACTERÍSTICAS

En el peor de los casos, el número de comparaciones que hay que realizar es de
N*(N+1)/2-1, lo que nos deja un tiempo de ejecución en O(n2). En el mejor caso
(cuando la lista ya estaba ordenada), el número de comparaciones es N-2. Todas
ellas son falsas, con lo que no se produce ningún intercambio. El tiempo de ejecución
está en O(n).

El caso medio dependerá de cómo están inicialmente distribuidos los elementos.
Vemos que cuanto más ordenada esté inicialmente más se acerca a O(n) y cuanto
más desordenada, más se acerca a O(n2).

El peor caso es igual que en los métodos de burbuja y selección, pero el mejor caso
es lineal, algo que no ocurría en éstos, con lo que para ciertas entradas podemos
tener ahorros en tiempo de ejecución.

PSEUDOCÓDIGO

Este es el código fuente, que mejor explica el método. si buscas bien y con paciencia todo encuentras ;).

Ejemplo en c.

void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i=1; i < index =" numbers[i];" j =" i;" style="font-weight: bold;">while ((j > 0) && (numbers[j-1] > index)){
numbers[j] = numbers[j-1];
j = j - 1;
}//fin del while
numbers[j] = index;
}//fin del for
}//fin del ejemplo

Aqui un link de un ejemplo en lenguaje .c
http://rapidshare.com/files/449013398/barajamio.c


Espero que la información aquí mostrada le sirva, y sino se entiende o cometí un error, dejen un comentario para solucionar el problema, estoy abierto a los errores y dudas ;)

NOTA: Los libros tienen la respuesta