Ordenación Shaker

El algoritmo de ordenación por el método Shaker, también conocido como "Cocktail" o "Sacudida" es una mejora del método de la burbuja en la cual el proceso se realiza tanto desde la primera posición a la última del arreglo como en sentido inverso, evitando así que los elementos más pequeños tarden un mayor tiempo en "ascender" a las posiciones superiores.

La implementación de este algoritmo en lenguaje JAVA es la siguiente:

// Algoritmo de ordenacion Shaker Sort
    public static void ordenacionShaker(int[] v) {
        final int N = v.length;
        int limInferior = 0;
        int limSuperior = N-1;
        while(limInferior <= limSuperior) {
            for(int j=limInferior; j<limSuperior; j++) {
                if(v[j]>v[j 1]) {
                    int tmp = v[j];
                    v[j]    = v[j+1];
                    v[j+1]  = tmp;
                }
            }
            limSuperior--;
            for(int j=limSuperior;j>limInferior; j--) {
                if(v[j]<v[j-1]) {
                    int tmp = v[j];
                    v[j]    = v[j-1];
                    v[j-1]  = tmp;
                }
            }
            limInferior++;
        }
    }

La complejidad del algoritmo es cuadrática, puesto que si bien mejora un poco el rendimiento del método de la burbuja, no cambia el hecho de recorrer el arreglo una vez por cada cada elemento que se quiere dejar en su posición correcta. Se puede probar con la ecuación de recurrencias T(n) = k n + T(n-1) con la tecnología del motor de cálculo WolframAlpha.