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

Note: Bounded wildcards
When using generic types, the wild card ? represents any class. You can bound , or limit, the
wildcard in one of two ways. For example, ? super Gizmo means any superclass of Gizmo . We
say that Gizmo is the lower bound of the wildcard. Analogously, ? extends Gizmo means any
subclass of Gizmo . Here, Gizmo is the upper bound of the wildcard. In Chapter 4,
Segments 4.13 and 4.17, respectively, provide other meanings for the terms upper bound and
lower bound.

We now turn our attention to several ways of sorting an array.

Selection Sort

8.3

Imagine that you want to rearrange the topics on your bookshelf by height, with the shortest book
on the left. You might begin by tossing all of the topics onto the floor. You then could return them
to the shelf one by one, in their proper order. If you first return the shortest book to the shelf, and
then the next shortest, and so on, you would perform a kind of selection sort . But using the floor—
or another shelf—to store your topics temporarily uses extra space needlessly.

Instead, approach your intact bookshelf and select the shortest book. Since you want it to be
first on the shelf, you remove the first book on the shelf and put the shortest book in its place. You
still have a book in your hand, so you put it into the space formerly occupied by the shortest book.
That is, the shortest book has traded places with the first book, as Figure 8-2 illustrates. You now
ignore the shortest book and repeat the process for the rest of the bookshelf.

VideoNote

Selection sort

FIGURE 8-2

Before and after exchanging the shortest book and the first book

Before

Swap

After

In terms of an array a , the selection sort finds the smallest entry in the array and exchanges it
with a[0] . Then, ignoring a[0] , the sort finds the next smallest entry and swaps it with a[1] , and so
on. Notice that we use only one array. We sort it by making entries trade places with other entries.
We could have copied the array into a second array and then moved the entries back to the original
array in their proper order. But that would be like using the floor to store topics temporarily. Fortunately,
all of that extra space is unnecessary.

8.4

Figure 8-3 shows how a selection sort rearranges an array of integers by interchanging values.
Beginning with the original array, the sort locates the smallest value in the array, that is, the 2 in
a[3] . The value in a[3] is interchanged with the value in a[0] . After that interchange, the smallest
value is in a[0] where it belongs.