La idea de este algoritmo de ordenación consiste en ir insertando un elemento de la lista ó un arreglo en la parte ordenada de la misma, asumiendo que el primer elemento es la parte ordenada, el algoritmo ira comparando un elemento de la parte desordenada de la lista con los elementos de la parte ordenada, insertando el elemento en la posición correcta dentro de la parte ordenada, y así sucesivamente hasta obtener la lista ordenada. Para explicarlo mejor nos basaremos en el siguiente enunciado:
“Para cada elemento de la lista después del primero, comparar los elementos con los anteriores desplazando una posición a la derecha a todos los elementos anteriores que cumplan con la comparación y luego colocar el elemento en la posición del último elemento anterior desplazado.”
Ahora veamos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:
7, 3, 10, 1, 9
La lista tiene 5 elementos, con lo cual tendremos que recorrer la lista 4 veces. Ya que la comparación se hará desde el segundo elemento de la lista, es decir recorremos la lista después del primer elemento hasta el último.
1er. recorrido: Se toma 3 para comparar con los elementos anteriores. Los elementos anteriores son: 7
3 7 10 1 9
La comparación 3<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.
3 7 10 1 9
Al no haber más elementos a comparar colocamos el 3 en la posición del último elemento desplazado.
3
10
1
9
2do. recorrido: Se toma 10 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7
10 3 7 1 9
La comparación 10<7, es falsa, entonces no desplazamos nada y se termina este recorrido.
3 7 10 1 9
3er. recorrido: Se toma 1 para comparar con los elementos anteriores. Los elementos anteriores son: 3, 7, 10
1 3 7 10 9
La comparación 1<10, es verdadera, entonces desplazamos el 10 una posición a la derecha.
1 3 7 10 9
La comparación 1<7, es verdadera, entonces desplazamos el 7 una posición a la derecha.
1 3 7 10 9
La comparación 1<3, es verdadera, entonces desplazamos el 3 una posición a la derecha.
1 3 7 10 9
Al no haber más elementos a comparar colocamos el 1 en la posición del último elemento desplazado.
1 3 7 10 9
4to. recorrido: Se toma 9 para comparar con los elementos anteriores. Los elementos anteriores son: 1, 3, 7, 10
9 1 3 7 10
La comparación 9<10 es verdadera, entonces desplazamos el 10 una posición a la derecha.
1 7 10
La comparación 9<7 es falsa, entonces no desplazamos nada y se termina este recorrido, colocando el 9 en la posición del último elemento desplazado.
1 3 7 9 10
Con este último recorrido la lista ya esta ordenada. Tal como se puede observar, cada recorrido termina cuando se encuentra una posición en donde colocar el elemento tomado o cuando ya no haya elementos con que comparar. Bien ahora el siguiente procedimiento sería la primera implementación del algoritmo:
Este algoritmo es el que hemos usado en capítulos anteriores, pero se tiene que observar que este algoritmo hace uso de la evaluación booleana en cortocircuito. Si observa la condición (j>=0) and (aux<A[j]) del bucle while, puede suceder que cada vez que se disminuye j en 1 este puede llegar a ser negativo, y el algoritmo comparará un valor fuera del rango, algo parecido a esto aux<A[-1], pero esa comparación no sucederá porque se usa la evaluación booleana en cortocircuito, lo que significa que sólo se evaluara el resultado de la primera condición (j>=0), y dependiendo de ella se evaluará la siguiente. Es decir si (j>=0) es falso, entonces no se evalúa la condición (aux<A[j]), ya que basta con que una de las condiciones sea falsa para que el operador and de como resultado un valor falso.
En caso se presente una situación en la que no debemos usar la evaluación booleana en cortocircuito, entonces es necesario usar el tipo de dato longword para la variable j. Esto nos obliga a modificar el algoritmo anterior haciendo uso para ello de una variable de tipo boolean que nos permite controlar el bucle while, y nos indique que j llego al inicio de la lista cuando este obtenga el valor 0. Ejemplo:
El algoritmo usa la variable IniLista para terminar el bucle while, esta variable será verdadera cuando j llegue a valer 0 y sólo disminuirá el valor de j en 1 cuando j sea mayor que 0, es decir j nunca llegará a valer -1. Esto nos lleva a colocar una condición después del bucle while que verifica como se salió del bucle, y de esa manera evitar incrementar j en 1 cuando este tenga el valor 0. Esta serie de adiciones harán que el algoritmo sea un poco más lento, pero nos permite evitar una comparación fuera del rango de la lista (aux<A [-1]).
Los algoritmos anteriores se pueden mejorar enormemente con el uso de la función move, que se puede usar en vez de ir desplazando los elementos anteriores uno por uno, move nos permite copiar el contenido de una variable por bloques. En ambos algoritmos la variable j nos indica en qué posición se colocará o insertará el elemento a ordenar, de esa manera podemos usar move para indicarle que mueve un bloque desde j a j+1, según sea el caso, veamos cómo debe ser el primer algoritmo usando move:
Como se puede observar el bucle while sólo disminuye la variable j hasta encontrar la posición de inserción. Una vez encontrado la posición de inserción entonces se hace uso de move. Se copia desde A[j], en la posición A[j+1], la cantidad de elementos indicada por i-j, se multiplica por 8 porque LNaturales usa qword que tiene un tamaño de 8 bytes y la cantidad de elementos a mover debe ser siempre en bytes; pero en el caso se quiera ordenar un arreglo dinámico que tiene elementos de tipo word, entonces se debe multiplicar por 2 y así respectivamente. Además se puede observar que hay una condición en la que j debe ser menor que i, esta condición es importante para evitar que cuando ambas variables sean iguales no se intente mover 0 bytes.
Para el segundo algoritmo se debe tener en cuenta el hecho de que la variable j no dará un resultado negativo con lo que la rutina move será diferente según cada caso:
En caso j sea cero (se llego al inicio de la lista) no es necesario restar i de j, y en caso sea distinto de cero se resta i de j, para obtener la cantidad de elementos a copiar con move.
Los algoritmos mencionados anteriormente ordenan la listas de menor a mayor (ascendente), en caso quisiéramos hacerlo de mayor a menor (Descendente), sólo basta con cambiar la condición, aux<A[j] por aux>A[j].
Si se quiere ordenar listas que usen los tipos de datos como ansistring o unicodestring, entonces lo recomendado es usar uno de los algoritmos que no use move, ya que será difícil determinar la longitud en bytes a desplazar por esta función.
El siguiente archivo comprimido: OrdenacionInsercion.zip ,tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales y LPalabras de la unidad listas.