Selection Sort

Steps

• Loop through the array
• Find the smallest element in the unsorted portion of the array
• Swap the smallest element with the first element in the unsorted portion of the array

The sorted portion of the array is on the left side while the unsorted portion is on the right. In the diagrams below, the blue boxes represent the sorted elements of the array, while the white boxes represent the unsorted elements. Elements that are going to be swapped are shown in green boxes.

On every iteration, an element from the unsorted portion is added to the sorted portion. For example, if we start with this array:

At this stage, the unsorted array is the entire array. The smallest element found is 1, so swap that with the first element of the unsorted array.

So after the first iteration, only the first element is sorted:

Now loop through the unsorted array (the items after the first element, which is now sorted). In the unsorted array, swap the smallest item with the first item

After the second iteration, the first two elements are sorted, as another element from the unsorted portion is added to the sorted portion:

This continues n - 1 times, where n is the length of the list.

Third iteration:

Fourth iteration:

Fifth iteration:

Note that it runs n - 1 times, since the last element is already sorted.

Pseudocode

function selection_sort(list):
  n = list.length

  for i from 0 to n-1:
    # Initialize smallest element to first one
    smallest_index = 1

    # Traverse through the unsorted list to find the 
    # smallest element
    for j from i to n:
      if collection[j] < collection[smallest_index]:
        smallest_index = j
    
    # Swap smallest element with first element of 
    # unsorted list
    swap(collection[smallest_index], collection[i])
  
  return collection

Python

While the pseudocode will produce expected results, there is a simple optimization we can make.

• smallest_index is already given an initial value of i, so there is no need to start at i in the inner for loop. Even if i happens to be the smallest value, smallest_index is already set to i.
• We only need to swap collection[smallest_index] and collection[i] if i is not equal to smallest_index.

def selection_sort(collection):
  length = len(collection)

    for i in range(length - 1):
        smallest_index = i
        for j in range(i + 1, length):
            if collection[j] < collection[smallest_index]:
                smallest_index = j

        if smallest_index != i:
            collection[smallest_index], collection[i] = (
                collection[i],
                collection[smallest_index],
            )

    return collection

To debug, I am going to run the following and print the list at every iteration:

selection_sort([3, 5, 2, 1, 9, 6])

The output is

[3, 5, 2, 1, 9, 6]
[1, 5, 2, 3, 9, 6]
[1, 2, 5, 3, 9, 6]
[1, 2, 3, 5, 9, 6]
[1, 2, 3, 5, 9, 6]
[1, 2, 3, 5, 6, 9]
[1, 2, 3, 5, 6, 9]

Time complexity

The worst-case scenario is $O(n^2)$ since there is a nested loop.

The first iteration has n swaps, the second has n - 1, the third has n - 2, and so on, so

$n + (n - 1) + (n - 2) + (n - 3) + ... + 1 = \cfrac{n^2}{2} + \cfrac{n}{2}$

Since $n^2$ is the highest magnitude, the time complexity is $O(n^2)$.

The best case scenario is also $\Omega{(n^2)}$ since selection sort will not exit if the list is already sorted.