Guido Krüger's Web Service

QuickSort

Introduction

The standard JDK up to version 1.1 does not have any sorting capabilites for collections. The SortableVector class in the gk.util package is an extension of java.util.Vector which provides basic sorting capabilities. By calling eithter the sort or qsort method, the application can choose among a simple selection sort algorithm or the much faster quicksort. While selection sort is usually O(n²), the quicksort performs at O(n log₂ n). In a number of simulations it has been able to sort 100.000 double values in a single second (using JDK1.2Beta4 with JIT enabled). The runtime has always approximated O(n log₂ n), no degenerated cases appeared during the testing. The pivot is selected by using a random number generator.

Example

The SortableVector uses a simple helper class ElementComparator. It provides a single method preceeds which compares two elements and should return true if the first one preceeds the second one according to the required sorting order of the Vector. The ElementComparator can easily be passed as an anonymous inner class when calling the sort or qsort methods. The following code shows how to sort a Vector of Double elements:

v2.qsort(new ElementComparator() {
  public boolean preceeds(Object element1, Object element2)
    {
      double x = ((Double)element1).doubleValue();
      double y = ((Double)element2).doubleValue();
      return x < y;
    }
});