Selection Sort

[Ganon11]

Earlier, mmccarthy was kind enough to post a short article explaining the Bubble Sort. As she said, this is a relatively slow sorting algorithm. Here, I will attempt to present a slightly faster algorithm called Selection Sort.

Imagine you have a list of numbers in random order. You want to sort these numbers in increasing order - that is, every element is smaller than or equal to the next element. It follows that the first element holds the smallest value, the second element holds the second smallest value, and so on.

So, to determine the first element's contents, we must find the smallest value in the rest of the list. Once we do that, we can swap this smallest value with the first element. Now the first element is finished being sorted, and we can continue with the rest of the list.

This basic process can be repeated, treating the second element of the original array as the first element in a smaller array.

To help visualize, suppose we have an array with 5 elements like this:

Index: 0 1 2 3 4
Array: 5 8 2 3 1

To determine the first element in our sorted array, we must find the smallest element in the rest of the array. This is Array[4], or 1. So we switch these values to obtain the 'new' array:

Index: 0 1 2 3 4
Array: 1 8 2 3 5

Now we consider the sub-array from 1 to 4. To determine the 'first element' of this array, we find the smallest element in the range 1-4. This happens at Array[2], or 2. So we switch these values:

Index: 0 1 2 3 4
Array: 1 2 8 3 5

Continuing in this same way, we would then switch Array[3] with Array[2], and then Array[4] with Array[3] to obtain the final, sorted array:

Index: 0 1 2 3 4
Array: 1 2 3 5 8

Now, how to put this into code? I usually implement this algorithm using 2 nested for...loops. The first loop goes from 0 to n-1, where n is the size of the array. This is because we must consider individually each sub-array Array(i) such that Array(i) contains values at Array[i], Array[i+1], Array[i+2]...Array[n-1] to sort. When we check each sub-array, we must have a variable to hold the position of the smallest value we have found. This will change throughout the execution of the second loop. Before we begin checking any values, we assume that the smallest value is Array[i], so smallest contains i. This makes sense - we have checked only one value, so that value must be the smallest.

The second for loop will go from i (the index of the first loop) to n-1. This loop is finding the smallest element in the sub-array Array(i). Let us say that this loop uses j as its index. This means that we must check if Array[j] is less than Array[smallest] - if it is, we have found a new smallest value, and must assign j to smallest.

Once this second loop has finished executing, we know that smallest contains the index of the smallest value in Array(i). We then swap the values at Array[i] (the first element in Array(i)) and Array[smallest] (the smallest element in Array(i)). Now we have finished with this execution of the first for loop.

In pseudocode, the above becomes:

void SELECTIONSORT(int array[], int n) { // n is the size of the array
   FOR (i loops from 0 to n-1)
      int smallest = i
      FOR (j loops from i to n-1)
         IF (array[j] is smaller than array[smallest])
            smallest = j
      SWAP(array, i, smallest)
}

To make the code shorter, I used a function SWAP that will swap the elements in array. This is a short function that looks something like this:

void SWAP(int array[], int from, int to) {
   int temp = array[from];
   array[from] = array[to];
   array[to] = temp;
}