Selection Sort: Simple But Effective

The selection sort is a simple but effective brute force method for sorting elements in ascending order, and it can be useful in a pinch when you know that your data set is small.

The sort works by looping n times, where n is the number of elements in the list, and at each step finding the i-th smallest element. Below is a sample implementation of the sort.

template<typename T>
void selection_sort(vector<T>& list)
{
	for (int i = 0; i < list.size(); ++i) // Iterate each item
	{
		int min = i;
		for (int j = i + 1; j < list.size(); ++j) // At each step, find the smallest remaining item
		{
			if (list[j] < list[min])
			{
				min = j;
			}
		}

		exchange(list, i, min); // Place it at the ith lowest position of the list
	}
}

For each step i, start with the assumption that list[i] is the smallest remaining element - in other words, that list[i] is in its proper sorted place. Then step through each following item, looking for smaller items. After having gone through every remaining item, we can be confident that we have found the smallest one. This item is the i-th smallest item, and so we swap the elements at i and min. Here is the exchange method.

template<typename T>
void exchange(vector<T>& list, int i, int j)
{
	T temp = list[i];
	list[i] = list[j];
	list[j] = temp;
}

By repeating this process for every i, we can find the 0th smallest item, then then 1st smallest item, then the 2nd smallest item, and so forth until the list is entirely sorted.

As you can see, this sort involves only a handful of instructions and thus is fairly easy to implement. However, this simplicity comes at the cost of efficacy. Selection sort exhibits quadratic complexity because the entire list (minus the first i elements) must be scanned at every step i. Thus, the runtime of selection sort may be unacceptable for sorting non-trivial amounts of data.

At the same time, the sort requires very little additional memory - just a few index counters - and so it may be useful in contexts where memory is at a premium and where the data to be sorted is limited.