MÉTODO DE ORDENACIÓN SHELL

El método Shell pertenece a los métodos de clasificación avanzados, nombrado así en honor a su desarrollador, Donald Shell.

Este método utiliza una segmentación entre los datos. Funciona comparando elementos que estén distantes; la distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la ultima fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama ordenación por disminución de incrementos.

La ordenación de Shell usa una secuencia, h1, h2, . . ., ht, conocida como la secuencia de incrementos. Al principio de todo proceso, se fija una secuencia decreciente de incrementos. Cualquier secuencia funcionará en tanto que empiece con un incremento grande, pero menor al tamaño del arreglo de los datos a ordenar, y que el último valor de dicha secuencia sea 1.

Una elección muy común (pero no tan eficiente) para la secuencia de incrementos es adoptar la secuencia sugerida por Shell: ht = [n / 2], y hk = [hk+1 / 2]. A continuación se muestra un programa que implanta la ordenación de Shell usando esta secuencia.

# include <iostream.h>

void main (void)

{

int a[15];

int n, inc, i, j, tmp;

cout <<"De cuantos elementos es el arreglo? ";

cin >> n;

for (i=1; i<=n; i++)

{

cout <<"Introduce el elemento " <<i<<" : ";

cin >> a[i];

}

inc = n/2;

while (inc > 0)

{

for (i = inc +1; i<=n; i++)

{

tmp = a[i];

j=i;

while ( (j-inc) > 0 )

{

if (tmp < a[j-inc])

{

a[j]=a[j-inc];

j=j-inc;

}

else

break;

} // fin del while //

a[j]=tmp;

} // fin del for //

inc = inc/2;

} // fin del while //

cout <<endl;

for (i=1; i<=n; i++)

cout << a[i] <<endl;

} // fin de shell sort //

Una variante de este método, utiliza un arreglo incrmnts, que contiene los incrementos decrecientes del ordenamiento y una constante numinc, el número de elementos en el arreglo incrmnts. Es decir, la variación está en que los incrementos no se calculan en el algoritmo, si no que se establece un arreglo que contiene dichos incrementos. La siguiente rutina implanta esta variante en el método.

Shellsort (x, n, incrmnts, numinc)

{

int incr, j, k, span, y;

for (incr =0; incr<numinc; incr++)

{

span=incrmnts[incr];

for (j=span; j<n; j++)

{

y=x[j];

for (k=j-span; k>=0 && y<x[k]; k-=span)

x[k+span]=x[k];

x[k+span]=y;

} // fin del for //

} // fin del for //

} // fin del shell sort //

Los requerimientos reales de tiempo para un ordenamiento específico dependen del número de elementos del arreglo incrmnts y de sus valores reales. Un requerimiento intuitivamente claro es que los elementos deberían ser primos relativos. Esto garantiza que iteraciones sucesivas entremezclen subarchivos de manera que el archivo completo esté ordenado cuando span sea igual a 1.

Se recomienda este método para archivos de tamaño moderado de algunos cientos de elementos.

Knuth aporta evidencia de que una elección razonable de incrementos es la secuencia (en orden inverso):

1, 4, 13, 40, 121, 364, . . .,(3m-1)/2

También recomienda la secuencia:

1, 3, 7 ,15, 31, 63, 127, . . ., (2m-1)

Para esta ultima secuencia, se ha encontrado que su complejidad es de O(n1.2) en el mejor caso, O(n1.25) para el caso promedio y O(n1.5) para el peor caso.

Contrastablemente, el tiempo de ejecución del peor caso en la ordenación de Shell, usando los incrementos de Shell, es de O(n2). El problema con los incrementos de Shell, es que los pares de incrementos no son necesariamente primos relativos, y así el menor incremento puede tener poco efecto.

Sedgewick ha propuesto varias secuencias de incremento que dan un tiempo de ejecución para el peor caso de O(n1.33). Se conjetura que el tiempo de ejecución medio es de O(n1.16) para estas secuencias. La mejor de estas secuencias es:

1, 5, 19, 41, 109, …

En la cual los términos son de la forma 9·4i - 9·2i +1