Quicksort

gistfile1.txt

public static void quicksort(int[] array)
  {  
    array = quicksort(array, 0, array.length-1);
  } 
  private static int[] quicksort(int[] array, int lo, int hi)   { 
      if (hi > lo)
      { 
        int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
        int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
        quicksort(array, lo, newPivotIndex-1);
        quicksort(array, newPivotIndex+1, hi); 
     }
      return (int[]) array;
   }
   private static int partition(int[] array, int lo, int hi, int pivotIndex)
   {
     int pivotValue = array[ pivotIndex ];
      swap(array, pivotIndex, hi); //send to the back
     int index = lo;
     for (int i = lo; i < hi; i++)
      {
         if ( (array[i])<=(pivotValue))
        {
           swap(array, i, index);
           index++;
        }
    }
     swap(array, hi, index);
      return index;
  }

  private static void swap(int[] array, int i, int j)
   {
      int temp = array[i];
      array[i] = array[j];  
      array[j] = temp;  
  }

PseudoCode

function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex