Informe

ORDENAMIENTO POR INSERCIÓN

El ordenamiento por inserción (insertionsort 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.

ALGORITMO

El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamentesencillo y se comporta razonablemente bien en gran cantidad de situaciones.
Se basa en intentar construir una lista ordenada en el interior del array a ordenar.
De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otrosdos en la mayor parte de las situaciones.
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no.

Este algoritmo también es bastante sencillo. ¿Has jugado cartas?. ¿Cómo lasvas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hastaque quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.
Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderáun elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

Un ejemplo
¿Te acuerdas de nuestra famosa lista?
4 - 3 - 5 - 2 - 1
“TEMP” toma el valor del segundo elemento, 3. La primera carta es el 4. Ahoracomparamos: 3 es menor que 4. Luego desplazamos el 4 una posición a la derecha y después copiamos el 3 en su lugar.
4 - 4 - 5 - 2 - 1
3 - 4 - 5 - 2 - 1
El siguiente elemento es 5. Comparamos con 4. Es mayor que 4, así que no ocurren intercambios.
Continuamos con el 2. Es menor que cinco: desplazamos el 5 una posición a la derecha:
3 - 4 - 5 - 5 - 1
Comparamos con 4: es menor, así que desplazamosel 4 una posición a la derecha:
3 - 4 - 4 - 5 - 1
Comparamos con 3. Desplazamos el 3 una posición a la derecha:
3 - 3 - 4 - 5 - 1
Finalmente copiamos el 2 en su posición final:
2 - 3 - 4 - 5 - 1
El último elemento a ordenar es el 1. Cinco es menor que 1, así que lo desplazamos una posición a la derecha:
2 - 3 - 4 - 5 - 5
Continuando con el procedimiento la lista va quedando así:
2 - 3 - 4 - 4 - 52 - 3 - 3 - 4 - 5
2 - 2 - 3 - 4 - 5
1 - 2 - 3 - 4 - 5
De esa forma quedan todos los calores del vector ordenados


DIAGRAMA DE FLUJO




































PSEUDOCÓDIGO
Expresado en pseudocódigo, podría ser algo como esto Algoritmo inserción
( A : array de n elementos indizados de 1 a n)
variables: enteros i, j, v
//estas son las pasadas, desde 2 hasta n
//en cada una intentaremosencontrar la posición
//relativa del elemento i entre los anteriores
para i desde 2 hasta n
//tomamos el elemento a examinar en una variable
//temporal v
v=A[i]
//empezamos a comparar con los anteriores.
j=i-1
//en este bucle intentamos saber cual es su
//lugar y le vamos haciendo hueco
mientras (j>=1) Y (A[j]>v) hacer
//desplazamos el elemento A[j]
A...