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

people by height, age, or name; music by title, artist, or album; and so on. Arranging things into
either ascending or descending order is called sorting . You can sort any collection of items that can
be compared with one another. Exactly how you compare two objects depends on the nature of the
objects. For example, you can arrange a row of topics on your bookshelf in several ways: by title,
by author, by height, by color, and so on. The designer of a class of book objects would choose one
of these ways when implementing the method compareTo .
Suppose you have a collection of items that need to be sorted in some way. For example, you
might want to arrange a group of numbers from lowest to highest or from highest to lowest, or you
might want to place some strings in alphabetical order. This chapter discusses and implements a
few simple algorithms that sort items into ascending order. That is, our algorithms rearrange the
first n entries in a collection so that

entry 1 entry 2 . . . entry n

With only small changes to our algorithms, you will be able to sort entries into descending order.
Sorting an array is usually easier than sorting a chain of linked nodes. For this reason, typical
sorting algorithms sort an array. In particular, our algorithms will rearrange the first n values in an
array a so that
a[0] a[1] a[2] . . . a[n - 1]
However, we also will use one of our algorithms to sort a chain of linked nodes.
Sorting is such a common and important task that many sorting algorithms exist. This chapter
examines some basic algorithms for sorting data. Although most of our examples will sort integers,
the Java implementations given will sort any Comparable objects—that is, objects of any class that
implements the interface Comparable and, therefore, defines the method compareTo .
The efficiency of a sorting algorithm is significant, particularly when large amounts of data
are involved. We will examine the performance of the algorithms in this chapter and find that they
are relatively slow. The next chapter will present sorting algorithms that usually are much faster.

Organizing Java Methods That Sort an Array

8.1

One way to organize methods that sort an array is to create a class of static methods that perform
the various sorts. The methods define a generic type T for the objects in the array. For example, we
could write the header of such a method as follows:
public static <T> void sort(T[] a, int n)
Recall that the array passed to this method can contain objects of any one class.
For an array to be sortable, the objects in that array must be Comparable . Thus, the class that T
represents must implement the interface Comparable . To ensure this requirement, we write
<T extends Comparable<T>>
instead of simply <T> before the return type in the headers of the sort methods. We then can use T as
the data type of the parameters and local variables within the methods. For example, our class could
begin as follows:

public class SortArray
{

public static <T extends Comparable<T>> void sort(T[] a, int n)
{. . .
A client could sort an array of 50 objects, for example, by using the statement
SortArray.sort(myArray, 50);