Selection Sort

• Moves the max/min element to the correct side of the array after each pass
• Comparisons: $O(n^2)$, Exchanges: $O(n)$

Implementation

for fill = 0 to n - 1
	posMin = fill
	for next = fill + 1 to n - 1
		if arr[next] < arr[posMin]
			posMin = next
	swap arr[posMin] and arr[fill]

void selectionSort (int array[], int size) {
	for (int i = 0; i < size - 1; i++) {
		int min_index = i;
		for (int j = i + 1; j < size; j++) {
			if (array[j] < array[min index])
				min_index = j;
		}
		// put min at the correct position
		swap(&array[min_index], &array[il);
	}
}