ALGORITMICA Y ESTRUCTURA DE DATOSINSERCIÓN

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos.

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos.

EJERCICIO PLANTEADO

El ejercicio anterior (arreglo original), resolverlo mediante el método de inserción. Compare la cantidad de pasos realizados por ambos e indique cuál es el más rápido.

Respuesta:El más rápido es el Método de Inserción, porque realiza menos comparaciones

RESOLUCIÓN CON VARIABLES

/ Definir variables

nota: array

j,x, z, ordena: enteros

INICIO

/ ingreso de los 5 notas

Para j=1 hasta 5 hacer

Leer nota[j]

ALGORITMICA Y ESTRUCTURA DE DATOSFin Para

/ Ordenamiento mediante método inserción

Para x = 2 hasta 5 hacer

ordena = nota[x]

z = x-1

Mientras ((z> 0) y (nota[z] > ordena)) hacer

nota[z+1] = nota[z]

z = z – 1

Fin mientras

nota[z+1]= ordena

Fin para

/ imprimir notas ordenadas

Para j=1 hasta 5 hacer

Escribir nota[j]

Fin Para

FIN

1. La variable nota es de tipo matriz.2. Las variables j, x, zserán utilizadas como contadores acumulativos de uno en

uno.3. La variable ordena será utilizada para el intercambio.4. El pseudocódigo se divide en:

o Definición o declaración de variables.o Un procedimiento de ingreso de valores (notas) en un array o matriz.o Un procedimiento de ordenamiento de los valores ingresados al

array, utilizando el método inserción.o Un procedimiento de impresión de los valores ya ordenados de la

matriz nota.5. En el procedimiento de Ordenamiento utilizando el método de Inserción se

define lo siguiente:- La variable x es la encargada de contar el número de pasadas.- La variable z es la encargada de posicionar el puntero en la nota o

elemento con los que se comparará.- La variable ordena carga temporalmente el valor de la nota actual para

cuando se produzca el intercambio no se pierda el valor de la nota[x] y este se cargue a la nota [y].

- En la primera pasada se compara:o Se compara el segundo con el primero. Si el segundo es mayor

que el primero, se cambia. Si no, no cambia de posición.

ALGORITMICA Y ESTRUCTURA DE DATOS- En la segunda pasada o recorrido se compara:

o Se compara el tercero con el segundo. Si el tercero es mayor que el segundo, se cambia. Sino, no cambia de posición.

o Se compara el segundo con el primero. Si el segundo es mayor que el primero se cambia. Sino, no cambia de posición.

- En la tercera pasada o recorrido se compara:o Se compara el cuarta con el tercero. Si el cuarto es mayor que el

tercero, se cambia. Si no, no cambia de posición.o Se compara el tercero con el segundo. Si el tercero es mayor que

el segundo, se cambia. Si no, no cambia de posición.o Se compara el segundo con el primero. Si el segundo es mayor

que el primero se cambia. Si no, no cambia de posición.- En la cuarta pasada o recorrido se compara:

o Se compara el quinto con el cuarto. Si el quinto es mayor que el cuarto, se cambia. Si no, no cambia de posición.

o Se compara el cuarta con el tercero. Si el cuarto es mayor que el tercero, se cambia. Si no, no cambia de posición.

o Se compara el tercero con el segundo. Si el tercero es mayor que el segundo, se cambia. Si no, no cambia de posición.

o Se compara el segundo con el primero. Si el segundo es mayor que el primero se cambia. Si no, no cambia de posición.

- Resultado de estos recorridos y cambios de lugares de los valores de la matriz nota estos valores están ordenados en forma ascendente.

Ordenamiento usando Método INSERCIÓN

Análisis del algoritmo.

Notas Ingresadas15 16 7 19 12

Primera Pasada15 16 7 19 12

Segunda Pasada

15 7 16 19 12

7 15 16 19 12Tercera Pasada

7 15 16 19 127 15 16 19 127 15 16 19 12

Cuarta Pasada7 15 16 12 197 15 12 16 197 12 15 16 197 12 15 16 19

Ordenados en forma ascendente7 12 15 16 19

ALGORITMICA Y ESTRUCTURA DE DATOS Estabilidad: Este algoritmo nunca intercambia registros con claves iguales.

Por lo tanto es estable. Requerimientos de Memoria: Una variable adicional para realizar los

intercambios. Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se

ejecuta n-1 veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc. Esto produce una complejidad O(n2).

Ventajas:

Fácil implementación. Requerimientos mínimos de memoria.