import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Something that can sort using quickSort.
 */
public class Quicksort
{
  public static void main(String[] args) 
    throws Exception
  {
    // Prepare input and screenput.
    BufferedReader keyboard = 
      new BufferedReader(new InputStreamReader(System.in));
    PrintWriter screen = new PrintWriter(System.out, true);

    //Original array
    Object[] unsorted = new Object[20]; 
    for (int i = 0; i < unsorted.length; i++){
      unsorted[i] = new Long(Math.round(Math.random()* 100));
    } //for

    // Print the array
    screen.print( "The unsorted list is: (");
    for(int i = 0; i < unsorted.length; i++){
      screen.print(unsorted[i] + " ");
    }
    screen.println(")");  

    // Sort it
    quicksort(unsorted, 0, unsorted.length-1, new NumberComparator());

    // Print the result
    screen.print( "The sorted list is: (");
    for(int i = 0; i < unsorted.length; i++){
      screen.print(unsorted[i] + " ");
    }
    screen.println(")");

  } // main(String[])

  private static void quicksort(Object[] stuff, 
                                int lb, int ub,
                                GComparator compare)
  {
    if (ub <= lb) return;
    int part = partition(stuff, lb, ub, compare);
    quicksort(stuff, lb, part-1, compare);
    quicksort(stuff, part+1, ub, compare);
  } // quicksort()

  private static int partition(Object[] stuff, 
                               int lb, int ub, 
                               GComparator compare)
  {
    // Pick a pivot and put it in the leftmost position.
    Object pivot = stuff[lb];
    // Start at the left and right and work your way inward.
    int left = lb;
    int right = ub;
    while (left < right) {
      // Move the right index left until you hit a small thing.
      while ((left < right) && (compare.mayPrecede(pivot, stuff[right])))
        --right;
      // Move the left index right until you hit a large thing or
      // cross over to the other side.
      while ((left < right) && (compare.mayPrecede(stuff[left], pivot)))
        ++left;
      // Swap 'em
      swap(stuff, left, right);
    } // while
    // Put the pivot in the middle.  Note the hidden assumption that
    // left always refers to a small element when you reach this point.
    swap(stuff, lb, left);
    // Return the position of the pivot
    return left;
  } // partition()

  /**
   * Swap the values at positions x and y in the array stuff.
   */
  private static void swap(Object[] stuff, int x, int y) {
    Object tmp = stuff[x];
    stuff[x] = stuff[y];
    stuff[y] = tmp;
  } // swap(Object, x, y)
} // class Quicksort