Selection Sort Implementation

Problem Statement

Sort an array using selection sort: on each round, find the minimum element in the unsorted portion and swap it into the next position.

Example

Input:  [64, 25, 12, 22, 11]
Step:   find min 11 -> front
Output: [11, 12, 22, 25, 64]

Approach

Maintain a growing sorted prefix. For position i, scan the rest of the array to find the index of the minimum, then swap it into place. It always performs the same number of comparisons regardless of input, but at most n-1 swaps — useful when writes are expensive.

Complexity

• Time: O(n^2) in all cases
• Space: O(1)

Solution Code

Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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

Java

void selectionSort(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 t = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = t;
    }
}

C++

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    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;
        swap(arr[i], arr[minIdx]);
    }
}

Key Takeaways

• Selection sort uses the fewest swaps (at most n-1) of the simple sorts.
• The standard version is not stable; comparisons are always O(n^2).
• Reference: CLRS; Wikipedia, "Selection sort".