Selection Sort
O(n²)

History

Selection Sort is an in-place comparison sorting algorithm. It divides the input into a sorted and unsorted region. The algorithm was one of the first sorting methods to be formally studied in computer science, appearing in early computing literature in the 1950s. While not efficient for large datasets, it has the advantage of making the minimum number of swaps (O(n)), which can be useful when memory writes are expensive.

How it works

Find the minimum element in the unsorted portion
Swap it with the first unsorted element
Move the boundary of sorted portion one element ahead
Repeat until the entire array is sorted

When to use

Minimal swaps needed: Only O(n) swaps are made
Memory writes are expensive: Like flash memory
Small datasets: Simple implementation
Checking if sorted: Easy to verify correctness

Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let minIdx = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
    return arr;
}

func selectionSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
    return arr
}

fn selection_sort<T: Ord>(arr: &mut [T]) {
    let n = arr.len();
    for i in 0..n {
        let min_idx = (i..n)
            .min_by_key(|&j| &arr[j])
            .unwrap();
        arr.swap(i, min_idx);
    }
}