Selection Sort: Find the Smallest Remaining Value
Goal: Understand how selecting one minimum fixes one position.
We want to sort [5,6,3,4,2] in ascending order. Search the whole array for its smallest value: 2. Exchange it with the first value, 5. The array becomes [2,6,3,4,5]. Exchanging two values is a swap.
The first position is now correct. Search only the remaining part, choose its smallest value, and put that value at the start of that part. This is Selection Sort. Each round fixes one more position.
Read the code after the idea
#include <utility>
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
std::swap(a[i], a[minIndex]);
}
}
Here n is the array length and is a nonnegative integer. a[i] means the value at index i; the first index is 0.
minIndex stores the position of the smallest value found so far, not the value itself. For the value 2 at index 4, it stores 4. We need that position when calling swap. The two parts are inside the same array; we do not create a second array.
Before the First Selection Round
We have not finished searching for the minimum yet. How many elements are in the part whose final positions have already been fixed?
Remember: Search the remaining part first. Swap only after the search is complete.