Quicksort.java

import java.util.*;
class Quicksort {
  public static void qsort(int[] ints, int fi, int li) {
    /* the recursive procedure */
    if (fi < li) {
      //int p = partition(ints, fi, li);
      int p = partition1(ints, fi, li);
      qsort(ints, fi, p - 1);
      qsort(ints, p + 1, li);
    }
  }
  public static int partition(int[] ints, int fi, int li) {
  /* Of course, the partitioning is the key procedure here */
    int boundary = fi;
    int pivot = ints[fi];
    int current = fi + 1;
    while (current <= li) {
      if (ints[current] < pivot) {
        swap(ints, current, boundary + 1);
        boundary++;
      }
      current++;
    }
    swap(ints, fi, boundary);
    return boundary;
    /* this procedure was due to Nico Lomuto */
  }
  public static int partition1(int[] a, int p, int r) {
    //this is something I have written
    int pivot = a[p];
    int i = p + 1;
    int j = i - 1;
    while (i <= r) {
      if (a[i] < pivot) {
        a[j] = a[i];
        a[i] = a[j+1];
        j++;
      }
      i++;
    }
    a[j] = pivot;
    return j;
  }
  private static void swap(int[] ints, int i1, int i2) {
    int tmp = ints[i2];
    ints[i2] = ints[i1];
    ints[i1] = tmp;
  }
  public static void main(String... args) {
    int[] a = generateRandomArray(Integer.valueOf(args[0]), Integer.valueOf(args[1]));
    System.out.println("unsorted: " + Arrays.toString(a));
    qsort(a, 0, a.length-1);
    System.out.println("sorted: " + Arrays.toString(a));
    System.out.println("Is Sorted?: " + isSorted(a));
  }
  static int[] generateRandomArray(int length, int max) {
    Random r = new Random();
    int[] a = new int[length];
    for (int i = 0; i < length; i++)
      a[i] = r.nextInt(max);
    return a;
  }
  static boolean isSorted(int[] a) {
    // for now, check if it is non-decreasing
    for (int i = 0; i < a.length-1; i++) 
      if (a[i] > a[i+1])
        return false;
    return true;
  }
}