Selection sort

Selection sort is a primitive sorting algorithm. The premise is simple: we’re selecting a number and placing it in the correct position in the array. So for each iteration, we find the largest number that we haven’t sorted and place it in the right-most index and keep moving left until the array is fully sorted.

For each iteration of the sort, the sub-array we examine is one less than the previous iteration, i.e., we look for the largest number $n-1$ times for an $n$ sized array. For each iteration, we look at a decreasing number of comparisons. This means selection sort has a time complexity of $O(n^2)$.

To implement iteratively, we need two for loops. The if statement should update the index of the largest element. Here is an iterative implementation in C:

void selectionSort (int list[], int n) {
	int largeLoc;
	for (int top = n - 1; top > 0; top--) {
		largeLoc = 0;
		for (int i = 1; i <= top; i++) {
			if (list[i] > list[largeLoc]) {
				largeLoc = i;
			}
		}
		int temp = list[largeLoc];
		list[largeLoc] = list[top];
		list[top] = temp;
	}	
}

We could probably find a recursive implementation too, or alternatively increment up in the outer for loop by starting from the left end of the array.