Selection Sort is not magic! What's going on?

[UncleBazerko]

I just noticed something about selection sort that I overlooked:

7 was smaller than 16 first.

How does my selection sort function know that 5 exists even though a linear search would encounter 7 first (since 7 is also smaller than 16)? It can't be the result of a binary search either, because the data hasn't even finished getting sorted yet. So what's going on?

void selectionSort(int arr[], int n)
{
	int smallestIndex;
	int smallest, saved;

	for (int i = 0; i < n - 1; i++) {
		// Find smallest element
		smallest = arr[i];
		smallestIndex = i;

		for (int j = i + 1; j < n; j++) {
			if (arr[j] < smallest) {
				smallest = arr[j];
				smallestIndex = j;
			}
		}
		// Swap with smallest element
		saved = arr[i];
		arr[i] = arr[smallestIndex];
		arr[smallestIndex] = saved;
	}
}

[laserlight]

How does my selection sort function know that 5 exists even though a linear search would encounter 7 first (since 7 is also smaller than 16)? It can't be the result of a binary search either, because the data hasn't even finished getting sorted yet. So what's going on?

Upon encountering 7, 7 becomes the new smallest known element, so by the time 5 is encountered, 5 being less than 7, 5 becomes the new smallest known element.

[VictorN]

...
How does my selection sort function know that 5 exists even though a linear search would encounter 7 first (since 7 is also smaller than 16)? It can't be the result of a binary search either, because the data hasn't even finished getting sorted yet. So what's going on?

It is because you do not break the inner loop after finding the first number being smaller, but continue the search and comparison until the end of array.