The selection sort algorithm is slightly better performing than bubble sort, and so we're going to explain how it works and implement it in Java.
The selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2). 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.
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.
// selectSort.java
// demonstrates selection sort
////////////////////////////////////////////////////////////////
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 99Invariant
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(N2) 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.
