método de insersion estructura con su ejemplo

Método de Inserción


Método de Inserción Este método también se denomina “método del jugador de cartas”, por la semejanza con la forma de clasificar las cartas de una baraja, insertando cada carta en el lugar adecuado. El algoritmo ordena los dos primeros elementos de la lista, a continuación el tercer elemento se inserta en la posición que corresponda, el cuarto se inserta en la lista de tres elementos, y así sucesivamente. Este proceso continua hasta que la lista este totalmente ordenada. Sea una lista A[1], A[2], ... A[n]. Los pasos a dar para una ordenación ascendente son: 1. Ordenar A[1] y A[2]. 2. Comparar A[3] con A[2], si A[3] es mayor o igual a que A[2], sigue con el siguiente elemento si no se compara A[3] con A[1]; si A[3] es mayor o igual que A[1], insertar A[3] entre A[1] yA[2]. Si A[3] es menor que A[1], entonces transferir A[3] a A[1], A[1] a A[2] y A[2] a A[3]. 3. Se suponen ordenados los n-1 primeros elementos y corresponde insertar el n-ésimo elemento. Si A[m] es mayor que A[k] (con K = 1, 2, ..., m-1), se debe correr una posición A[k+1], ... A[m-1] y almacenar A[m] en la posición k+1.



Consideremos el mismo arreglo del ejemplo anterior { 7, 2, 8, 3, 5, 1 }. El proceso sería de la siguiente manera: 

1ra iteración, i permanece fijo en la casilla 1 y j se decrementa mientras el elemento es menor a j: { 7, 2, 8, 3, 5, 1 } tem = 2, j = 0, mientras j >= 0 y tem < 7, { 7, 7, 8, 3, 5, 1 }, j se decrementa en 1 { 7, 7, 8, 3, 5, 1 } tem = 2, j = -1, mientras j >=0, rompe mientras, tem ingresa { 2, 7, 8, 3, 5, 1 } 

2da iteración, i permanece fijo en la casilla 2 y j se decrementa mientras el elemento es menor a j: { 2, 7, 8, 3, 5, 1 } tem = 8, j = 1, mientras j >= 0 y tem < 7, rompe mientras { 2, 7, 8, 3, 5, 1 } 

3ra iteración, i permanece fijo en la casilla 3 y j se decrementa mientras el elemento es menor a j: { 2, 7, 8, 3, 5, 1 } tem = 3, j = 2, mientras j >= 0 y tem < 8, { 2, 7, 8, 8, 5, 1 }, j se decrementa en 1 { 2, 7, 8, 8, 5, 1 } tem = 3, j = 1, mientras j >= 0 y tem < 7, { 2, 7, 7, 8, 5, 1 }, j se decrementa en 1 { 2, 7, 7, 8, 5, 1 } tem = 3, j = 0, mientras j >= 0 y tem < 2, rompe, tem ingresa { 2, 3, 7, 8, 5, 1 }

 4ta iteración, i permanece fijo en la casilla 4 y j se decrementa mientras el elemento es menor a j: { 2, 3, 7, 8, 5, 1 } tem = 5, j = 3, mientras j >= 0 y tem < 8, { 2, 3, 7, 8, 8, 1 }, j se decrementa en 1 { 2, 3, 7, 8, 8, 1 } tem = 5, j = 2, mientras j >= 0 y tem < 7, { 2, 3, 7, 7, 8, 1 }, j se decrementa en 1 { 2, 3, 7, 7, 8, 1 } tem = 5, j = 1, mientras j >= 0 y tem < 3, rompe, tem ingresa { 2, 3, 5, 7, 8, 1 }

 5ta iteración, i permanece fijo en la casilla 5 y j se decrementa mientras el elemento es menor a j: { 2, 3, 5, 7, 8, 1 } tem = 1, j = 4, mientras j >= 0 y tem < 8, { 2, 3, 5, 7, 8, 8 }, j se decrementa en 1 { 2, 3, 5, 7, 8, 8 } tem = 1, j = 3, mientras j >= 0 y tem < 7, { 2, 3, 5, 7, 7, 8 }, j se decrementa en 1

{ 2, 3, 5, 7, 7, 8 } tem = 1, j = 2, mientras j >= 0 y tem < 5, { 2, 3, 5, 5, 7, 8 }, j se decrementa en 1
 { 2, 3, 5, 5, 7, 8 } tem = 1, j = 1, mientras j >= 0 y tem < 3, { 2, 3, 3, 5, 7, 8 }, j se decrementa en 1 
{ 2, 3, 3, 5, 7, 8 } tem = 1, j = 0, mientras j >= 0 y tem < 2, { 2, 2, 3, 5, 7, 8 }, j se decrementa en 1
 { 2, 2, 3, 5, 7, 8 } tem = 1, j = -1, mientras j >= 0, rompe mientras, tem ingresa { 1, 2, 3, 5, 7, 8 }   

 Diagrama de flujo de ordenamiento por inserción