Ordenamiento por inserción

Teoría

En este algoritmo la idea es ordenar un conjunto de números realizando múltiples comparaciones iniciando con los dos primeros elementos del conjunto, luego agregando uno por uno hasta terminar con todos.

Caso de estudio

Imagine un juego de cartas, a usted le entregan su primera carta, que resulta ser un 5, este es su punto de referencia, al recibir la segunda carta obtiene un 3, en este momento se ubica el 3 a la izquierda del 5, ordenando las primeras dos cartas; la siguiente carta es un 7 la cual se compara con las cartas que ya tiene, de derecha a izquierda, al compararla con el 5 el 7 es mayor, y este queda de ultimo, a continuación recibe un 4, siguiente el método, se compara con la primera carta de la derecha, que es un 7, al ser menor el 4 continua comparando, se compara con el 5, al ser menor sigue comparando, se compara con el 3, al ser mayor se detiene en esa posición, la ultima carta es un 6, siguiente el método se compara con el 7, al ser menor pasa a comparar con el 5, pero al ser mayor que el 5 se detiene en esa posición, al final se obtienen las cartas ordenas.

1. Recibe el 5 y se ubica en la primera posición de izquierda a derecha.




2. Recibe el 3 y lo compara con el 5.



3. Al ser 3 menor que 5 se ubica en la primera posición a la izquierda.



4. Recibe 7 y lo compara con el 5.



5. Al ser 7 mayor que 5, se ubica 7 en la ultima posición después del 5, aunque el 7 sea mayor se debe realizar la comparación porque el computador es bruto.



6. Recibe 4 y se compara con 7.



7. Al ser 4 menor que 7, se continua comparando con 5.



8. Al ser 4 menor que 5, se continua comparando con 3.



9. Al ser 4 mayor que 3, se ubica el 4 entre el 3 y el 5.



10. Recibe 6 y se compara con 7.



11. Al ser 6 menor que 7, se continua comparando con 5.



12. Al ser 6 mayor que 5, se ubica el 6 entre el 5 y el 7.



13. Como ya no hay mas elementos las cartas están ordenadas.



NOTA: Si nos asignaran todas las cartas al mismo tiempo, la idea seria la misma pero la ejecución se haría de la siguiente manera:

By Swfung8 (Own work) via Wikimedia Commons

Algoritmo

Para ordenar una lista de números(sin repetirse) de menor a mayor de izquierda a derecha usando "Ordenamiento por inserción".

1. Se toma el segundo elemento de izquierda a derecha de la lista a ordenar.
2. Se evalúa si existe un elemento anterior, de ser así continua al paso 3, de lo contrario al paso 4.
3. Se evalúa si dicho elemento es menor que el anterior.
3.1 Si es menor, se intercambian de posición, garantizando que el menor quede a la izquierda y se continua al paso 2.
3.2 En caso contrario, se conservan las posiciones iniciales y se continua con el paso 4.
4. Se vuelve al paso 2 con siguiente elemento de la lista hasta que no queden más.

Vídeo

Por si todavía no es claro, dejamos a su disposición un vídeo demasiado didáctico.

Enlaces recomendados

Libros:

• Ejemplo completo y muy gráfico [Ingles]

Java 6 Illuminated: An Active Learning Approach, Julie Anderson y Hervé Franceschi, Pag. 516 a 524.

• Explicación mas concreta.

Beginning Programming For Dummies, Wallace Wang, Pag. 216 a 223.