miércoles, septiembre 29, 2010

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.

7 comentarios:

  1. Anónimo2:22 p.m.

    es un excelente metodo de ordenacion y muy facil de entender

    ResponderBorrar
  2. Antes de nada agradecerte la respuesta, me ha servido de mucho pero, tengo una pregunta, ¿El while por qué está al final? Muchas gracias!!!

    ResponderBorrar
  3. Otra pregunta... ¿Que hace j-=incremento? Muchas gracias

    ResponderBorrar
  4. Anónimo10:25 a.m.

    como es el codigo para matrices??...ayuda.. es para
    hoy

    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...