Quick Sort

QuickSort.java

public void swap(int[] A, int x, int y){
  int temp = A[x];
  A[x] = A[y];
  A[y] = temp;
}

public void quickSort(int[] A, int first, int last){
  if (first >= last){
    return;
  }
  int pivotIndex = partition(A, first, last);
  quickSort(A, first, pivotIndex);
  quickSort(A, pivotIndex+1, last);
}

public int partition(int[] A, int first, int last){
  int pivot = A[(first + last)/2];
  while (first < last){
    while (A[first] < pivot){
      first++;
    }
    while (A[last] > pivot){
      last--;
    }
    swap(A, first, last);
  }
  return first;
}




//With output:

public class QuickSort
{
  public static void main(String[] args)
  {
    int[] array = {7, 4, 2, 8, 3, 1, 5, 6};
    
    quickSort(array, 0, array.length - 1);
    
    for (int i = 0; i < array.length; i++){
      System.out.print(String.format("%-3d", array[i]));
    }
    
  }
  
  public static void swap(int[] A, int x, int y){
    int temp = A[x];
    A[x] = A[y];
    A[y] = temp;
  }

  public static void quickSort(int[] A, int first, int last){
    if (first >= last){
      return;
    }
    int pivotIndex = partition(A, first, last);
    
    //start debug
    System.out.println("pivot: " + A[pivotIndex]);
    for (int i = first; i <= last; i++){
      System.out.print(String.format("%-3d", A[i]));
    }
    System.out.println();
    //end debug
    
    quickSort(A, first, pivotIndex);
    quickSort(A, pivotIndex+1, last);
  }

  public static int partition(int[] A, int first, int last){
    int pivot = A[(first + last)/2];
    while (first < last){
      while (A[first] < pivot){
        first++;
      }
      while (A[last] > pivot){
        last--;
      }
      swap(A, first, last);
    }
    return first;
  }
  
}

/*output:

pivot: 8
7  4  2  6  3  1  5  8  
pivot: 6
5  4  2  1  3  6  7  8  
pivot: 2
1  2  4  5  3  6  
pivot: 1
1  2  
pivot: 5
4  3  5  6  
pivot: 3
3  4  5  
pivot: 4
4  5  
pivot: 7
7  8  
1  2  3  4  5  6  7  8  

*/