metodo de ordenacion shell sort

Método shellsort

Introducción:
Hoy en día existen muchos métodos de ordenamiento en sistemas o programas de software por lo tanto es más fácil mantener ordenados los datos y así ser encontrados más fácilmente.
En este documento se hablara acerca de un método de ordenamiento el cual es llamado Shell sort el cual recibe ese nombre en honor a su autor Donald L. Shell, también se hablara sobresus comprobaciones, su función y su magnitud.

Que es el método shellsort?
El algoritmo de ordenación Shell Sort se base en el algoritmo de ordenación por inserción, el cual 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 distanciasrelativamente mayores (empezando con distancias iguales a la mitad del tamaño del vector), la cuales se van reduciendo rápidamente.

En que consiste el shellsort
Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald shell – y también método de inserción con incrementos decrecientes.En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño - por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía laclasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de mas de una posición.
Supongamos un vector de elementos
4          12        16        24        36        3
 
En el método de inserción directa, los saltos se hacen de una posición en una posición y se necesitaran cinco comparaciones. En el método de Shell, si los saltos son de dos posiciones, serealizaran comparaciones.
            4          12        16        24        36        3

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 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 laordenació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.

Método de Ordenamiento Shell sort.
El método de Shell es una versión...