2.6 Selection Sort

Consider again the problem of sorting a pile of phone bills for the past year. Another intuitive approach might be to look through the pile until you find the bill for January, and pull that out. Then look through the remaining pile until you find the bill for February, and add that behind January. Proceed through the ever-shrinking pile of bills to select the next one in order until you are done. This is the inspiration for our last Θ(n2)\Theta(n^2) sort, called Selection Sort.

The ii’th pass of Selection Sort “selects” the ii’th largest key in the array, placing that record at the end of the array. In other words, Selection Sort first finds the largest key in an unsorted list, then the next largest, and so on. Its unique feature is that there are few record swaps. To find the next-largest key value requires searching through the entire unsorted portion of the array, but only one swap is required to put the record into place. Thus, the total number of swaps required will be n−1n-1 (we get the last record in place “for free”).

Here is an implementation for Selection Sort.

function selectionSort(A):
    N = A.size()
    for i = 0 to N-1:               // Select i'th biggest element
        bigindex = N - i            // Current biggest index
        for j in 0 to N-i-1:        // Find the max value
            if A[j] > A[bigindex]:  // Found something bigger  
                bigindex = j        // Remember bigger index
        swap(A, bigindex, N-i)      // Put it into place

Consider the example of the following array.

Now we continue with the second pass. However, since the largest record is already at the right end, we will not need to look at it again.

Selection Sort continues in this way until the entire array is sorted.

The following visualization puts it all together.

Now try for yourself to see if you understand how Selection Sort works.

2.6.1 Selection Sort Analysis

Any algorithm can be written in slightly different ways. For example, we could have written Selection Sort to find the smallest record, the next smallest, and so on. We wrote this version of Selection Sort to mimic the behavior of our Bubble Sort implementation as closely as possible. This shows that Selection Sort is essentially a Bubble Sort except that rather than repeatedly swapping adjacent values to get the next-largest record into place, we instead remember the position of the record to be selected and do one swap at the end.

This visualization analyzes the number of comparisons and swaps required by Selection Sort.

There is another approach to keeping the cost of swapping records low, and it can be used by any sorting algorithm even when the records are large. This is to have each element of the array store a pointer to a record rather than store the record itself. In this implementation, a swap operation need only exchange the pointer values. The large records do not need to move. This technique is illustrated by the following visualization. Additional space is needed to store the pointers, but the return is a faster swap operation.

2.6.2 Review questions: Selection sort

Here are some review questions to check how well you understand Selection Sort.

Answer TRUE or FALSE.

Selection sort is simple, but less efficient than the best sorting algorithms.

  • What is Selection Sort’s average case complexity?
  • It is Θ(n2)\Theta(n^2).
  • Are there any better sorting algorithms?

Answer TRUE or FALSE.

Selection Sort (as the code is written in this module) is a stable sorting algorithm. Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

  • Think of the behaviour of every pass through the inner for loop of Selection Sort if two records are equal, with the greatest value in the array.
  • Which record will be selected?
  • The first such record.
  • Where will it be moved to?
  • The last position in the array.

Suppose that Selection Sort is given an input of 100 records, and it has completed 37 iterations of the main loop.

How many records are now guaranteed to be in their final position (never to be moved again by the sort)?

  • On each pass, Selection Sort puts a record into its final position.
  • So, if Selection Sort has done 37 passes, then at least 37 records are in their final positions.

How many times does Selection Sort call the swap function on an array of nn records?

  • Selection Sort first finds the largest key in an unsorted list, then the second largest, and so on.
  • To find the next largest key value requires searching through the entire unsorted portion of the array, but the search itself needs no swaps.
  • Once the next largest key is found, one swap is required to put the record in place.
  • We don’t need to check anything on the very last pass, since at that point the first record must already be in place.

In which cases are the time complexities the same for Selection Sort?

  • Does Selection Sort’s cost vary according to the order of the array input values?
  • No, it does not matter what order the input values have.

The order of the input records has what impact on the number of comparisons required by Selection Sort (as presented in this module)?

  • Does Selection Sort change when it make a comparison according to the order of the array input values?
  • No, it does not matter what order the input values have.

What is the worst-case time for Selection Sort to sort an array of n records?

  • Does Selection Sort’s order and number of comparisons depend on the particular order of the input array?
  • No, it does not.
  • Recall that our implementation for Selection Sort will try to swap even if the current record is in its correct location.

What is the running time of Selection Sort when the input is an array that has already been sorted?

  • Each test in the inner for loop will be the same no matter what the order of the input array.

What is the running time of Selection Sort when the input is an array that has all equal values?

  • Each test in the inner for loop will be the same no matter what the order of the input array.

Which statement best characterizes Selection Sort (as the code is written in this module)? Recall that a stable sorting algorithm maintains the relative order of records with equal keys.

  • Think of the behaviour of every pass through the inner for loop of Selection Sort if two records are equal, with the greatest value in the array.
  • Which record will be selected?
  • The first such record.
  • It will be moved to the last position in the array, putting it out of order with other equal-valued records.
  • But we could easily change the maximum-finding part of the loop to take the last of these equal-valued records.

In the worst case, the total number of swaps done by Selection Sort is closest to:

  • Does Selection Sort’s number of swaps depend on the particular order of the input array?
  • No, it does not.
  • Recall that our implementation for Selection Sort will try to swap even if the current record is in its correct location.

When is Selection Sort a good choice to use for sorting an array?

  • The big advantage of Selection Sort is that it keeps the number of swaps small.
  • So it will make best use of this advantage when the cost to swap is large.

In the worst case, the total number of comparisons for Selection Sort is closest to:

  • Selection Sort’s implementation is made up of two nested for loops.
  • The outer for loop is executed n−1n-1 times.
  • The inner for loop is executed n−in-i times.
  • The total cost is the sum of ii’s for ii goes from 1 to nn.