3.49 Selection Sort Array

3.49.1 Problem Metadata

3.49.2 Description

Given an integer array, sort it in ascending order using the selection sort algorithm.

3.49.3 Examples

Input: [3,5,1,4,2]
Output: [1,2,3,4,5]

3.49.4 Constraints

  • 1 <= n <= 10^4
  • Elements fit in 32-bit signed integers

3.49.5 Solution - Iterative Selection

3.49.5.1 Walkthrough

Selection sort repeatedly selects the smallest remaining element and swaps it into the next output position. For each index i, scan the suffix [i, n) to find the minimum value and swap it with arr[i].

3.49.5.2 Analysis

  • Time Complexity: O(n^2) due to nested loops
  • Space Complexity: O(1)

3.49.5.3 Implementation Steps

  1. For i from 0 to n - 1, set minIndex = i.
  2. For j from i + 1 to n - 1, update minIndex when arr[j] < arr[minIndex].
  3. Swap arr[i] with arr[minIndex].
  4. Return the sorted array.

3.49.5.4 Code - Java

public int[] selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}