Sorting Suite User's Guide

Download

Welcome to the RP Sorting Suite user's guide. The RP Sorting Suite is implemented entirely in Java. For a details about performance of the algorithms, click below. Sorting Suite -- Timing Data and Analysis

INSTALLATION

The Sorting Suite download is via a zip file named rpSortingSuite.zip. This zip file contains a jar file named rpsort.jar that contains both the source and the class files for the sorting suite. Also contained within the zip file is the javadoc documentation for the classes in the suite.

CODE LAYOUT OF THE SORTING SUITE:
The sorting suite consists of the following packages:

  • com.rp.util.sort -- This directory contains the implementations of the 13 sorting algorithms, as well as the exception thrown by each of the classes and the interface they all implement.

  • com.rp.util.sort.compare -- This directory contains some common java.util.Comparator implementations that can be used when sorting objects. These will be discussed in more detail below.

  • com.rp.util -- This package contains some general utility classes. These include a utility class for Exceptions and a utility class that contains methods for using Java Reflection.

  • com.rp.util.sort.test -- This package contains the random array generator used for generating arrays of random values that are used for testing and timing purposes.

  • test.sort -- This package contains the code for running test and timing tests on the sorting algorithms.

  • timer -- This package contains the timing code.

USING THE RP SORTING SUITE
Each of the sorting algorithm implementations contained in the suite implement the com.rp.util.sort.ISort interface. This interface requires the implementations to define methods for sorting arrays Objects, Strings, ints, longs, shorts, doubles, floats, chars, and bytes, as well as java.util.Lists, an example of which is an ArrayList. First, let's take a look at sorting Java primitive data types:

Sorting Primitives
Below is a simple example code snippet demonstrating how to sort:
import com.rp.util.sort.*;
.
.
.
int[] arr = {4, 3, 5, 1, 2};
ISort sorter = new QuickSort();
sorter.sort (arr);

The above simply creates an array of ints, and uses the QuickSort class to sort it.
The sorting suite also offers methods for sorting sections of an array. For example, the ISort interface has the following method signature within it that all algorithm implemenations implement:
public void sort (int[] arr, int begin, int end). //NOTE: int[] is just an example in this case. Each data type is implemented. Thus, using the example above, we can do the following:
int[] arr = {4, 3, 5, 1, 2};
ISort sorter = new QuickSort();
sorter.sort (arr, 1, 4);

