A Sorting System and Some Quadratic Sorting Routines

As the corresponding reading implies, in developing a sorting library, you may want to create a variety of files: interfaces, tests, utilities, multiple implementations, and so and so forth. Let's explore the elements of this library.

a. Read through Sorter.java and determine why there seem to be two sorting routines.

b. Read through SorterBridge.java and determine what purpose that code seems to serve.

c. Read through Utils.java and determine what purpose permute, randomSortedInts, sorted, and swap seem to have. You should also read the bodies of the methods to better understand how they are implemented.

We will be implementing our own sorting algorithms. In part, implementing sorting algorithms as an important exercise in developing skills in algorithm design and analysis. In part, implementing key sorting algorithms is an exercise in literacy - computer scientists are expected to know “the literature” of algorithms. In part, knowing about various algorithms helps you choose the best sorting algorithm for a particular set of data.

However, in practice, most programmers use the sorting routines that come with the language. Java provides a sort algorithm as part of java.util.Arrays.

A common problem in object-oriented design is taking an existing method or object and “wrapping” it so that it can be used to meet a specified interface. The name of this design pattern is an “Adapter”.

a. Sketch a class that implements the Sorter interface or extends the SorterBridge class and that implements sorting by a call to java.util.Arrays.sort.

b. Compare your answer to BuiltinSorter.java.

c. Summarize for yourself what you've learned in this exercise.

One of the first ways we explore the implementation of an algorithm is to design a series of “experiments” in which we can watch the algorithm in action. The file ExptUtils.java contains some generic utilities for conducting experiments with sorting algorithms.

a. Read through the code for ExptUtils.java and identify the available methods and their purposes.

b. Sketch a simple main class that runs the two sets of experiments using BuiltinSorter.java.

c. Compare your answer to BuiltinSortExpt.java.

d. Predict a bit of the output you'll see if you run the experiment.

e. Run the experiment.

f. Summarize for yourself what you've learned in this exercise.

Of course, experiments take a lot of human cognitive power to process. Hence, we traditionally write unit tests for our algorithms. When we write a generic algorithm, as we've done in this case, it's equally helpful to write generic tests.

a. Read through TestUtils.java to identify some of the utilities available to help you test sorting algorithms.

b. Sketch a test for BuiltinSorter.java. You may assume that you only want to run the two basic tests (test1 and test2).

c. Compare your answer to BuiltinSorterTest.java.

d. Run the test.

e. Summarize for yourself what you've learned in this exercise. (You probably didn't learn anything from running the test, but you might have learned something from the earlier steps.)

You are now ready to implement your own sorting algorithm. As you may recall, selection sort works by partitioning an array into sorted and unsorted values and repeatedly swapping the smallest unsorted value into the front of that section.

a. Sketch the invariant for the main loop of selection sort.

b. Compare your answer to the comments in SelectionSorter.java.

c. You'll note that we've put a set of experiments in SelectionSortExpt.java. Do you expect experiments to give correct results? Why or why not?

d. Check your answer experimentally.

e. As you likely noted, the experiments fail. Why? Because indexOfSmallest is not implemented. Implement it.

f. Write a simple set of unit tests for SelectionSorter.sort.