Método de Shell (Shell Sort)

El método Shell (en honor a su descubridor) mejor del método de inserción simple ordenando subarrreglos del arreglo original en forma separada. Para crear estos nuevos subarreglos, se toman elementos saltados del areglo original en relación a incrementos predeterminados.

Por ejemplo suponiendo un arreglo X, y tomando un incremento (salto) igual a 5, se generarían los siguientes subarreglos:

Con un salto igual a 3 se obtendrían:

Lo habitual es tomar un valor de incremento, y ordenar mediante inserción los subarreglos obtenidos. Luego se toma otro valor de incremento, y se ordenan ahora los asubarreglos generados a partir de este incremento. Y así sucesivamente para diferentes valores de incremento o salto.

Supongamos que tenemos el siguienmte arreglo:

y que se elige la secuencia de incrementos (5,3,1), los archivos a ordenar para esta secuencia serían:

con incremento = 5:

con incremento = 3:

con incremento = 1:

A continuación se muestra el resultado del ordenamiento Shell sobre este arreglo. Las líneas indican los subarreglos que se procesan por separado.

arreglo original	o	25	57	48	37	12	92	86	33
paso 1 salto = 5	o	25	57	48	37	12	92	86	33
paso 2 salto = 3		25	57	33	37	12	92	86	48
paso 3 salto = 1		25	12	33	37	48	92	86	57
Arreglo ordenado		25	12	33	37	48	57	86	92

Habitualmente lo que se hace es generar un arreglo que contenga los incrementos. Suponiendo que se tiene un arreglo con los incrementos, a continuación se muestra un ejemplo del método Shell en el siguiente fragmento de código en C:

.
.
.
int X[n]; /* será el número de elementos del arreglo */
int i,j,K /* K será el elemento que se inserte para mantener el orden */
int incre[numinc]; /* incre contiene la secuencia de incrementos,
		         y numinc es el número total de incrementos */
int salto, numi;
.
.
.
for (numi=0;numi<numinc;numi++)
{
	salto = incre[numi]; /* salto es el incremento actual */
	for (j=salto;j<n;j++)
	{	
		K=X[j];
		for(i=j-salto;i>=0&&K<X[i];i-=salto)
		{
			X[i+salto]=X[i];
			X[i]=K;
		}
	}
}
.
.
.

Se recomienda utilizar secuencias de incrementos, donde ellos sean numeros primos relativos, es decir, que no tengan divisores comunes entre ellos distintos del 1.