10.4 Selection Sort

An insertion sort has a great deal of data movement. This can be costly in terms of the amount of time that it takes for the sort to complete. Another sorting method that reduces the amount of data movement is called a selection sort.

We perform the same number of passes through the data but once an item is placed it is never moved again. First we find the largest value in the data. We swap that largest with the item at the top of the list. On the next pass we find the next largest value and swap it with the second last item in the list. We keep doing this with shorter and shorter sublists until the items are in order.

Here is an applet to demonstrate this.

Example

This applet demonstrates how a selection sort works.

Unlike the insertion sort the only exchanges of position are the ones indicated by the blue and red circles. There are still a lot of comparisons to be done in each pass but there is much less data movement.

Now let's look at the code to implement this sort: 

public static void selectSort(double[] list)
{
   for (int top = list.length - 1; top > 0; top--)
   {
      int largeLoc = 0;
      for (int i = 1; i <= top; i++)
         if (list[i] > list[largeLoc])
            largeLoc = i;
      double temp = list[top];
      list[top] = list[largeLoc];
      list[largeLoc] = temp;
   }
}

Try tracing through the code using a set of numbers from the above applet. It would get called in a fragment like this:

double[] nums = new double[10];
// fill the array with your unsorted numbers
selectSort(nums);