Es deseable a la hora de programar, hacerse un sencillo esquema de como ha de funcionar el algoritmo, precisamente para luego ver que si falla, qué punto puede estar mal programado.
Primero procede una descripción del algoritmo, simple y clara... obviando que se trata de una lista enlazada (es más sencillo de entender si se aplica a un array) cuando se esté seguro que la descripción es correcta, se hace un pseudocódigo del mismo y luego se programa con el tipo de estructura que se haya solicitado...
Una descricpción simple podría ser:
Algoritmo de ordenación por inserción: 1 - Comenzando por el segundo elemento (en la lista) y siguiendo hasta el último, se toma como actual y se aparta.
2 - Luego el actual se va comparando con los que le preceden, mientras el precedente sea menor que él (y no se alcance el primero).
3 - En dicho caso el precedente cambia de posición colocándose detrás del puesto que ocupa el actual y el puesto del actual se reduce en 1 (sigue apartado).
4 - Cuando ya no hay más precedentes menor que él, se ubica en tras ese precedente.
5 - Volvemos al paso 1
Hay que entender la descripción. De otro modo, el código que le siga fracasará.
Lo siguiente es un pequeño pseudocódigo, todavía pòdemos obviar que se trata de listas enlazadas, resolvámoslo primero con arrays y luego se tratará con listas enlazadas...
funcion InsertionSort(array de enteros Array)
entero min, max, n, j, k, temp
min = 0
max = Array.length
j = (min +1)
bucle para k desde j hasta max // 1
temp = Array(k)
hacer mientras (temp < Array(j)) // 2
Array(j+1) = Array(j) // 3
j -=1
Si (j<0) salir del bucle // 2 ***
repetir
Array(j +1) = temp // 4
j = k
siguiente // 5
*** En según que lenguajes puede ponerse como primera condición del bucle, porque solo se evalua la segunda condición si la primera falla, en lenguajes que no 'cortocircuitan' incurre en un error, que se solventa colocando al final del bucle dicha condición (como se observa).
Nota que si los valores 'min' y 'max' se pasaran como parámetros, en vez de tenerlos internamente en la función, podría ordenarse cualquier subsección del array en vez del array entero que se toma por defecto de este modo.
Puede hacerse una ligera mejora al algoritmo. Es fácil darse cuenta que el elemento apartado, se asigna tras el bucle incluso aunque el precedente no sea menor. Si se hace una comprobación previa al bucle interno, y solo si se cumple dicha condición la asignación (del elemento siendo comparado) siempre será aplicable, si no, no se precisa... a su vez dado que esa condición ya examina dicha posibilidad, el bucle interno, puede mudar su condición a la parte baja (algunos lenguajes no toleran cambiar la condición al final del bucle):
funcion InsertionSort(array de enteros Array)
entero min, max, n, j, k, temp
min = 0
max = Array.length
j = (min +1)
bucle para k desde j hasta max // 1
temp = Array(k)
Si (temp < Array(j)) // 2
hacer //mientras (Array(j) < temp) // 2
Array(j+1) = Array(j) // 3
j -=1
Si (j<0) salir del bucle // 2
repetir mientras (temp < Array(j)) // 2
Array(j +1) = temp // 4
Fin si
j = k
siguiente // 5
Es importante notar la diferencia entre este y el pseudocódigo anterior.
Esta ligera mejora, ya que evita hacer asignaciones innecesarias, será aún más notable en la lista doblemente enlazada.
Como se puede seguir en el pseudocódigo (aplicado a un array) es bastante sencillo y podría pasarse a programar ya en cualquier lenguaje. Como se requiere aplicarlo sobre una lista doblemente enlazada, conviene pasarlo a una estructura de tal tipo antes de programarlo. Básicamente es copiar y pegar el pseudocódigo y luego hacer remplazos para referirse a los ítems de una lista doblemente enlazada. Suele requerirse a veces (este es el caso), tener algún elemento auxiliar, para no perder referencias del curso del actual.
Lo primero a notar es como cambiaremos las variable del tipo entero al tipo 'nodo' que son los elementos de la lista, y que la función recibe como parámetro el odo raíz.
estructura nodo
entero Valor
nodo Anterior
nodo Siguiente
fin estructura
funcion InsertionSort(nodo Raiz)
nodo j, k, temp //min, max,
temp = Raiz.Siguiente
hacer mientras temp no sea nulo // 1 Supone que hay más de 1 elemento y que no está más allá del último.
j = temp.Anterior
k = temp.siguiente
si (temp.Valor < j.Valor) // 2
// Aislamos temp de la lista reconectando sus extremos entre sí.
// Esto además nos permite, no tener necesidad de hacer intercambios contínuamente en el bucle que sigue.
Si (temp.Siguiente no es nulo)
temp.Siguiente.Anterior = j // el anterior al siguiente a temp, será ahora el anterior a temp (no temp)
fin si
j.Siguiente = temp.Siguiente // el siguiente del previo a temp, ahora será el siguiente de temp, incluso si es nulo (el último)
hacer // 2
Si (j.Anterior es nulo ) salir del bucle // 2
j = j.Anterior // 3
repetir mientras (temp.Valor < j.Valor)
// Ahora conectamos temp entre medios del que es manor o igual que él (aún siendo el primero) y el mayor que él (aún siendo el último)
// 4
si (j.Anterior es nulo)
temp.Anterior = j.Anterior // nulo
temp.siguiente = j
j.Anterior = temp
Raiz = temp
sino
j.siguiente.Anterior = temp
temp.Anterior = j
temp.siguiente = j.siguiente
j.siguiente = temp
fin si
Fin si
temp = k
repetir // 5
fin funcion
El código no es mucho más largo que la versión que opera sobre un array.
Nota como al desenlazar el nodo siendo examinado (y una vez vimos que debe cambiar de sitio, merced a la mejora introducida), podemos hacer un recorrido hacia atrás más sencillo y elegante.
También debes notar, como las precauciones tomadas preguntando cuando interesa si no es nulo, hace que no tengamos que hacer asignaciones más complejas...
Para probarlo, puede recurirse a crear una lista, ordenarla y luego imprimirla:
funcion CrearOrdenarYProbar
nodo j, k, temp, Raiz
entero n, valores[]
// 1 Creamos una lista doblemente enlazada de nodos
valores = Array(6, 4, 7, 8, 2, 5, 5, 1, 7, 3, 6, 8, 4, 9, 2)
Raiz = nuevo nodo
Raiz.Valor = valores(0)
k = Raiz
bucle para n desde 1 hasta valores.length
j = nuevo nodo
j.Valor = valore[n]
j.Anterior = k
k.siguiente = j
k = j
siguiente
// 2 ordenamos la lista.
llamada a InsertionSort(raiz)
// 3 mostramos el resultado.
temp = Raiz
hacer mientras temp no sea nulo
imprimir temp.Valor
temp = temp.siguiente
repetir
fin funcion
Resultado:
1
2
2
3
4
4
5
5
6
6
7
7
8
8
9