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

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

• O(n2) 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.

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.Integer`s 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).

History

Wednesday, 28 April 2004 [Samuel A. Rebelsky]

• Created.

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 `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Homework/hw.08.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu