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

METODO BURBUJA.... ¿Que es?

Buen día, se que este tema ya esta saturado en Internet pero les pondré solo la información mas importante de este tema.

DEFINICIÓN

Este algoritmo de ordenamiento (descendente o ascendente) se basa en el principio de comparar pares de elementos adyacentes e intercambiar entre si hasta que estén todos ordenados.

EJEMPLO

Supogamos que se desea clasificar en orden ascedente el vector o lista

50 ---- 15 --- 56 --- 14 --- 35 --- 1 ---- 12 ---- 9
A[1] -A[2] -A[3] -A[4] -A[5] -A[6] -A[7] -A[8]

Los pasos para ordenarlo son:
1.- Comparar A[1] y A[2]; si estan en orden, se mantiene como estan; en caso contrario, se intercambian entre si.
2.- A continuacion se compara los elementos 2 y 3; de nuevo se intercambian si es necesario.
3.- El proceso continua hasta que cada elemento del vector ha sido comparada con sus elementos adyacentes y se han realizado los intercambios necesarios.

En pseudocodigo lo fundamental es (el metodo):

desde i=1 hasta 7 hacer
si elemento[i] > elemento [i+1] entonces
aux=A[i]
A[i]=A[i+1]
A[i+1]=aux
fin_si
fin_desde

NOTA: las palabras en negritas son propias del lenguaje.

DATOS IMPORTANTES DEL MÉTODO BURBUJA

Este es el método más simple y antiguo para ordenar un conjunto de datos, es
también el más lento.

El algoritmo burbuja tiene dos bucles for internos que recorren el vector
comparando el elemento j-esimo-1 con el elemento con el j-esimo elemento y en
caso de que este sea mayor hace un cambio de los elementos.

Al tener dos bucles internos el comportamiento es en general O(n^2), y en las mejores
condiciones se comporta como O(n).

Este es un link de un ejemplo en codigo en lenguaje c.
http://rapidshare.com/files/448851279/metodo_burbuja.c

Estoy abierto a cualquier duda o error que pude haber causado.