Selection Sort

A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then repeats this process starting with the sublist from the 2nd element onwards.

The loop invariants are:

When looking at the sublist from i+1 onwards, all the entries are greater than the sublist up to i.
Everything to the left of the i-th element is sorted in ascending order.

To increment the loop, we increase i. The invariant breaks, so we take steps to restore the invariance. Those steps are the actual algorithm.

Complexity

The complexity is \(\Theta(N^{2})\).

Properties

The expense is \(N^{2}\) regardless of the input - even if the list is already sorted.
The data movement is minimal. Each item moves at most once, and when it does move it is to its final location.
The sorting is in-place. No extra memory is needed, and is thus useful in tight memory situations.
It is not a stable sort, as when you swap, placing the current element ahead in the array can break stability.

Implementations

Python

def selection_sort(lst, comparator=None):
    """
    Selection sort. It takes in a list of objects and sorts them based
    on the comparator. It only works with a list. 
    
    Keyword Arguments:
    lst        -- List to sort
    comparator -- Comparator function. It should take in two arguments, and
                  return -1 if the left is smaller, 1 if the right is smaller,
		  and 0 if they are equal. If none is provided, then it will
		  assume a numerical sort.
    """
    if not comparator:
	def comp(left, right):
	    if left < right:
		return -1
	    elif left > right:
		return 1
	    else:
		return 0
	comparator = comp

    for index in xrange(len(lst)):
	minimum = lst[index]
	min_index = index
	for inner_index in xrange(index+1, len(lst)):
	    if comparator(lst[inner_index], minimum) == -1:
		minimum = lst[inner_index]
		min_index = inner_index
	tmp = lst[index]
	lst[index] = minimum
	lst[min_index] = tmp

C++

#include <algorithm>
#include <vector>

void selection_sort(std::vector<int>& lst);

void selection_sort(std::vector<int>& lst)
{
  for(std::vector<int>::iterator outer_it = lst.begin(); 
      outer_it != lst.end(); ++outer_it) 
    {
      int minimum = *outer_it;
      std::vector<int>::iterator min_location = outer_it;
      for(std::vector<int>::iterator inner_it = outer_it + 1;
          inner_it != lst.end(); ++inner_it) 
        {
          if ((*inner_it) < minimum)
            {
              minimum = *inner_it;
              min_location = inner_it;
            }
        }
      std::iter_swap(min_location, outer_it);
    }
}