External Exam Download Resources Web Applications Games Recycle Bin

quick sort


The quick sort algorithm uses recursion:

quickSort(array[])
BEGIN
  IF array[] is empty THEN don't sort!
  ELSE
    {
      SELECT a random pivot (often the last element)
      SPLIT array in half:
        left[] with elements ≤ pivot
        right[] with elements > pivot
      quickSort(left[])
      quickSort(right[])
    }
  JOIN left[] + pivot + right[]
END
and in java:
public class QuickSort {
 public static void main(String[] args) {
  int[] y = { 9, 2, 4, 7, 3, 7, 10 };
  int low = 0;
  int high = y.length - 1;
  quickSort(y, low, high);
  for(int x=0; x<y.length; x++) {System.out.println(y[x]);}
 }
 
 public static void quickSort(int[] arr, int low, int high) {
  if (arr == null || arr.length == 0)
   return;
 
  if (low >= high)
   return;
 
  // pick the pivot:
  int middle = low + (high - low) / 2;
  int pivot = arr[middle];
 
  // make left < pivot and right > pivot:
  int i = low, j = high;
  while (i <= j) {
   while (arr[i] < pivot) {
    i++;
   }
 
   while (arr[j] > pivot) {
    j--;
   }
 
   if (i <= j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++;
    j--;
   }
  }
 
  // recursively sort the two sub parts:
  if (low < j)
   quickSort(arr, low, j);
 
  if (high > i)
   quickSort(arr, i, high);
 }
}