# Quicksort

The following documents the state of an array throughout the application of a quick sort.

import java.util.Random;

public class QuickSorter {

///////// "helper" methods //////////

private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}

private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}

private static void printOrder(Comparable[] b) {
for (int i = 0; i < b.length; i++) {
System.out.print(b[i] + "  ");
}
System.out.println();
}

// needed for performance guarantee (using the quicksort algorithm
// sorted lists take O(n^2) time, whereas random lists take
// O(n ln n) time
private static void shuffle(Object[] a) {
// take elements i = 0..(n-1) in turn and swap them randomly
// with some position >= i
Random random = new Random();
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + random.nextInt(n-i);     // between i and N-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}

// for documenting the various stages of the sort...
private static void quickTrace(int lo, int j, int hi, Comparable[] a) {
System.out.print(lo + ((lo < 10) ? "  " : " "));
System.out.print("  " + j  + ((j  < 10) ? "   " : "  "));
System.out.print(hi + ((hi < 10) ? "   " : "  "));
printOrder(a);
}

public static void printIndices(Comparable[] b) {
System.out.print("lo pivot hi  ");

for (int i = 0; i < b.length; i++) {
System.out.print(i + " " + (i < 10 ? " " : ""));
}
System.out.println();
System.out.print("-------------");

for (int i = 0; i < b.length; i++) {
System.out.print("---");
}
System.out.println();
}

///////////////////////////////////////

private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi+1;
while (true) {

while (less(a[++i], a[lo]))   //find item on left to swap
if (i == hi) break;

while (less(a[lo], a[--j]))   //find item on right to swap
if (j == lo) break;

if (i >= j) break;            //check if pointers cross and we are

exch(a, i, j);                //swap
System.out.print("             ");
printOrder(a);
}

exch(a, lo, j);  // final exchange (with pivot)

return j;        // return index of item now known to be in place
}

private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;   // base case of one element
int j = partition(a, lo, hi);
quickTrace(lo, j, hi, a);
sort(a, lo, j-1);
sort(a, j+1, hi);
}

public static void sort(Comparable[] a) {
System.out.print("             ");
printOrder(a);

//Shuffle array a (needed for performance guarantee)
shuffle(a);
System.out.print("             ");
printOrder(a);
System.out.println("               (after shuffling for performance guarantee)\n");

sort(a, 0, a.length-1);
}

public static void main(String[] args) {
Character[] a = {'K','R','A','T','E','L','E','P','U','I','M','Q','C','X','O','S'};

System.out.println("Order before quicksort application:");
printOrder(a);
System.out.println();

printIndices(a);
QuickSorter.sort(a);
System.out.println();
System.out.println("Order after quicksort application:");
printOrder(a);
}
}


### Output

The following shows one possibility for the result of running the above code. (Note, different runs will shuffle the elements differently, which of course impacts the rest of the output.)

To provide a clearer trace of the quicksort algorithm --in addition to showing the state of the array after each exchange -- the low and high values for the subset of the array examined and the ultimate position of each pivot are also provided each time a pivot value is moved.

Order before quicksort application:
K  R  A  T  E  L  E  P  U  I  M  Q  C  X  O  S

lo pivot hi  0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
------------------------------------------------------------
K  R  A  T  E  L  E  P  U  I  M  Q  C  X  O  S
S  K  X  Q  E  A  R  I  C  E  T  U  L  P  M  O
(after shuffling for performance guarantee)

S  K  O  Q  E  A  R  I  C  E  T  U  L  P  M  X
S  K  O  Q  E  A  R  I  C  E  M  U  L  P  T  X
S  K  O  Q  E  A  R  I  C  E  M  P  L  U  T  X
0    12  15  L  K  O  Q  E  A  R  I  C  E  M  P  S  U  T  X
L  K  E  Q  E  A  R  I  C  O  M  P  S  U  T  X
L  K  E  C  E  A  R  I  Q  O  M  P  S  U  T  X
L  K  E  C  E  A  I  R  Q  O  M  P  S  U  T  X
0    6   11  I  K  E  C  E  A  L  R  Q  O  M  P  S  U  T  X
I  A  E  C  E  K  L  R  Q  O  M  P  S  U  T  X
0    4   5   E  A  E  C  I  K  L  R  Q  O  M  P  S  U  T  X
E  A  C  E  I  K  L  R  Q  O  M  P  S  U  T  X
0    2   3   C  A  E  E  I  K  L  R  Q  O  M  P  S  U  T  X
0    1   1   A  C  E  E  I  K  L  R  Q  O  M  P  S  U  T  X
7    11  11  A  C  E  E  I  K  L  P  Q  O  M  R  S  U  T  X
A  C  E  E  I  K  L  P  M  O  Q  R  S  U  T  X
7    9   10  A  C  E  E  I  K  L  O  M  P  Q  R  S  U  T  X
7    8   8   A  C  E  E  I  K  L  M  O  P  Q  R  S  U  T  X
13   14  15  A  C  E  E  I  K  L  M  O  P  Q  R  S  T  U  X

Order after quicksort application:
A  C  E  E  I  K  L  M  O  P  Q  R  S  T  U  X