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.