QuickSort

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Test test = new Test();
    test.runTests();
  }
}

class Test{
  private QuickSort quickSort;
  private int[] array;
  
  public void runTests(){
    startTest();
    System.out.println("Before: " + Arrays.toString(array));
    quickSort.partition(array, 0, array.length);
    System.out.println("After Partition: " + Arrays.toString(array));
    
    startTest();
    quickSort.sort(array, 0, array.length);
    System.out.println("After Sort: " + Arrays.toString(array));
  }
  
  private void startTest(){
    quickSort = new QuickSort();
    array = new int[]{2, 8, 7, 1, 3, 5, 6, 4};
  }
}

class QuickSort{
  public void sort(int[] array, int head, int tail){
    if(tail > head){
      int partitionIndex = partition(array, head, tail);
      sort(array, head, partitionIndex);
      sort(array, partitionIndex + 1, tail);
    }
  }
  
  public int partition(int[] array, int head, int tail){
    int leftTail = head - 1, rightTail = head;
    int pivotIndex = tail - 1;
    int tmp = 0;
    
    while(rightTail < pivotIndex){
      if(array[rightTail] <= array[pivotIndex]){ // exchange
        leftTail++;
        tmp = array[leftTail];
        array[leftTail] = array[rightTail];
        array[rightTail] = tmp;
      }
      rightTail++;
    }
    // move pivot into the right spot
    tmp = array[leftTail + 1];
    array[leftTail + 1] = array[pivotIndex];
    array[pivotIndex] = tmp;
    
    return leftTail + 1;
  }
}