tpop(2.4): A Java Quicksort

2.4 A Java Quicksort

2011-03-11 Fri

• One big difference from C or C++ is that in Java it is not possible to pass a comparison function to another function; there are no function pointers.
• Instead we create an interface whose sole cotent is a function that compares two Objects. For each data type to be sorted, we then create a class with a member function that implements the interface for that data type. We pass an instance of that class to the sort function, which in turn uses the comparison function within the class to compare elements.

We begin by defining an interface named Cmp that declares a single member, a comparison function cmp that compares two Objects:

interface Cmp {
    int cmp(Ojbect x, Object y);
}

Then we can write comparison functions that implement this interface; for example, this class defines a function that compares Integers:

/* Icmp: Integer comparison */
class Icmp implements Cmp {
    public int cmp(Object o1, Object o2)
    {
        int i1 = ((Integer) o1).intValue();
        int i2 = ((Integer) o2).intValue();
        if (i1 < i2)
            return -1;
        else if (i1 == i2)
            return 0;
        else
            return 1;
    }
}

and this compares Strings:

/* Scmp: String comparison */
class Scmp implements Cmp {
    public int cmp(Object o1, Object o2)
    {
        String s1 = (String) o1;
        String s2 = (String) o2;
        return s1.compareTo(s2);
    }
}

We can sort only types that are derived from Object with this mechanism; it cannot be applied to the basic types like int or double.

With these components, we can now translate the C quicksort function into Java and have it call the comparison function from a Cmp object passed in as an argument. The most significant change is the use of indices left and right, since Java does not have pointers into arrays.

/* Quicksort.sort: quicksort v[left]..v[right] */
static void sort(Object[] v, int left, int right, Cmp cmp){
    int i, last;
    if (left >= right) //nothing to do
        return;
    swap(v, left, rand(left, right));//move pivot elem
    last = left;
    for (i = left+1; i <= right; i++) //artition
        if (cmp.cmp(v[i], v[left]) < 0)
            swap (v, ++last, i);
    swap(v, left, last); //restore pivot elem
    sort (v, left, last-1, cmp);  //recursively sort
    sort (v, last+1, right, cmp);  //each part
}

Quicksort.sort used cmp to comare a pair of objects, and calls swap as before to interchange them.

/* Quicksort.swap: swap v[i] and v[j] */
static void swap(Object[] v, int i, int j)
{
    Object temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

Random number generation is done by a function that produces a random integer in the range left to right inclusive:

static Random rgen = new Random();

/* Quicksort.rand: return random integer in [left, right] */
static int rand(int left, int right)
{
    return left + Math.abs(rgen.nextInt())%(right-left+1);
}

We compute the absolute value, using Math.abs, because java's random number generator returns negative integers as well as positive.

The functions sort, swap, and rand, and the generator object rgen are the members of a class Quicksort.

Finally, to call Quicksort.sort to sort a String array, we would say

public static void main(String[] argv)
{

    String[] sarr = new String[] {"mark", "tau", "atau", "haitao"};
    Quicksort.sort(sarr, 0, sarr.length-1, new Scmp());
        System.out.println("The sorted array is " );
        for (String s : sarr)
        System.out.println(s);
    System.out.println("\n");
}