Shell sort en listas dobles

En este nuevo post hablare sobre como empleamos gracias al aprendizaje de las listas simples y dobles, el método de ordenamiento shell en una lista doblemente enlazada.

Para empezar hablare breve mente que es una lista doblemente enlazada y en que consiste el método de ordenamiento shell. Las listas dobles o doblemente enlazadas, son estructuras que se llenan o se cargan de elementos durante el tiempo de ejecución, con la ayuda de dos punteros; uno que apunte hacia el elemento anterior y el otro apuntando hacia el elemento siguiente. Si desean saber mas de las listas dobles entren aquí: http://es.ccm.net/faq/2872-listas-doblemente-enlazadas

El método de ordenamiento shell es un método por el cual, recibimos un array o en este caso una lista de elementos desordenados. Lo que se hace es definir un intervalo entre un elemento dividiendo entre 2 el tamaño de la lista o array, y otro para poder ordenarlos por partes, y repetir el ciclo, hasta obtener la lista ordenada de una forma mas rápida y eficiente que por un método de ordenación por burbuja.

Uso de Shell Sort en una lista doble

Para aplicar el  método shell sort en una lista doble es necesario entender la lógica para crear un código que asimile al método.

Hay que declarar dos nodos de tipo null( estos serán los que marcaran los intervalos de toda la lista), la mismo tiempo hay que declarar un contador iniciado en 0 y por ultimo un auxiliar de tipo nodo, esto es necesario porque en el método shell es necesario llevar el intervalo dependiendo de cuantos elementos tenga la lista o arreglo, declararemos un ciclo que mantenga al nodo cabeza sin apuntar a un elemento null, haciendo esto el contador declarado debe sumar cada vez que este proceso se cumpla.

Una vez se sepa el tamaño de la lista, lo siguiente sera dividir ese tamaño entre 2 como lo dice el método. El resultado es la posición donde pondremos el segundo nodo declarado para terminar el intervalo declarado con el nodo cabeza.
Cuando eso pase compararemos si el elemento del nodo cabeza se menor a el elemento en el nodo final, is es así entonces se mantendrá tal como esta y se adelantara una casilla cada nodo, si no, entonces se intercambiaran posiciones usando el auxiliar declarado anteriormente y para finalizar se repite el ciclo hasta que la lista quede completamente ordenada.
En resumen este es el código que deben generar:

public void shell() {
        Nodo q;
        Nodo p;
        int cont = 0;
        Nodo aux;
        q = this.cab;
        while (q != null) {
            q = q.getSig();
            cont++;
        }
        int k = cont / 2;
        while (k > 0) {
            q = this.cab;
            for (int i = 0; i < k; i++) {
                q = q.getSig();
            }
            p = this.cab;
            while (q != null) {
                if (p.getCod() > q.getCod()) {
                    aux = p;
                    p = this.exchange(p, q);
                    q = aux;
                }
                p = p.getSig();
                q = q.getSig();
            }
            k = k / 2;
        }
    }

Sin mas que decir espero que les haya servido.

REFERENCIAS

1. Listas Doblemente Enlazadas. [EN LINEA]. Web. septiembre del 2015. [Citado en 28 de Octubre de 2015]. Disponible en internet: <http://es.ccm.net/faq/2872-listas-doblemente-enlazadas>