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.

3 comentarios:

Anónimo dijo...

no correo el programa

Anónimo dijo...

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

Anónimo dijo...

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++;
}
}

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar