QuickSort

QuickSort.

Concepto
Si bien el método de la burbuja era considerado como el peor método de ordenación simple o menos eficiente, el método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el array a ordenar en dos subarrays de forma que los elementos del subarray inferior sean más pequeños que los del subarray superior, y aplicamos el método reiteradamente, al final tendremos el array inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell.

Descripción del algoritmo
El algoritmo consta de los siguientes pasos:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Demostración de un caso particular

Supongamos que el número de elementos a ordenar es una potencia de dos, es decir, n = 2^k para algún natural k. Inmediatamente k = log₂(n), donde k es el número de divisiones que realizará el algoritmo.
En la primera fase del algoritmo habrá n comparaciones. En la segunda fase el algoritmo instanciará dos sublistas de tamaño aproximadamente n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n. En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.
En conclusión, el número total de comparaciones que hace el algoritmo es:
n + n + n + ..... + n = kn, donde k = log₂(n), por tanto el tiempo de ejecución del algoritmo en el mejor caso es O(n.log₂n).

Técnicas de elección del pivote

El algoritmo básico del método Quicksort consiste en tomar cualquier elemento de la lista al cual denominaremos como pivote, dependiendo de la partición en que se elija, el algoritmo será más o menos eficiente.

• Tomar un elemento cualquiera como pivote tiene la ventaja de no requerir ningún cálculo adicional, lo cual lo hace bastante rápido. Sin embargo, esta elección «a ciegas» siempre provoca que el algoritmo tenga un orden de O(n²) para ciertas permutaciones de los elementos en la lista.
• Otra opción puede ser recorrer la lista para saber de antemano qué elemento ocupará la posición central de la lista, para elegirlo como pivote. Esto puede hacerse en O(n) y asegura que hasta en el peor de los casos, el algoritmo sea O(n·log n). No obstante, el cálculo adicional rebaja bastante la eficiencia del algoritmo en el caso promedio.
• La opción a medio camino es tomar tres elementos de la lista - por ejemplo, el primero, el segundo, y el último - y compararlos, eligiendo el valor del medio como pivote.

Técnicas de reposicionamiento

Una idea preliminar para ubicar el pivote en su posición final sería contar la cantidad de elementos menores que él, y colocarlo un lugar más arriba, moviendo luego todos esos elementos menores que él a su izquierda, para que pueda aplicarse la recursividad.
Existe, no obstante, un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos índice izquierdo, y j, al que llamaremos índice derecho. El algoritmo es el siguiente:

• Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
• Cuando lista[i] sea mayor que el pivote y lista[j] sea menor, se intercambian los elementos en esas posiciones.
• Repetir esto hasta que se crucen los índices.
• El punto en que se cruzan los índices es la posición adecuada para colocar el pivote, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados). 

Operaciones
   Las operaciones de ordenamiento con quicksort, son el de elegir un pivote, el cual va a ser las comparaciones, y asi poder hacer comparaciones, ya que al tener el pivote podremos saber al momento de hacer las comparaciones, si movemos a la izquierda o a la derecha.


Programa

Package quicksort;

Public class Ordenador

{   
    public int[] quicksort(int numeros[])//…………………………captando valores enteros para quicksort
    {

        return quicksort(numeros,0,numeros.length-1); //…………….regresa el valor quicksort al arreglo

    }
    public int[] quicksort(int numeros[],int izq,int der) //…………declara números enteros de izquierda a derecha
    {
        if(izq>=der) //……………………..if si la condición de izquierda es igual a la derecha
            return numeros; //………………….retorna los valores numéricos
        int i=izq,d=der; //…………………… si el entero es igual a izquierda, derecha
        if(izq!=der) //……………………..si la condición de izquierda es igual a derecha
        {
        int pivote; //………………….el entero pivote
        int aux; //………………..int es auxiliar
        pivote = izq; //……………..el pivote va a la izquierda
        while(izq!=der) //……………………..mientras que la izquierda es igual a la derecha
        {          

         imprimeArreglo(numeros); //………………………imprime los arreglos de numeros

         while(numeros[der]>=numeros[pivote] && izq<der) //……………mientras que los números son

                   mayor igual de la derecha el pivote hará la acción de ordenarlos de izquierda a derecha
          der--;
          while(numeros[izq]<numeros[pivote] && izq<der) //………..mientras que los números de la izquierda

                                    son menor del pivote, se moverán de izquierda a derecha
         izq++;//………….incrementando los de la izquierda

         if(der!=izq) //……………..si la condición de la derecha sea diferente a la izquierda
         {
            aux = numeros[der]; //………………….auxiliar los números  de la derecha en arreglo
            numeros[der]= numeros[izq]; //…………….numeros de la derecha sean iguales a los de la izquierda
            numeros[izq]=aux;} //………………………….. auxiliar los números  de la izquierda en arreglo
        }
        if(izq==der)
        {
               //……………..si la condición de la izquierda es igual al de la derecha
            quicksort(numeros,i,izq-1); //………ordenamiento quicksort de números de la izquierda
            quicksort(numeros,izq+1,d); //………….. ordenamiento quicksort de números de la derecha
        }
        }
        else//………………….sino, retorna los números de ambos lados
            return numeros;
       return numeros;
    }
    public void imprimeArreglo(int arreglo[])//……………..imprime el arreglo
    {
        String imp="";
        for(int i=0;i<arreglo.length;i++)//………………ciclo del arreglo de quicksort
        {
            if(i!=arreglo.length-1) //………………….condición si el arreglo puede ejecutar el ciclo
            imp=imp+arreglo[i]+",";
            else
                imp=imp+arreglo[i]+"";

        }
        System.out.println(imp); //…………….imprimir resultados
    }
    public static void main(String[] args) {
        int array[] ={4,2,5,7,6,1,3};//……………………..numeros a ordenar en modo quicksort
     Ordenador a = new Ordenador();
     a.quicksort(array);
     }
     } 

LINK DE DESCARGA

http://www.megaupload.com/?d=NHFTZKCI

Videos
*********************************************************************************

*********************************************************************************

Bibliografia
http://es.wikipedia.org/wiki/Quicksort
http://www.genbetadev.com/algoritmos/implementando-el-algoritmo-quicksort