Quicksort
by Isai Damier, Android Engineer @ Google

/*****************************************************************************
 * Author: Isai Damier
 * Title: QuickSort.java
 * Project: geekviewpoint
 * Package: algorithm.sorting
 *
 * Statement: Given a disordered list of integers (or any other items),
 *  rearrange the integers in natural order.
 *
 * Sample Input: {8,5,3,1,9,6,0,7,4,2}
 *
 * Sample Output: {0,1,2,3,4,5,6,7,8,9}
 *
 * Time Complexity of Solution:
 *  Best = Average = O(n*log(n)); Worst = O(n^2).
 *
 * Approach:
 *  Quicksort is admirably known as the algorithm that sorts an array while
 *  preparing to sort it. For contrast, recall that merge sort first
 *  partitions an array into smaller pieces, then sorts each piece, then
 *  merge the pieces back. Quicksort actually sorts the array during the
 *  partition phase.
 *
 *  Quicksort works by selecting an element called a pivot and splitting the
 *  array around that pivot such that all the elements in, say, the left
 *  sub-array are less than pivot and all the elements in the right sub-array
 *  are greater than pivot. The splitting continues until the array can no
 *  longer be broken into pieces. That's it. Quicksort is done.
 *
 *  All this fussing about quicksort sorting while preparing to sort may give
 *  the impression that it is better than mergesort, but its not. In practice
 *  their time complexity is about the same -- with one funny exception.
 *  Because quicksort picks its pivot randomly, there is a practically
 *  impossible possibility that the algorithm may take O(n^2) to compute.
 *
 *  The aforementioned notwithstanding, quicksort is better than mergesort if
 *  you consider memory usage. Quicksort is an in-place algorithm,
 *  requiring no additional storage to work.
 * **************************************************************************/ 
 public void quicksort(int[] input) {
    quicksort(input, 0, input.length - 1);
  }

  private void quicksort(int[] input, int first, int last) {
    if (first < last) {
      int pivot = partition(input, first, last);
      quicksort(input, first, pivot - 1);
      quicksort(input, pivot + 1, last);
    }
  }

  private int partition(int[] input, int first, int last) {
    int pivot = first + new Random().nextInt(last - first + 1);
    swap(input, pivot, last);
    for (int i = first; i < last; i++) {
      if (input[i] <= input[last]) {
        swap(input, i, first);
        first++;
      }
    }
    swap(input, first, last);
    return first;
  }

  private void swap(int[] input, int a, int b) {
    int tmp = input[a];
    input[a] = input[b];
    input[b] = tmp;
  }

import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {
  
  /**
   * Test of quicksort method, of class Sorting.
   */
  @Test
  public void testQuicksort() {
    System.out.println(""quicksort"");
    int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
    Sorting instance = new Sorting();
    instance.quicksort(input);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""quicksort method fails."");
      }
    }
    System.out.println(Arrays.toString(input));
  }
}