The above sorts the 3, 5, 1, and 2 values of the array, and leaves the 4 in the 0th position of the array. NOTE:(The begin and end values passed to the sort method corresponds to index values of the array. Thus, if we wanted to sort the entire array, we would use: sorter.sort (arr, 0, arr.length-1).
For simple data types, which include ints, longs, shorts, doubles, floats, chars, bytes, and for the most part, Strings, following the examples above are all there is to using the suite.
Objects and Lists are a little more complicated. This is because Objects and lists require the use of a java.util.Comparator. (NOTE: Strings can also be sorted as Objects, and as such, a comparator can be passed to sort an array of List of Strings. However, the suite provides methods to sort arrays of Strings based on the "equalsToIgnoreCase" method of the java.lang.String object.)

Sorting Objects and Lists
In each of the methods provided by the suite for sorting objects, a java.util.Comparator is required. A Comparator is simply an interface that describes the ordering of an object. For example, below is a Comparator that describes the ordering on an Integer:
public class IntegerComparator implements java.util.Comparator
{
    public int compare(Object o1,Object o2) throws ClassCastException
    {
        if(!(o1 instanceof Integer))
        {
            throw new ClassCastException();
        }
        if(!(o2 instanceof Integer))
        {
            throw new ClassCastException();
        }
        int d1 = ((Integer)o1).intValue();
        int d2 = ((Integer)o2).intValue();

        if (d1 < d2)
        {
            return -1;
        }
        else if (d1 > d2)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}
Suppose that we have an array of Integers. To sort these Integers with the suite, we can simply do the following:
//suppose we have an array of Integers called arr
Isort sort = new QuickInsertionSort();
sort.sort (arr, new com.rp.util.sort.compare.IntegerComparator());
There are several common Comparators implemented in the com.rp.util.sort.compare package. These include IntegerComparator, StringComparator (ignores case), LongComparator, ShortComparator, DoubleComparator, FloatComparator, CharacterComparator, and ByteComparator.
Sometimes we need to sort a custom object. For example, the following:
public class CustomObject
{
    private String name = null;
    private String date = null;
    private int size = 0;

    public void setName (String value)
    {
        this.name = value;
    }

    public String getName ()
    {
        return this.name;
    }

    public void setDate (String value)
    {
        this.date = value;
    }

    public String getDate ()
    {
        return this.date;
    }

    public void setSize (int value)
    {
        this.size = value;
    }

    public String getSize ()
    {
        return this.size;
    }

}

The suite gives a couple options in this case. If we want to sort this object by name, we can use the sort method of the suite that takes a method name and sorts based on a value returned from a method call to that method on the given Object. For example:
//CustomObject[] arr = an array of Custom Objects
ISort sort = new CombSort();
sort.sort (arr, new com.rp.util.sort.compare.StringComparator(), "getName");

NOTE: The methods that take method names as parameters use Reflection to get the returned values of the methods. This is much slower than using just a Comparator.
Sometimes we want to sort by more than just one value on a particular object. In the example of the CustomObject, we may want to sort by name, but sub-sort by date. In this case, we need to create a Comparator to accomplish this. The following is an example Comparator implementing the above:
public class CustomObjectComparator implements java.util.Comparator
{

    public int compare(Object o1,Object o2) throws ClassCastException
    {
        if(!(o1 instanceof CustomObject))
        {
            throw new ClassCastException();
        }
        if(!(o2 instanceof CustomObject))
        {
            throw new ClassCastException();
        }
        
        CustomObject c1 = (CustomObject)o1;
        CustomObject c2 = (CustomObject)o2;
        
        String nameOne = c1.getName();
        String dateOne = c1.getDate();
        
        String nameTwo = c2.getName();
        String dateTwo = c2.getDate();
        
        if (nameOne.compareToIgnoreCase(nameTwo) < 0)
        {
            return -1;    
        }
        else if (nameOne.compareToIgnoreCase(nameTwo) > 0)
        {
            return 1;    
        }
        else
        {
            if (dateOne.compareToIgnoreCase(dateTwo) > 0)
            {
                return 1;    
            }
            else if (dateOne.compareToIgnoreCase(dateTwo) < 0)
            {
                return -1;    
            }
            else
            {
                return 0;    
            }
        }
    }
}

Below is an example where we use the above Comparator:
        CustomObject[] arr = new CustomObject[4];
        
        CustomObject one = new CustomObject();
        one.setName("Abe");
        one.setDate ("01/01/2001");
        
        CustomObject two = new CustomObject();
        two.setName ("Ben");
        two.setDate ("01/02/2001");
        
        CustomObject three = new CustomObject ();
        three.setName ("Cal");
        three.setDate ("01/03/2001");
        
        CustomObject four = new CustomObject ();
        four.setName ("Ben");
        four.setDate ("01/01/2001");
        
        arr[0] = two;
        arr[1] = three;
        arr[2] = one;
        arr[3] = four;
        
        ISort sort = new HeapSort();
        CustomObjectComparator sc = new CustomObjectComparator();
        sort.sort (arr, sc);
Here is another example, this time using a java.util.List instead of an array:
        List arr = new ArrayList(4);
        
        CustomObject one = new CustomObject();
        one.setName("Abe");
        one.setDate ("01/01/2001");
        
        CustomObject two = new CustomObject();
        two.setName ("Ben");
        two.setDate ("01/02/2001");
        
        CustomObject three = new CustomObject ();
        three.setName ("Cal");
        three.setDate ("01/03/2001");
        
        CustomObject four = new CustomObject ();
        four.setName ("Ben");
        four.setDate ("01/01/2001");
        
        arr.add(two);
        arr.add(three);
        arr.add(one);
        arr.add(four);
        
        ISort sort = new HeapSort();
        CustomObjectComparator sc = new CustomObjectComparator();
        sort.sort (arr, sc);

This concludes the user's guide for the RP Sorting Suite. For downloading instructions, please click here.