Selection Sort

selection-sort.h

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

/**
 * In a typical selection sort (a simple, but inefficient
 * sort method), the sort is conducted in place by
 * iterating over each item in the list.
 * At each item, assume it is the minimum until proven wrong.
 * Find the minimum of remaining items, and swap it into the
 * current slot. By the end, all items will be in place.
 * This sort exhibits quadratic time complexity (O(n2))
 * because it has two inner loops.
 */
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 minimum remaining item
		{
			if (list[j] < list[min])
			{
				min = j;
			}
		}

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