El algoritmo de ordenación Shell está basada en el algoritmo de ordenación por inserción. Tiene mejores resultados que el algoritmo de Burbuja, Selección o Inserción directa.

El ShellSort ordena por inserción de subconjuntos del vector que están separados entre sí por iguales a la mitad del tamaño del vector, es decir, va armando subvectores de tamaño igual a k/2, e intercambiando valores, los cuales se van reduciendo rápidamente.

Ejemplo.

Tenemos el vector original.

Iteración 1:

Se formarán subvectores en saltos de 5, es decir el primer subvector esta compuesto par la posición 0, 5 y 11 del vector original (Color rojo).

El segundo subvector estará conformado por la posición 1 y 7 del vector original (Color verde).

Y así sucesivamente hasta tener todo los elementos en un subvector.

En total tenemos 5 subvectores, estos subvectores se ordenan internamente y regresan al vector original con las posiciones ordenadas.

Nuevo vector después de iteración 1:

Iteración 2:

Se modifica K, K=5/2=2.

Ahora los saltos se hacen de 2 en 2 para formar los nuevos subvectores.

De ésta forma se crean dos subvectores (rojo y verde), se ordenan internamente y se regresan con las posiciones ordenadas por cada subvector.

Se crea el nuevo vector con las nuevos números ordenados.

Iteración 3:

Se modifica k. K=2/2=1.

Cuando k=1 sólo podenos obtener 1 subvector; el vector original. Cuando k=1 Shell funaciona igual que el algoritmo de inserción dejando así el vector ordenado.

public static int[] ordenacionShell(int vec[]){
                int cont=0;
                final int N=vec.length; 
                int k=N/2;
                   while (k>=1){ 
                     for (int i = 0; i < k; i++){
                       //para cada subvector recorremos sus elementos
                       for (int j = k+i; j < N; j+= k)
                       {
                         int v = vec[j];
                         int n = j - k;
                         while (n>=0&& vec[n] >v){
                           vec[n + k] = vec[n];
                           n-=k;
                         }
                         vec[n + k] = v;
                       } 
                     } 
                   //obtenemos un nuevo salto
                   k /= 2;
                   } 
                   return vec;
        }

public class Shell {

        public static void main(String[] args) {
                int vec[]={45,17,23,67,21,55,8,18,89,26,58};
                System.out.println("Vector original");
                imprimirVector(vec);
                System.out.println("\n");
                vec=ordenacionShell(vec);
                imprimirVector(vec);
        }

        public static int[] ordenacionShell(int vec[]){
                int cont=0;
                final int N=vec.length; 
                int k=N/2;
                   while (k>=1){ 
                     for (int i = 0; i < k; i++){
                       //para cada subvector recorremos sus elementos
                       for (int j = k+i; j < N; j+= k)
                       {
                         int v = vec[j];
                         int n = j - k;
                         while (n>=0&& vec[n] >v){
                           vec[n + k] = vec[n];
                           n-=k;
                         }
                         vec[n + k] = v;
                       } 
                     } 
                   //obtenemos un nuevo salto
                   k /= 2;
                   System.out.print("iteracion: "+(++cont)+": ");imprimirVector(vec);System.out.println();
                   } 
                   return vec;
        }
        
        public static void imprimirVector(int vec[]){
                for(int i=0;i<vec.length;i++){
                        System.out.print(vec[i]+" ");
                }
        }

}