public class QuickSort{
      public static void main(String args[]){
         int a[]={5,3,4,1,2,7,6};
         System.out.println("Origen:");
         imprimeArray(a);
         System.out.println("");
         quickSort(a);
         System.out.println("Ordenado:");
         imprimeArray(a);
      }
      public static void quickSort( int a[ ]){
         quickSort( a, 0, a.length-1 );
      }
      public static void swapReferences(int a[], int index1, int index2 ){
         int tmp = a[ index1 ];
         a[index1] = a[ index2];
         a[index2] = tmp;
      }
      private static void quickSort( int a[], int low, int high){
       //  System.out.println("ordenando qs: ");
       //  imprimeArray(a);
         if (low >= high) {  // Array vacío o de un solo elemento: nada que hacer
         return;
         } 
         else {    
         
         // ELECCIÓN DEL PIVOTE
         
         // La eficiencia del algoritmo depende en gran medida de la elección del pivote
         // La mejor opción sería la mediana, pero es demasiado costosa de calcular
         // Como solución de compromiso, se selecciona la mediana de 3 elementos: 
         // primero, centro y último
         
         // Ordenamos entre sí el primer elemento, el último y el del centro (mediana de tres)
            int middle = (low + high)/2; 
            if( a[ middle ]< a[ low ] )
               swapReferences( a, low, middle );
            if( a[ high ]< a[ low ])
               swapReferences( a, low, high );
            if( a[ high ]< a[ middle ] ) 
               swapReferences(a, middle, high );
         
            int pivot = a[ middle ]; // colocamos pivote (= mediana)
            System.out.println("mediana de tres: ");
            imprimeArray(a);
         // Apartamos temporalmente el pivote, para que no interfiera en la segmentación 
         // del resto de elementos del array
            swapReferences(a, middle, high-1);
         
            System.out.println("Aparto pivote: ");
            imprimeArray(a);
         // PARTICIÓN DEL ARRAY
         
            int i, j;                              
            for( i=low, j=high-1 ; i < j ; ){ // recorremos con i de izda a dcha con j de dcha a izda
            
            // i se mueve hasta llegar al primer elemento mayor que el pivote (desde la izquierda)
               while( a[ ++i ]< pivot );
            // j se mueve hasta llegar al primer elemento menor que el pivote (desde la derecha)
               while( pivot < a[ --j ] );
            System.out.println("i: "+i);
            System.out.println("j: "+j);
               if( i < j )                   // si no están bien colocados los intercambiamos 
                  swapReferences( a, i, j );
               else
                  break;
            
            }
         // Volvemos a colocar el pivote en su lugar
            swapReferences(a, i, high-1);
         // Todos los elementos a la izquiera del pivote son menores que éste y
         // todos los elementos a su derecha, mayores
         // (i = posición del pivote)

            System.out.println("low: "+low);
            System.out.println("high: "+high);
            System.out.println("pivot: "+pivot);

            imprimeArray(a);
            System.out.println("ordeno izdo");
            quickSort( a, low, i - 1 );     // ordenamos el fragmento izquierdo (elementos menores)
            System.out.println("ordeno dcho");
            quickSort( a, i + 1, high );    // ordenamos el fragmento derecho (elementos mayores)
         }
      
      }
      public static void imprimeArray(int a[]){
      
         for(int i=0;i<a.length;i++){
            System.out.print(a[i]);
         }
         System.out.println("");
      }
   }