Sorting - Selection Sort

Implement the Selection Sort algorithm. Repeatedly find the minimum element from the unsorted part of the array and place it at the beginning.

Input: [64, 25, 12, 22, 11] → Output: [11, 12, 22, 25, 64]

Input: [29, 10, 14, 37, 13] → Output: [10, 13, 14, 29, 37]

Divide the array into sorted and unsorted halves. On each pass, find the minimum of the unsorted part and swap it with the first unsorted element.

Outer loop i from 0 to n-2 marks the start of the unsorted portion.
Find the index of the minimum element in arr[i..n-1].
Swap arr[i] with arr[minIdx].
After n-1 passes the array is fully sorted.

class SelectionSort { public void sort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; } int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } } }

Time Complexity: O(N^2) all cases
Space Complexity: O(1) in-place