Selection Sort

Selection Sort is an in-place comparison sorting algorithm that divides the input list into a sorted and unsorted region. It repeatedly finds the minimum element from the unsorted region and moves it to the end of the sorted region.

Complexity Analysis

Best Case

O(n²)

Average Case

O(n²)

Worst Case

O(n²)

Space Complexity

O(1)

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i;

        // Find minimum element in unsorted portion
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap if minimum is not at current position
        if (minIndex !== i) {
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    return arr;
}

How Selection Sort Works

Selection Sort maintains two subarrays: a sorted subarray on the left and an unsorted subarray on the right. Initially, the sorted subarray is empty and the unsorted subarray contains all elements.

Algorithm Steps:

  1. Set the first element as the minimum
  2. Compare this minimum with the next element in the unsorted subarray
  3. If the next element is smaller, update the minimum index
  4. Continue scanning the unsorted subarray to find the absolute minimum
  5. Swap the minimum element with the first element of the unsorted subarray
  6. Move the boundary between sorted and unsorted subarrays one element to the right
  7. Repeat until the entire array is sorted

Key Characteristics:

  • Simple: Easy to understand and implement
  • In-place: Requires only constant extra space O(1)
  • Unstable: Does not maintain relative order of equal elements
  • Predictable: Performance is O(n²) regardless of input order
  • Minimal swaps: Makes only O(n) swaps in worst case

Comparison with Other O(n²) Sorts:

  • vs Bubble Sort: Fewer swaps but same time complexity
  • vs Insertion Sort: Worse performance on nearly sorted arrays
  • Advantage: Predictable running time, minimal data movement