Thursday, October 22, 2015

QuickSort in Java

 public static void quicksort(int[] A) {
  quicksort(A, 0, A.length-1);
 }
 
 private static void quicksort(int[] A, int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(A, lo,hi);
  quicksort(A, lo, p-1);
  quicksort(A, p+1, hi);
 }
 
 private static int partition(int[] A, int lo, int hi) {
  int i = lo+1;
  int j = hi;
  while (i <= j) {
   while (A[i] < A[lo]) {
    i++;
    if (i > hi) break;
   }
   while (A[j] > A[lo]) {
    j--;
   }
   if (i <= j) {
    swap(A, i, j); 
    i++;
    j--;
   }
  }
  swap(A, lo, j); 
  return j;
 }

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


No comments:

Post a Comment