Selection Sort

Given an unsorted array of integers, sort it in ascending order using Selection Sort. Modify the array in-place ($O(1)$ extra space). Input: [64, 25, 12, 22, 11] → Output: [11, 12, 22, 25, 64]. Do not use built-in sort functions.

Selection Sort divides the array into a sorted portion (left) and an unsorted portion (right). In each iteration, find the minimum of the unsorted portion and swap it to the front. After $N$ passes, one more element is permanently placed — the key idea is "select the minimum and place it correctly."

1. Iterate through the array from index $i = 0$ to $N-1$.
2. Assume arr[i] is the minimum. Scan the remaining unsorted portion ($i+1$ to $N-1$) to find the true minimum index.
3. Swap arr[i] with arr[min_index].
4. Repeat until the entire array is sorted.

• Swapping inside the inner loop instead of after finding the minimum
• Forgetting to reset min_index for every outer loop iteration
• Assuming it becomes faster for already sorted arrays (it does not — always $O(N^2)$)
• Confusing with Bubble Sort (Selection Sort minimizes swaps; Bubble Sort minimizes passes when optimized)

Selection Sort performs at most $N$ swaps, useful when write operations are costly. However, it always runs in $O(N^2)$ regardless of input. Its value lies in understanding loop invariants and sorting logic before moving to $O(N \log N)$ algorithms like Merge Sort or Quick Sort.