Ordenacion x Insercion Binaria

ORDENACION POR INSERCION
Este método se basa en considerar una parte de lista ordenada y situar cada uno de los elementos insertándolo en el lugar que le corresponda por su valor, todos los valores a la derecha se desplazan una posición para dejar espacio.


EJEMPLO


Este método esta basado en la técnica utilizada por los jugadores de cartas para clasificar sus cartas. El jugador va colocando (insertando) cada carta en su posición correcta:

2 8 10 tres cartas

2 8 9 10 cuatro cartas



ALGORITMO DE INSERCION

( para cada elemento de la lista después del primero ) desde k 2 hasta n hacer:

Guardar el valor de este elemento A(k) en una variable Aux.

Hacer espacio para Aux desplazando todos los valores mayores que dicho valor A(k) una posición.

Insertar el valor de Aux en el lugar del ultimo valor desplazado.


ORDENACION POR INSERCION

La operación de desplazamiento se realiza con un procedimiento Desplazar, Que mueve todos los elementos de la lista mayores que Aux, comenzando con el elemento de la lista de posición Aux-1. Si Aux es el valor mas pequeño, la operación de desplazamiento termina cuando un valor menor o igual a Aux se alcanza. Aux se inserta en la posición que ocupaba el ultimo valor que se desplazo.


ALGORITMO DE DESPLAZAMIENTO

Mientras el primer elemento no se desplaza y valor del elemento > Aux hacer:

Desplazar elemento una posición.

Comprobar valor del siguiente elemento.

Definir NuevaPos como posición original del ultimo elemento desplazado.


METODO DE INSERCIÒN BINARIA

El análisis de la ordenación por inserción es un poco mas complicado. El numero de comparaciones en i-èsimo paso es como k-1 y como mínimo 1. por consiguiente proporciona el numero de comparaciones.


METODO DE INSERCIÒN BINARIA

1. Hallamos el elemento central del área comprendida por la parte ordenada más la posición del elemento a insertar.

2 3 5 6 7 4

2. Comparamos el elemento central con el elemento que queremos insertar. Si dicho elemento central es menor o igual, nos quedamos con la parte derecha (Sin incluir el elemento central). En caso contrario, nos quedamos con la parte
izquierda incluyendo al elemento central.

2..

2 3 5 4

3..

Repetimos el mismo proceso sobre el área con la que nos quedamos, hasta que dicha área se nula.

5 4


4..

Cuando el área sea nula, tendremos la posición de inserción.


2 3 4 5 6 7