domingo, octubre 03, 2010

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.

4 comentarios:

  1. Anónimo5:04 p.m.

    no correo el programa

    ResponderBorrar
  2. Anónimo3:45 p.m.

    soy dorling de managua nicaragua, estudio en la Unan managua y no le entendi

    ResponderBorrar
  3. Anónimo4:42 p.m.

    solo le faltaba un signo de operador "+", el cual quedaria de la siguiente forma:

    public static void ShakerSort(int[] a1)
    {
    int final;
    int N = a1.Length;
    int limInferior = 0;
    int limSuperior = N-1;
    while(limInferior <= limSuperior)
    {
    for(int j=limInferior; ja1[j+1])
    {
    int tmp = a1[j];
    a1[j] = a1[j+1];
    a1[j+1] = tmp;
    }
    }
    limSuperior--;
    for(int j=limSuperior;j>limInferior; j--)
    {
    if(a1[j]<a1[j-1])
    {
    int tmp = a1[j];
    a1[j] = a1[j-1];
    a1[j-1] = tmp;
    }
    }
    limInferior++;
    }
    }

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...