Selection Sort

Share

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

Example 1
Input: [64, 25, 12, 22, 11] → Output: [11, 12, 22, 25, 64]
Example 2
Input: [29, 10, 14, 37, 13] → Output: [10, 13, 14, 29, 37]

Solution Approach

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.
Java
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