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