* Dentro de los métodos Indirectos

1. Método de Ordenamiento Shell

Técnica del Método: 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. Se considera que el método Shell es una mejora de los métodos de inserción directa. 

En el álgoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es el más pequeño hay que realizar muchas comparaciones antes de colocarlo en su lugar definitivo.

El algoritmo de Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con ello se consigue que la ordenación sea más rápida. 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.

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.

Ejemplo:

Obtener las secuencias parciales del vector al aplicar el método Shell para ordenar en orden creciente la lista:

                                                             6 1 5 2 3 4 0

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

Codificación de la Función de Método de Shell

void Shell(int 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;

       else

  {

  int temp;

  temp=a[j];

  a[j]=a[k];

                   a[k]=temp;

  j-=intervalo;

  }

        }

   }

              intervalo=intervalo/2;

     }

}

Prueba de Escritorio: