ORDENACIÓN SHELL
La ordenación Shell debe el nombre a su inventor, D. L. Shell. Se suele denominar también
ordenación por inserción con incrementos decrecientes.
El algoritmo de Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de
mayor tamaño. Generalmente se toma como salto inicial n/2 (siendo n el número de elementos),
luego se reduce el salto a la mitad en cada repetición hasta que el salto es de tamaño 1. El Ejemplo
ordena una lista de elementos siguiendo paso a paso el método de Shell.
Ejemplo
Obtener las secuencias parciales del vector al aplicar el método Shell para ordenar en orden
creciente la lista:
6152340
El número de elementos que tiene la lista es 6, por lo que el salto inicial es 6/2 = 3. La siguiente
tabla muestra el número de recorridos realizados en la lista con los saltos correspondiente.
Recorrido Salto Intercambios Lista
1 3 (6,2),(5,4),(6,0) 2 1 4 0 3 5 6
2 3 (2, 0) 0 1 4 2 3 5 6
3 3 ninguno 0 1 4 2 3 5 6
salto 3/2 = 1
4 1 (4,2),(4,3) 0 1 2 3 4 5 6
5 1 ninguno 0 1 2 3 4 5 6
Algoritmo de ordenación Shell
Los pasos a seguir por el algoritmo para una lista de n elementos son:
1. Dividir la lista original en n/2 grupos de dos, considerando un incremento o salto entre los
elementos de n/2.
2. Clarificar cada grupo por separado, comparando las parejas de elementos, y si no están
ordenados, se intercambian.
3. Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los
elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.
4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido
anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego
clasificando cada grupo por separado.
5. El algoritmo termina cuando se consigue que el tamaño del salto es 1.
Por consiguiente, los recorridos por la lista está condicionados por el bucle,
intervalo n / 2
mientras (intervalo > 0) hacer
Para dividir la lista en grupos y clasificar cada grupo se anida este código,
para i (intervalo + 1) hasta n hacer
j i - intervalo
mientras (j > 0) hacer
k v j + intervalo
si (a[j] <= a[k]) entonces
j −1
sino
Intercambio (a[j], a[k]);
j j - intervalo
fin_si
fin_mientras
fin_para
En el código anterior se observa que se comparan pares de elementos indexados por j y k,
(a[j],a[k]), separados por un salto, intervalo. Así, si n = 8 el primer valor de intervalo
= 4, y los índices i =5, j =1, k =6. Los siguientes valores de los índices son i = 6, j = 2, k =
7,
y así hasta recorrer la lista.
Para realizar un nuevo recorrido de la lista con la mitad de grupos, el intervalo se hace la mitad:
intervalo intervalo / 2
así se repiten los recorridos por la lista, mientras intervalo > 0.
Codificación en C del algoritmo del método Shell
Al codificar en C este método de ordenación se ha de tener en cuenta que el operador, /, realiza una
división entera si los operandos son enteros, y esto es importante al calcular el ancho del salto entre
pares de elementos: intervalo = n/2.
En cuanto a los índices, C toma como base el índice 0 y, por consiguiente, se ha de desplazar
una posición a la izquierda las variables índice respecto a lo expuesto en el algoritmo.
void ordenacionShell(double a[], int n)
{
int intervalo, i, j, k;
intervalo = n / 2;
while (intervalo > 0)
{
for (i = intervalo; i < n; i++)
{
j = i - intervalo;
while (j >= 0)
{
k = j + intervalo;
if (a[j] <= a[k])
j = -1; /* así termina el bucle, par
ordenado */
else
{
double temp;
temp = a[j];
a[j] = a[k];
a[k] = temp;
j -= intervalo;
}
}
}
intervalo = intervalo / 2;
}
}
