4

 La idea central de este 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 segundohasta el n elemento.

 1. Partimos de un arreglo aleatoriamente ordenado, y

marcamos su primer elemento como parte ordenada,
el resto será la parte desordenada.

 2. Tomamos el primerelemento de la parte no

ordenada, y se almacena en una variable temporal.

 3. Comparamos empezando por el final de la parte

ordenada, hasta que se encuentra un elemento menor.

 4.Se desplaza una posición a la derecha todos los

elementos que han resultado mayores que el que
queremos insertar y se coloca el valor de la variable
temporal en el lugar encontrado.

Se repite el proceso hasta terminar la sección de

elementos no ordenados.
 Si observamos la posición del valor que estamos
ordenando se "borra" automáticamente.

 Ejemplo:Supongase quese desea ordenar las siguientes

claves del arreglo A utilizando el método de inserción
directa.

A: 15 67 08 16 44 27 12 35

PRIMERA PASADA
A[2] A: 15 6708 16 44 27 12 35

SEGUNDA PASADA
A[3] A[2] A: 08 15 67 16 44 27 12 35

 TERCERA PASADA






A: 08 15 67 16 44 27 1235
A[4] A[3] A: 08 15 16 67 44 27 12 35
Obsérvese que una vez que se determina la posición
correcta del elemento seinterrumpen las
comparaciones.
 Por ejemplo, en el caso anterior no se realizó la
comparación A[2]
 Las restantes pasadas se presentan a continuación:

Código en Java












void insercion_directa(int n)
{
int i,j,aux;
i=j=1;
for(;j for(i=j;i > 0 && (arr[i] < arr[i-1]); i--)
{
aux=arr[i];
arr[i]=arr[i+1];
arr[i+1]=aux;
}
}

BIBLIOGRAFIAS



Leer documento completo

Regístrate para leer el documento completo.