Homework 8: Sorting, Revisited

Assigned: Thursday, 29 April 2004
Due: Wednesday, 5 May 2004

Summary: In this assignment, you will comparatively evaluate a number of sorting algorithms.

Turning it in: Email me your files.

Collaboration: You must work with at least one other person. (This means you, Andy!) You may work in group of up to size four, and may discuss your design with any size group. You may also work with each other on general debugging issues.

Contents:

• Background
• Useful Classes
• Steps

Background

This semester, we have studied a wide range of sorting algorithms, including

• O(n²) sorts: Insertion sort, Selection sort, Bubble sort
• O(nlogn) sorts: Merge sort, Heap Sort, Quick sort (expected)

We have also mentioned radix sort, a potentially more efficient sorting algorithm.

When we were working in Scheme, we conducted a quick and dirty comparison of a few of these sorts. It is now time to try again in Java.

Useful Classes

• java.lang.System, which provides currentTimeMillis.
• java.lang.Integer, the things you'll be sorting.
• java.util.Comparator, which provides a mechanism for comparing objects (like the Order interface you designed for exam 3).
• java.util.Random, a random sequence generator.
• java.util.Vector, extensible arrays.
• Sorter.java, an interface for your sorting classes.

Steps

1. Research radix sort (since you will be expected to implement it). You may also find it useful to scan the documentation for the classes above.

2. Write the following classes (each of which will implement the Sorter interface:

• InsertionSort
• SelectionSort
• BubbleSort
• MergeSort
• QuickSort
• HeapSort

3. Write a RadixSort class (which only needs to sort arrays of Integers).

4. Write IncreasingInteger and DecreasingInteger classes that implement Comparator For the first, compare(a,b) will return a negative number if a represents an integer less than b; for the second, compare(a,b) will return a negative number if b represents an integer less than a.

5. Write a TestSorts director class (one that contains a main method) that, given a test size as a command line parameter, reports on the amount of time each sorting method takes. This class should create a vector of random java.lang.Integers and then call each sorting method in sequence. Preferably, you will also verify that the sorting mechanism worked correctly (although you need not check that the original vector is not modified).