Shell Sort

El algoritmo de ordenación Shell Sort se base en el algoritmo de ordenación por inserción, el cuál tiene un muy buen desempeño si el vector está relativamente ordenado.  Entonces, teniendo esto como premisa, el Shell Sort, ordena por inserción subconjuntos del vector que están separados entre sí por distancias relativamente mayores (empezando con distancias iguales a la mitad del tamaño del vector), la cuales se van reduciendo rápidamente.

El siguiente código escrito en el lenguaje JAVA recibe como parámetro el conjunto de elementos representado en un arreglo de números enteros y define inicialmente el incremento como la mitad del tamaño del vector, entonces se ordenan por inserción los elementos de las posiciones v[0] y v[n/2], luego los de las posiciones v[1] y v[n/2] +1, y así sucesivamente.  Cuando termina este proceso, se divide por dos el tamaño del incremento y se repite el proceso hasta que el incremento sea igual a 1, en cuyo caso su comportamiento sería exactamente el del algoritmo de ordenación por inserción.

// Algoritmo de ordenacion ShellSort
    public static void ordenacionShell(int[] v) {
        final int N = v.length;
        int incremento = N;
        do {
            incremento = incremento / 2;
            for (int k = 0; k < incremento; k++) {
                for (int i = incremento + k; i < N; i += incremento) {
                    int j = i;
                    while (j - incremento >= 0 && v[j] < v[j - incremento]) {
                        int tmp = v[j];
                        v[j] = v[j - incremento];
                        v[j - incremento] = tmp;
                        j -= incremento;
                    }
                }
            }
        } while (incremento > 1);
    }

En cuanto a la complejidad del algoritmo, ésta tiende a ser O(n log n), teniendo en cuenta que este método se basa en la ordenación por inserción la cual tiende a ser O(n) en el mejor de los casos (es decir, cuando el vector está casi ordenado), y que el proceso de ordenación por inserción se repite tantas veces como tarde la variable incremento en llegar al valor de 1, que es aproximadamente el logaritmo en base 2 del tamaño del vector.