Selection Sort

Selection Sort is a O(n2) sorting algorithm. Working from left to right, the algorithm repeatedly finds the smallest remaining element and places it in the correct position.

The problem

Sort a given array with n elements (integers, strings, etc.).

Sorting is often required in practical applications. For example, on most online stores you can sort the products by name, price, popularity and other attributes.
There are also some algorithms, like Binary Search, which require sorting as a preprocessing step.

When to use it

Selection Sort is a great algorithm for sorting relatively small arrays. It is easy to learn and simple to implement, which makes it perfect for beginners.
If you need to sort a large array, then Selection Sort is not a good choice because of the running time.

Algorithm Description

The algorithm uses an integer variable current which is illustrated as an arrow below.
Throughout the algorithm, every element left of the arrow (with index < current) is in the correct position.

Set current = 0 and repeat until current = n:

  1. Find the smallest element with index >= current (elements right of the arrow or at the arrow)
  2. Swap the located element with the element at index current
  3. Increment current

Note: array[current] may be the smallest element with index >= current.
In this case array[current] is already in the correct position and the array will be unchanged.

Implementation Detail

The swap operation can be a little tricky to implement and many people get it wrong the first time.
Given an array arr and two indices i and j, we want to swap arr[i] and arr[j].

Wrong implementation

  1. arr[i] = arr[j]
  2. arr[j] = arr[i]

The problem is that both arr[i] and arr[j] will contain the same element - the one that was initially at index j.
We need to use a temporary variable to store one of the elements.

Correct implementation

  1. tmp = arr[i]
  2. arr[i] = arr[j]
  3. arr[j] = tmp

Running Time

Linear Search is a O(n2) algorithm. The most expensive part of Selection Sort is finding the smallest element at each step.
In the first step Selection Sort finds the smallest of n elements, then n-1 elements in step 2, n-2 elements in step 3, and so on.
The sum of these numbers have the form: 1+2+3+...+n (written in opposite order).
This well known sum solves to n(n+1)/2 which is roughly n2/2 making Linear Search a quadratic time algorithm.