<![CDATA[
// Stuart Reges handout #29
// 11/23/05
//
// Class Sorter3 provides an implementation of the quicksort algorithm. It has
// the following public methods:
// public static <T extends Comparable<T>> void sort(List<T> list)
// public static void sort(Object[] list, int low, int high)
// public static void sort(Object[] list)
import java.util.*;
public class Sorter3 {
public static void main(String[] args) {
int n = 100000;
List<String> list1 = new LinkedList<String>();
List<String> list2 = new LinkedList<String>();
Random r = new Random();
for (int i = 0; i < n; i++) {
String text = "some text with #" + r.nextInt(2 * n);
list1.add(text);
list2.add(text);
}
long start = System.currentTimeMillis();
sort(list1);
double elapsed1 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("quicksort took " + elapsed1 + " seconds");
System.out.println();
start = System.currentTimeMillis();
Collections.sort(list2);
double elapsed2 = (System.currentTimeMillis() - start)/1000.0;
System.out.println("collections sort took " + elapsed2 + " seconds");
System.out.println();
System.out.println("Ratio = " + elapsed1 / elapsed2);
Iterator<String> i1 = list1.iterator();
Iterator<String> i2 = list2.iterator();
while (i1.hasNext() && i2.hasNext())
if (!i1.next().equals(i2.next()))
throw new RuntimeException("lists don't match");
}
// post: list is in sorted (nondecreasing) order
public static <T extends Comparable<T>> void sort(List<T> list) {
Object[] data = list.toArray();
sort(data);
ListIterator<T> i = list.listIterator();
for (int j = 0; j < data.length; j++) {
i.next();
i.set((T) data[j]);
}
}
// pre : 0 <= index1, index2 < list.length
// post: Values of list[x] and list[y] are exchanged.
private static void swap(Object[] list, int index1, int index2) {
Object temp = list[index1];
list[index1] = list[index2];
list[index2] = temp;
}
// post: uses the middle value of the list as a "pivot" to
// partition the list into two sublists: all those values less
// than or equal to the pivot appearing first followed by the
// pivot followed by all those values greater than the pivot;
// places the pivot value between the two sublists and returns
// the index of the pivot value
private static int partition(Object[] list, int low, int high) {
// swap middle value into first position
swap(list, low, (low + high) / 2);
// remember pivot
Comparable pivot = (Comparable) list[low];
// loop invariant: list divided into 3 parts: values <= pivot followed
// by unknown values followed by values > pivot
int index1 = low + 1; // index of first unknown value
int index2 = high; // index of last unknown value
while (index1 <= index2) // while some values still unknown
if (pivot.compareTo(list[index1]) >= 0)
index1++;
else if (pivot.compareTo(list[index2]) < 0)
index2--;
else {
swap(list, index1, index2);
index1++;
index2--;
}
// put the pivot value between the two sublists and return its index
swap(list, low, index2);
return index2;
}
// post: uses recursive quicksort to sort elements low through
// high; base case is a list of 0 or 1 elements, which requires
// no sorting; in recursive case, the list is partitioned using
// a pivot value and the two resulting lists are recursively sorted
public static void sort(Object[] list, int low, int high) {
if (low < high) {
int pivotIndex = partition(list, low, high);
sort(list, low, pivotIndex - 1);
sort(list, pivotIndex + 1, high);
}
}
// post: uses recursive quicksort to sort all elements of the array
public static void sort(Object[] list) {
sort(list, 0, list.length - 1);
}
}
]]>