An Introduction to Sorting - Data Structures and Abstractions with Java - page 214

18.

Consider a class Student that has private data fields for name, class rank, identification number, and grade point aver-
age. Imagine an array of Student objects that you want to sort according to any one of the previously given fields.

a. What difficulty will you encounter in implementing such a sort?
b. One solution to this problem defines a new class for each criterion for sorting. Each of these classes encap-
sulates a Student object. In this way, you can use the sorting methods given in this chapter. Provide the
details necessary for another programmer to implement this solution.
c. Another solution to this problem changes the signature and definition of the sorting method. One parame-
ter of the method is an object that can compare two Student objects according to a certain criterion. This
parameter belongs to one of several new classes that correspond to the sorting criteria. Provide the details
necessary for another programmer to implement this solution.

P ROJECTS

1.

Graphical demonstrations of various sorting algorithms are instructive, as they provide insight into how an algo-
rithm behaves. Consider a collection of vertical lines of varying lengths, such as the ones in Figure 8-18a. Create
a sorting demonstration that sorts the lines by length, as shown in Figure 8-18b. You should draw the configura-
tion of lines after every swap or move that a given sorting algorithm makes. If you delay execution very briefly
after each redraw, the result will be an animation of the sort.
You could begin by drawing 256 lines, each one pixel wide but of different lengths—and perhaps different
colors—arranged from shortest to longest so that they appear as a triangle. The user then should exercise an
option to scramble the lines. At a user signal, your sorting algorithm should sort the lines.
You can provide individual demonstrations, perhaps as applets, for each sort algorithm. Or you can include
all the algorithms in one program that asks the user to choose an algorithm. Each sort should start with the same
scrambled lines so the user can compare methods. You might also choose a sort algorithm at random and see
whether the user can guess which one it is.

FIGURE 8-18

An animated sorting demonstration that sorts vertical lines (a) before its
execution; (b) after its execution

(a) (b)

2.

Revise the implementations of the insertion sort and the Shell sort so that they count the number of comparisons made
during a sort. Use your implementations to compare the two sorts on arrays of random Integer objects of various sizes.
Also, compare the Shell sort as implemented in Segment 8.24 with a revised Shell sort that adds 1 to space any time it
is even. For what array size does the difference in the number of comparisons become significant? Is the size consistent
with the size predicted by the algorithm's Big Oh?

3.

Complete the implementations of the sorting algorithms given in this chapter. Use your implementations to com-
pare the run times of the sorts on various arrays of 50,000 random Integer objects. See the projects at the end of
Chapter 4 for a description of how to time a block of Java code. Write a summary of which algorithm you find to
be more efficient and why.