Quicksort

QuickSort.java

class QuickSort {

  private int[] numbers;

  public static void main(String[] args) {
    int[] numbers = {2, 8, 7, 1, 3, 5, 6, 4};

    QuickSort q = new QuickSort();
    q.sort(numbers);
    for (int i : numbers) {
      System.out.print(i + " ");
    }
    System.out.println();
  }

  public void sort(int[] numbers) {
    this.numbers = numbers;
    quickSort(0, numbers.length-1);
  }

  private void quickSort(int start, int end) {
    if (start < end) {
      int pivot = partition(start, end);
      quickSort(start, pivot-1);
      quickSort(pivot+1, end);
    }
  }

  private int partition(int start, int end) {
    int pivot = numbers[end]; // random would be better
    int i = start -1;
    for (int j = start; j <= end-1; j++) {
      if (numbers[j] <= pivot) {
        i++;
        int tmp = numbers[j];
        numbers[j] = numbers[i];
        numbers[i] = tmp;
      }
    }
    int tmp = numbers[i+1];
    numbers[i+1] = numbers[end];
    numbers[end] = tmp;
    return i+1;
  }
}