Este algoritmo de ordenación fue creado por Donald Shell, el algoritmo se denomina Shell en honor a su inventor. El algoritmo se parece al algoritmo de ordenación por inserción. En el algoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda de uno en uno, pero con el algoritmo de Shell la comparación se hace con intervalos mayores a uno, logrando con ello que la ordenación sea más rápida. Generalmente se toma como intervalo inicial n div 2, siendo n la cantidad de elementos de la lista a ordenar, luego se reduce los intervalos a la mitad hasta que el intervalo llegue a ser uno. Cuando la ordenación de la lista se hace con un intervalo de 1 el algoritmo se comporta como el algoritmo de inserción, pero con la ventaja de que al tener una lista casi ordenada, debido a los ordenamientos por intervalos anteriores, el ordenamiento se hará más rápido.
Veremos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:
7, 3, 10, 1, 9, 8, 4
La lista tiene 7 elementos (de 0 a 6), con lo cual obtendremos un intervalo inicial de 3, división entera de 7 entre 2 (7 div 2). Desde el elemento 3 se ordena la lista por inserción, hacia la izquierda tomando los elementos de 3 en 3, y así hasta terminar de recorrer la lista.
1er recorrido: intervalo 3, resultado de la división entera de 7 entre 2.
Desde el elemento 3. Elementos a ordenar: 7, 1
7 1 7 3 10 1 9 8 4
Se colocan los elementos ordenados por inserción
1 3 10 7 9 8 4
Desde el elemento 4. Elementos a ordenar: 3, 9
3 9 1 3 10 7 9 8 4
Se colocan los elementos ordenados por inserción
1 3 10 7 9 8 4
Desde el elemento 5. Elementos a ordenar: 10, 8
10 8 1 3 10 7 9 8 4
Se colocan los elementos ordenados por inserción
1 3 8 7 9 10 4
Desde el elemento 6. Elementos a ordenar: 1, 7, 4
1 7 4 1 3 10 7 9 8 4
Se colocan los elementos ordenados por inserción
1 3 8 4 9 10 7
2do recorrido: intervalo 1, resultado de la división entera de 3 entre 2.
La lista se ordena con un intervalo de 1, es decir desde el elemento 1 hasta el último elemento de la lista. En esta parte el algoritmo se comporta como en el algoritmo de inserción y la lista se ordena haciendo menos intercambios.
1 3 4 7 8 9 10
Tal como se puede observar el bucle while es el que controla la cantidad de intervalos a ordenar, y el resto viene a ser el mismo algoritmo de inserción adaptado para que se usen los intervalos que se van obteniendo. La variable j que es la clave de este algoritmo se va disminuyebdo de intervalo en intervalo (intv), en vez de hacerlo de 1 en 1 como en el algoritmo de inserción.
Este algoritmo también se puede adaptar para que no use la evaluación booleana en cortocircuito, a continuación el procedimiento correspondiente:
Este algoritmo de Ordenamiento Shell, tiene otras variantes, que se diferencian en la generación de la secuencia de intervalos. Originalmente la secuencia de intervalos es ir dividiendo con 2 los intervalos hasta llegar a 1, tomando como primer intervalo la longitud de la lista, pero cualquier secuencia de intervalos funcionará con este algoritmo siempre y cuando esta termine en 1. A continuación dos secuencias de intervalos que ofrecen un mejor rendimiento y de fácil implementación:
1era Secuencia de intervalos (Gonnet y Baeza-Yates): Esta secuencia de intervalos consiste en tomar la longitud de la lista multiplicarlo por 5 y después hacer una división entera con 11, para el siguiente intervalo, tomar el anterior multiplicarlo por 5 y hacer una división entera con 11, y así sucesivamente hasta llegar a 1. Sólo se debe tener en cuenta que cuando el intervalo es 2 este debe cambiarse siempre a 1.Por ejemplo si tenemos una lista de 100 elementos a ordenar, los intervalos serían. 45, 20, 9, 4, 1; pero en el caso de 150 elementos los intervalos serán: 68, 30, 13, 5, 1. Como puede observar del 5 se salto al 1, ignorando el 2 que es resultado de (5*5) div 11. Esto es por lo siguiente: Si intentáramos obtener el intervalo considerando el 2 obtendríamos 68, 30, 13, 5, 2, 0; y eso estaría muy mal porque la secuencia de intervalos no termina en 1 sino en cero, es por eso que se debe cambiar el 2 por el 1, sólo cuando este aparezca. Ejemplo:
2da Secuencia de intervalos (Steven Pigeon): Esta secuencia de intervalos está basado en la siguiente secuencia matemática: an=1+en-2, en donde, e es el número de Euler y n es cualquier número entero positivo mayor que 0, es decir n=1, 2 , 3, 4, 5, 6 ... ∞. A todos los valores de esta secuencia matemática se debe redondear antes de obtener la parte entera, que se usará como intervalo. Para una lista de 150 elementos los intervalos con dos cifras decimales sin redondear serían: 1.36, 2.00, 3.71, 8.38, 21.08, 55.59, 49.41, redondeando obtendremos: 1, 2, 4, 8, 21, 56, 149. El ordenamiento shell ordena la lista usando los intervalos desde el mayor hasta 1, por lo que se necesita obtener el intervalo an que sea menor que la longitud de la lista, para ello despejamos n de la siguiente ecuación: a=1+en-2, en donde a es la longitud de la lista, con lo que obtenemos la siguiente ecuacion: n=ln(a-1)+2, (ln=logaritmo neperiano) el valor devuelto por la ecuación, debe ser truncado para obtener un valor entero que nos permite obtener el intervalo an menor a la longitud de la lista. Hay que tener presente que si la lista tiene longitud de 1 entonces al obtener el valor de n, se intentará obtener el ln(0), esto producirá un error, que se puede evitar con una estructura de control if-then-else al inicio del procedimiento. En donde se evita ordenar la listas cuando este es de un sólo elemento.
En este algoritmo se puede observar que se comprueba que la longitud de la lista sea mayor que 1, en caso no lo sea la variable intv tendrá el valor 0, evitando ordenar la lista. Cada vez que se obtiene el nuevo intervalo se debe asegurar que n no llegue a valer 0, ya que si obtenemos un valor 0 para n, obtendremos un intervalo de 1, y si se sigue disminuyendo n obtendríamos un error de desbordamiento de punto flotante.
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-intv] por aux>A[j-intv].
El siguiente archivo comprimido: OrdenacionShell.zip,tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales y LPalabras de la unidad listas.