Selection Sort in Java

We'll begin our investigation of algorithms with a classic example, Selection Sort.  Selection sort is the process of starting with the first item in an array; iterating through the array to find the smallest item then exchanging it with the first item.  The algorithm then proceeds to the second item in the array and repeats until the array is sorted.

For our example we're going to work with a simple set of integers organized in an array and ranging in value from 0-9.

We'll setup our array like this:

 Integer[] ints = new Integer[10];
 ints[0] = 5;
 ints[1] = 2;
 ints[2] = 7;
 ints[3] = 0;
 ints[4] = 3;
 ints[5] = 8;
 ints[6] = 4;
 ints[7] = 6;
 ints[8] = 1;
 ints[9] = 9;

Lets think of our array like this:

    index: 0  1  2  3  4  5  6  7  8  9
    value: 5, 2, 7, 0, 3, 8, 4, 6, 1, 9

Our first goal is to find index 0 the smallest value in the array, which happens to be 0.  A quick glance at the array shows us that the value 0 is located at index 3.  The approach selection sort takes is to start at index 0 and look at every index in the array comparing its value to find the smallest value in the array.  This means, if we start at index 0, our current smallest value is 5.
 
    current index: 0
    min value:      5

    index: 0  1  2  3  4  5  6  7  8  9
    value: 5, 2, 7, 0, 3, 8, 4, 6, 1, 9

Then our algorithm moves on to index 1 and compares the value of index 1 to the min value we established at index 0.  If the value at index 1 is less than the value at index 0 we set the min value to the value at index 1.

    Is 2 less than 5? Yes...therefore min = 2

But remember we are not changing our array yet.  Our algorithm is just holding a reference to the index it currently knows to have the smallest value.  So let's change our answer to:

    Is 2 less than 5? Yes...therefore our min value of 2 is located at index 1.

Next our algorithm moves on to index 2.

    Is 7 less than 2? No...therefore our min value is still 2 and is located at index 1.

Next our algorithm moves on to index 3.

    Is 0 less than 2? Yes...therefore our min value of 0 is located at index 3.

We've found the smallest value in the array.  However, our algorithm does not know this and will continue to iterate through all the way to index 9 and do comparisons.  Once the algorithm reaches the end of the array it will need to place the smallest value at index 0.  This is why we hold on to the reference to the smallest value.  We have selected the smallest value in the array to be 0 located at index 3.  Therefore we need to swap the values at index 0 and index 3:

    swap(ints[0], ints[3])  which swaps the values 5 and 0 changes our array to:
    index: 0  1  2  3  4  5  6  7  8  9
    value: 0, 2, 7, 5, 3, 8, 4, 6, 1, 9

The next step is to repeat this process to find the smallest value to be placed at index 1.

And here is what the algorithm looks like:


 The source code and an accompanying jUnit Test Driver can be found at:

Selection Sort Source