Computer Science Fundamentals (CS153 2004S)

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.



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

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


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:

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).



Wednesday, 28 April 2004 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 7 09:44:09 2004.
The source to the document was last modified on Wed Apr 28 23:27:04 2004.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,