QuickSort es un algoritmo basado en el principio “divide y vencerás”. Es una de los algoritmos más rápidos conocidos para ordenar. Este método es recursivo aunque existen versiones con formas iterativas que lo hacen aún más rápido. Su funcionamiento es de la siguiente manera:

• Se elige un numero del vector como referencia, al que se le llamará “pivote”.

• Reordenar el arreglo de tal forma que los elementos menores al pivote queden en el lado izquierdo y al lado derecho los elementos mayores.

• Se hace uso de la recursividad para ordenar tanto el conjunto de la izquierda como el de la derecha.
  

Tenemos nuestro vector original:

{20,12,28,24,8,4,16}

Obtenemos variables:

inicio=0; fin=6; pivote=20;

elemIzq=1;

elemDer=6;

Recursivo 1

Iteración 1 del ciclo while.

{20,12,28,24,8,4,16}

Compara 12 – 16, no hay cambio.

Iteracion 2

{20,12,28,24,8,4,16}

Cambia 28 por 16.

{20,12,16,24,8,4,28}

Iteracion 3

{20,12,16,24,8,4,28}

Cambia 24 por 4.

{20,12,16,4,8,24,28}

Cambia 8 por 20.

{8,12,16,4,20,24,28}

Recursividad 2-1

inicio=0; fin=3; pivote=8;

elemIzq=1;

elemDer=3;

Iteracion 1:

{8,12,16,4,20,24,28}

Cambia 4 por 12

{8,4,16,12,20,24,28}

Cambia 8 por 4

{4,8,16,12,20,24,28}

Recursividad 2.2

inicio=2; fin=3; pivote=16;

elemIzq=3;

elemDer=3;

{4,8,16,12,20,24,28}

cambia 16 por 12.

{4,8,12,16,20,24,28}

Nuestro vector ya esta ordenado pero falta terminar el proceso recursivo.

Recursividad 3.1

No hay cambios, el vector ya esta ordenado.

Recursividad 3.2

No hay cambios, el vector ya esta ordenado.

       public static void quickSort(int vec[], int inicio, int fin){
                if(inicio>=fin) return;
                int pivote=vec[inicio];
                int elemIzq=inicio+1;
                int elemDer=fin;
                while(elemIzq<=elemDer){
                        while(elemIzq<=fin && vec[elemIzq]<pivote){
                                elemIzq++;
                        }
                        while(elemDer>inicio && vec[elemDer]>=pivote){
                                elemDer--;
                        }
                        if(elemIzq<elemDer){
                                int temp=vec[elemIzq];
                                vec[elemIzq]=vec[elemDer];
                                vec[elemDer]=temp;
                        }
                }
                
                if(elemDer>inicio){
                        int temp=vec[inicio];
                        vec[inicio]=vec[elemDer];
                        vec[elemDer]=temp;
                }
                quickSort(vec, inicio, elemDer-1);
                quickSort(vec, elemDer+1, fin);
        }

public class QuickSort {
        
        private static int vec[]={20,12,28,24,8,4,16};
        
        public static void main(String[] args) {
                System.out.println("Vector original");
                imprimirVector(vec);
                ordenacionRapida(vec);
                System.out.println("\nVector ordenado");
                imprimirVector(vec);
        }

        public static void ordenacionRapida(int vec[]){
                final int N=vec.length;
                quickSort(vec, 0, N-1);
        }
        
        public static void quickSort(int vec[], int inicio, int fin){
                if(inicio>=fin) return;
                int pivote=vec[inicio];
                int elemIzq=inicio+1;
                int elemDer=fin;
                while(elemIzq<=elemDer){
                        while(elemIzq<=fin && vec[elemIzq]<pivote){
                                elemIzq++;
                        }
                        while(elemDer>inicio && vec[elemDer]>=pivote){
                                elemDer--;
                        }
                        if(elemIzq<elemDer){
                                int temp=vec[elemIzq];
                                vec[elemIzq]=vec[elemDer];
                                vec[elemDer]=temp;
                        }
                }
                
                if(elemDer>inicio){
                        int temp=vec[inicio];
                        vec[inicio]=vec[elemDer];
                        vec[elemDer]=temp;
                }
                quickSort(vec, inicio, elemDer-1);
                quickSort(vec, elemDer+1, fin);
        }
        
        public static void imprimirVector(int vec[]){
                for(int i=0;i<vec.length;i++){
                        System.out.print(vec[i]+" ");
                }
        }
        
}