The Selection Sort Algorithm

Selection Sort: Basic Idea

The idea of this sorting algorithm is to maintain a sorted list while selecting, at each step, from the remaining unsorted items, the "next optimal item" (i.e., the largest or smallest remaining element, depending on the implementation) and putting that element in its proper location.

Selection Sort: Name, Input and Output

Name: SortBySelection

Input:

• A sequence of values, all of a given type, which is called s
• Two positions in the sequence, to determine the range of values within the sequence that will be sorted, which are called firstPosition and lastPosition, and which satisfy firstPosition <= lastPosition

Output:

• The sequence of values s, sorted in ascending order between firstPosition and lastPosition, inclusive

Selection Sort: Pseudocode

Algorithm SortBySelection(s, firstPosition, lastPosition)
-------------------------------------------------------------------
while values not yet sorted
    Select next required value from remaining unsorted values
    Swap this value with the one currently in the position where it should go
endwhile

Note that after each iteration the number of remaining unsorted values has been reduced by one. Note too that "required" may mean "largest" or "smallest", depending on whether the sort is ascending or descending and how it is actually being implemented. But remember, as well, that the usual default sort of any kind is in ascending order.

Selection Sort: Performance

We say that the selection sort algorithm is, in general, a O(n²) algorithm, or that it has "quadratic time complexity". To see this, let us begin by "implementing" the pseudocode above, using something more closely resembling Java or C++ code, as follows (in which n is the number of data values being sorted):

for (startIndex = 0; startIndex < n-1; startIndex++)
{
    minIndex = startIndex;
    for (position = startIndex+1; position < n; position++)
        if (s[position] < s[minIndex]) minIndex = position;
    swap(s[minIndex], s[startIndex]);
}

The first thing to note here is that the pseudocode uses a single while-loop, while the "actual" code uses two nested for-loops. This should not cause any consternation. There is no reason why actual code has to parrot pseudocode, though if it does, or can, that sometimes makes an implementor's life a little easier. And, in fact, the pseudocode contains a "hidden" inner loop in this statement:
Select next required value from remaining unsorted values

The other thing to note is that this may not be the world's best implementation of selection sort, but it has the advantage of being straightforward and therefore both easy to understand and implement, and easy to analyze.

So, note first that the outer loop executes n-1 times, and during each loop it performs one exchange (i.e., three assignments), so there are n-1 exchanges (or 3*(n-1) assignments) in all.

Second, note that the inner loop executes

n-1 times on the first pass of the outer loop
n-2 times on the second pass of the outer loop
...
1 time on the last (i.e., the (n-1)th) pass of the outer loop

n-1 + n-2 + n-3 + ... + 2 + 1 = (n-1)n/2

It follows that the total number of operations (counting both comparisons and assignments, or we could count comparisons and exchanges, since the result would be the same) is given by

(n–1)n/2 + 3(n–1) = n²/2 – n/2 + 3n – 3 = n²/2 + 5n/2 – 3

which is O(n²).