6.1.3 Shell Sort Ordenacion

Ordenación por el método de Shell

El método de Shell es una versión mejorada del método de inserción directa. Recibe ese nombre en honor de su autor, Donald L. Shell, quien lo propuso en 1959. Este método tén se conoce comoinserción con incrementos decrecientes.

En el método de ordenación por inserción directa cada elemento se compara para su ubicación correcta en el arreglo con los elementos que se encuentran en su parte izquierda. Si el elemento a insertar es mas pequeño que el grupo de elementos que se encuentran a su izquierda, será necesario efectuar varias comparaciones antes de su ubicación.

Shell propone que las comparaciones entre elementos se efectúen con saltos de  mayor tamaño, pero con incrementos decrecientes; así, los elementos quedaran n nados en el arreglo más rápidamente. Para comprender mejor este algoritmo anlice siguiente caso.

Consideremos un arreglo que contenga 16 elementos. En primer lugar, se dividirán los elementos del arreglo en ocho grupos, teniendo en cuenta los elementos que se encuentran a ocho posiciones de distancia entre si y se ordenaran por separado.

Quedarán en el primer grupo los elementos (A[l], A[9]); en el segundo, (A[2], A[10]); en d i cero, (A[3], A[ll]), y así sucesivamente. Después de este primer paso se dividir los elementos del arreglo en cuatro grupos, teniendo en cuenta ahora que los  elementos se encuentren a cuatro posiciones de distancia entre si y se les ordenara por separado. Quedarán en el primer grupo los elementos (A[l], A[5], A[9], A[13]); en el segundo (A[2], A[6], A[10], A[14]), y así sucesivamente. En el tercer paso se dividirán los elementos del arreglo en grupos, tomando en cuenta los elementos que se encuentran ahora a dos posiciones de distancia entre si y nuevamente se les ordenara por separado. En el primer grupo quedarán (A[l], A[3], A[5], A[7], A[9], A[ll], A[13], A[15])  y en el segundo (A [2], A[4], A[6], A[8], A[10], A[12], A[14], A[16]).

Finalmente se agruparan y ordenaran los elementos de manera normal; es decir, de uno en uno. Se presenta a continuación un ejemplo.

Ejemplo. Supongamos que se desea ordenar los elementos que se encuentran en el arreglo unidimensional A utilizando el método de Shell.

A:    15    67    08    16   44   27    12   35    56   21    13    28    60   36    07    10

EJEMPLO PAG 351

A continuación se presenta el algoritmo de ordenación por el método de Shell.

Shell (A, A7)
{Este algoritmo permite ordenar los elementos de un arreglo unidimensional utilizando el método de Shell. A es un arreglo unidimensional de N elementos}
{INT, I y AUX son variables de tipo entero. BAND es una variable de tipo booleano}

1. Hacer INT <- N + 1
2. Mientras (INT > 1) Repetir
      Hacer INT <- parte entera (INT / 2) y BAND  <- VERDADERO
      2.1. Mientras (BAND = VERDADERO) Repetir
              Hacer BAND  <- FALSO  e  I -1
              2.1.1. Mientras ((I  +  INT)  <  N) Repetir
                     2.1.1.1. Si A[I > A[I + INT] entonces
                               Hacer AUX <- A[ I ],  A[ I ] <- A[ I + INT ],
                                       A[I + INT] <- AUX  y
                                       BAND <- VERDADERO
                     2.1.1.2. {Fin del condicional del paso 2.1.1.1}
                     Hacer  I <- I  + 1
              2.1.2. {Fin del ciclo del paso 2.1.1}
      2.2 {Fin del ciclo del paso 2.1}
3. {Fin del ciclo del paso 2}

Análisis de eficiencia del método de Shell

El análisis de eficiencia del método de Shell es un problema muy complicado y aun no resuelto. Hasta el momento no se ha podido establecer la mejor secuencia de incrementos cuando n es grande. Cabe recordar que cada vez que se propone una secuencia de intervalos, es necesario correr el algoritmo para analizar su tiempo de ejecución.

En 1969, Pratt descubrió que el tiempo de ejecución del algoritmo es del orden de n*(log n)2. Unas pruebas exhaustivas realizadas para obtener la mejor secuencia de intervalos cuando el número de elementos del arreglo es igual a 8 arrojaron como resultado que la mejor secuencia corresponde a un intervalo de 1, que no es más que el método de inserción directa estudiado previamente. Estas pruebas también determinaron que el menor número de movimientos se registraba con la secuencia 3, 2, 1. Cabe aclarar que las pruebas exhaustivas corresponden al análisis de (8!) posibilidades; es decir, 40 320 casos diferentes.

Para concluir con el análisis de eficiencia de método de Shell, se menciona que estudios de Peterson y Russell, en la Universidad de Stanford, en 1971, muestran que las mejores secuencias para valores de N comprendidos entre 100 y 60 000 son las que se presentan en la Lista de secuencias , donde k = 0, 1, 2, 3,...

Listas de Secuencias

• l, 3, 5, 9, ... ,2k + l
• 1, 3, 7, 15, ..., 2k -l
• 1, 3, 5, 11, ...,(2k ± l)/3
• 1, 4, 13, 40,..., (3k + l)/2

Ejemplo en C

int i, j, increment, temp;

increment = 3;
while (increment > 0)
{
      for (i=0; i < array_size; i++)
      {
            j = i;
            temp = numbers[i];
            while ((j >= increment) && (numbers[j-increment] > temp))
            {
                  numbers[j] = numbers[j - increment];
                  j = j - increment;
            }
            numbers[j] = temp;
      }
      if (increment/2 != 0)
      increment = increment/2;
      else

            if (increment == 1)
                  increment = 0;
            else
                  increment = 1;
      }