## Selection Sort

The selection sort improves on the bubble sort by reducing the number of
swaps necessary from O(N^{2}) to O(N). Unfortunately, the number of
comparisons remains O(N^{2}). However, the selection sort can still
offer a significant improvement for large records that must be physically moved
around in memory, causing the swap time to be much more important than the
comparison time. (Typically, this isn't the case in Java, where references
are moved around, not entire objects.)

### Selection Sort on the Baseball Players

Let's consider the baseball players again. In the selection sort, you can no longer compare only players standing next to each other. Thus, you'll need to remember a certain player's height; you can use a notebook to write it down. A magenta-colored towel will also come in handy.

#### A Brief Description

What's involved in the selection sort is making a pass through all the players and picking (or selecting, hence the name of the sort) the shortest one. This shortest player is then swapped with the player on the left end of the line, at position 0. Now the leftmost player is sorted and won't need to be moved again. Notice that in this algorithm the sorted players accumulate on the left (lower indices), whereas in the bubble sort they accumulated on the right.

The next time you pass down the row of players, you start at position 1, and, finding the minimum, swap with position 1. This process continues until all the players are sorted.

#### A More Detailed Description

In more detail, start at the left end of the line of players. Record the leftmost player's height in your notebook and throw the magenta towel on the ground in front of this person. Then compare the height of the next player to the right with the height in your notebook. If this player is shorter, cross out the height of the first player and record the second player's height instead. Also move the towel, placing it in front of this new "shortest" (for the time being) player. Continue down the row, comparing each player with the minimum. Change the minimum value in your notebook and move the towel whenever you find a shorter player. When you're done, the magenta towel will be in front of the shortest player.

Swap this shortest player with the player on the left end of the line. You've now sorted one player. You've made N-1 comparisons, but only one swap.

On the next pass, you do exactly the same thing, except that you can completely ignore the player on the left because this player has already been sorted. Thus, the algorithm starts the second pass at position 1, instead of 0. With each succeeding pass, one more player is sorted and placed on the left, and one less player needs to be considered when finding the new minimum. Figure 3.9 shows how this sort looks for the first three passes.

### The SelectSort Workshop Applet

To see how the selection sort looks in action, try out the SelectSort
Workshop applet. The buttons operate the same way as those in the BubbleSort
applet. Use New to create a new array of 10 randomly arranged bars. The red
arrow called `outer` starts on the left; it points to the leftmost
unsorted bar. Gradually, it will move right as more bars are added to the sorted
group on its left.

The magenta `min` arrow also starts out pointing to the leftmost bar;
it will move to record the shortest bar found so far. (The magenta `min`
arrow corresponds to the towel in the baseball analogy.) The blue `inner`
arrow marks the bar currently being compared with the minimum.

As you repeatedly press Step, `inner` moves from left to right,
examining each bar in turn and comparing it with the bar pointed to by
`min`. If the `inner` bar is shorter, `min` jumps over to
this new, shorter bar. When `inner` reaches the right end of the graph,
`min` points to the shortest of the unsorted bars. This bar is then
swapped with `outer`, the leftmost unsorted bar.

Figure 3.10 shows the situation midway
through a sort. The bars to the left of `outer` are sorted, and `inner`
has scanned from `outer` to the right end, looking for the shortest bar.
The `min` arrow has recorded the position of this bar, which will be
swapped with `outer`.

Use the Size button to switch to 100 bars, and sort a random arrangement.
You'll see how the magenta `min` arrow hangs out with a perspective
minimum value for a while and then jumps to a new one when the blue
`inner` arrow finds a smaller candidate. The red `outer` arrow
moves slowly but inexorably to the right, as the sorted bars accumulate to its
left.

**FIGURE 3.9 Selection sort on baseball players.**

**FIGURE 3.10**** The SelectSort
Workshop applet.**

### Java Code for Selection Sort

The listing for the `selectSort.java` program is similar to that for
`bubbleSort.java`, except that the container class is called
`ArraySel` instead of `ArrayBub`, and the `bubbleSort()`
method has been replaced by `selectSort()`. Here's how this method
looks:

public void selectionSort() { int out, in, min; for(out=0; out<nElems-1; out++) // outer loop { min = out; // minimum for(in=out+1; in<nElems; in++) // inner loop if(a[in] < a[min] ) // if min greater, min = in; // we have a new min swap(out, min); // swap them } // end for(out) } // end selectionSort()

The outer loop, with loop variable `out`, starts at the beginning of
the array (index 0) and proceeds toward higher indices. The inner loop, with
loop variable `in`, begins at `out` and likewise proceeds to the
right.

At each new position of `in`, the elements `a[in]` and
`a[min]` are compared. If `a[in]` is smaller, then `min` is
given the value of `in`. At the end of the inner loop, `min`
points to the minimum value, and the array elements pointed to by `out`
and `min` are swapped. Listing 3.2 shows the complete
`selectSort.java` program.

#### LISTING 3.2 The `selectSort.java` Program

// selectSort.java // demonstrates selection sort // to run this program: C>java SelectSortApp //////////////////////////////////////////////////////////////// class ArraySel { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArraySel(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void selectionSort() { int out, in, min; for(out=0; out<nElems-1; out++) // outer loop { min = out; // minimum for(in=out+1; in<nElems; in++) // inner loop if(a[in] < a[min] ) // if min greater, min = in; // we have a new min swap(out, min); // swap them } // end for(out) } // end selectionSort() //-------------------------------------------------------------- private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } //-------------------------------------------------------------- } // end class ArraySel //////////////////////////////////////////////////////////////// class SelectSortApp { public static void main(String[] args) { int maxSize = 100; // array size ArraySel arr; // reference to array arr = new ArraySel(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items arr.selectionSort(); // selection-sort them arr.display(); // display them again } // end main() } // end class SelectSortApp ////////////////////////////////////////////////////////////////

The output from `selectSort.java` is identical to that from
`bubbleSort.java`:

77 99 44 55 22 88 11 0 66 33 0 11 22 33 44 55 66 77 88 99

### Invariant

In the `selectSort.java` program, the data items with indices less
than or equal to `out` are always sorted.

### Efficiency of the Selection Sort

The selection sort performs the same number of comparisons as the bubble
sort: N*(N-1)/2. For 10 data items, this is 45 comparisons. However, 10 items
require fewer than 10 swaps. With 100 items, 4,950 comparisons are required, but
fewer than 100 swaps. For large values of N, the comparison times will dominate,
so we would have to say that the selection sort runs in O(N^{2}) time,
just as the bubble sort did. However, it is unquestionably faster because there
are so few swaps. For smaller values of N, the selection sort may in fact be
considerably faster, especially if the swap times are much larger than the
comparison times.