Ordenación por Montículos - Heap Sort

El algoritmo de ordenación por montículos o Heap Sort recorre el conjunto de elementos desde la posición de la mitad hasta la primera organizando el montículo correspondiente a dicho elemento.  Una vez terminado este proceso, se inicia el proceso de ordenación intercambiando el primer elemento por el último del arreglo y reorganizando el montículo a partir de la primera posición.

// Ordenacion por monticulos - HeapSort
    public static void ordenacionMonticulos(int[] v) {
        final int N = v.length;
        for(int nodo = N/2; nodo>=0; nodo--) hacerMonticulo(v, nodo, N-1);
        for(int nodo = N-1; nodo>=0; nodo--) {
            int tmp = v[0];
            v[0]    = v[nodo];
            v[nodo] = tmp;
            hacerMonticulo(v, 0, nodo-1);
        }
    }

    public static void hacerMonticulo(int[] v, int nodo, int fin) {
        int izq = 2*nodo+1;
        int der = izq+1;
        int may;
        if(izq>fin) return;
        if(der>fin) may=izq;
        else may= v[izq]>v[der]?izq:der;
        if(v[nodo] < v[may]) {
            int tmp = v[nodo];
            v[nodo] = v[may];
            v[may]  = tmp;
            hacerMonticulo(v, may, fin);
        }
    }

La complejidad del algoritmo de ordenación por montículos es O(n log n) teniendo en cuenta que el proceso de organizar el montículo en el peor caso solamente tiene que hacer intercambios sobre una sola línea de elementos desde la raíz del ábol hasta alguna de las hojas para un máximo de log n intercambios.

Ordenación Rápida - Quick Sort

El algoritmo de ordenación rápida, o QuickSort, se implementa a través de un procedimiento recursivo que implementa tres pasos:

1. Selecciona un elemento de referencia o pivote, con base en el cual se reorganizará el arreglo a ordenar
2. Reorganiza el arreglo de tal manera que a la izquierda del pivote se sitúen todos los elementos menores a él y a la derecha los mayores.
3. Se invoca recursivamente el método de ordenación tanto para el subconjunto de elementos de la izquierda como para el de la derecha.

En la siguiente implementación en JAVA, el proceso de ordenación está implementado en el método quickSort, mientras que el método ordenacionRapida sirve para presentar al usuario final un mismo estilo de invocación del algoritmo.

// Ordenacion rapida: Quick Sort
    public static void ordenacionRapida(int[] v) {
        final int N = v.length;
        quickSort(v,0,N-1);
    }

    public static void quickSort(int[] v, int inicio, int fin) {
        if(inicio>=fin) return ;
        int pivote = v[inicio];
        int izq    = inicio+1;
        int der    = fin;
        while(izq<=der) {
            while(izq<=fin   && v[izq]< pivote) izq++;
            while(der>inicio && v[der]>=pivote) der--;
            if(izq<der) {
                int tmp = v[izq];
                v[izq]  = v[der];
                v[der]  = tmp;
            }
        }
        if(der>inicio) {
            int tmp  = v[inicio];
            v[inicio]= v[der];
            v[der]   = tmp;
        }
        quickSort(v,inicio, der-1);
        quickSort(v, der+1, fin);
    }

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2).  La solución a esta ecuación se puede comprobar utilizando la tecnología del motor de cálculo WolframAlpha 

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.

Ordenación por Combinación - Merge Sort

El algoritmo de ordenación por combinación o Merge Sort, basado en la técnica Divide y Vencerás, ordena recursivamente un conjunto de elementos dividiéndolo en dos, ordenando cada una de estas partes en forma independiente y combinando los dos resultados.

Este código en el lenguaje de programación JAVA 1.6 recibe como entrada un arreglo de números enteros denominado v, lo parte utilizando el método copyOfRange de la clase java.util.Arrays, se llama recursivamente con cada una de las dos partes como argumento y, una vez terminada la ordenación de dichas partes, invoca al proceso de combinación de las dos respuestas implementado en el método combinar, el cual recibe como entrada el arreglo original y las dos mitades del mismo previamente ordenadas que serán combinadas en el arreglo original.

// Algoritmo de ordenacion por combinacion: Merge Sort
    public static void ordenacionCombinacion(int[] v) {
        final int N = v.length;
        if(N<=1) return;
        int mitad=N/2;
        int[] izq = Arrays.copyOfRange(v, 0, mitad);
        int[] der = Arrays.copyOfRange(v, mitad, N);
        ordenacionCombinacion(izq);
        ordenacionCombinacion(der);
        combinar(v, izq, der);
    }

    public static void combinar(int[] resp, int[] izq, int[] der) {
        int i = 0;
        int j = 0;
        for(int k=0; k<resp.length;k++) {
            if(i>=izq.length) { resp[k]=der[j++]; continue; }
            if(j>=der.length) { resp[k]=izq[i++]; continue; }
            resp[k]=(izq[i]<der[j])?izq[i++]:der[j++];
        }
    }

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2).  La solución a la misma se puede comprobar gracias a la tecnologías del sitio WolframAlpha