Selection Sort (Python)

Pick the minimum, put it in place, repeat. Simple, in-place, and write-efficient — but quadratic time.

Quiz progress
0 / 10 answered

Idea & when to use #

Core idea

For position i (0..n-1): find the minimum in the suffix i..n-1, swap it into i.

Good for

  • Very small arrays (teaching / quick demo).
  • When writes are expensive (e.g., flash memory) — only ~n-1 swaps.

Not great for

  • Large inputs (Θ(n²) comparisons regardless of order).
  • Nearly-sorted data (insertion sort is better: O(n) best-case).

Algorithm & Python code #

Pseudocode

for i from 0 to n-2:
    min_idx = i
    for j from i+1 to n-1:
        if a[j] < a[min_idx]:
            min_idx = j
    swap a[i], a[min_idx]

Python (in-place)

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

nums = [5, 2, 9, 1, 5, 6]
print(selection_sort(nums))  # [1, 2, 5, 5, 6, 9]
Observation: The outer loop runs n-1 times. The inner loop does ~n-i-1 comparisons. Total ≈ n(n-1)/2 comparisons; swaps ≤ n-1.

Complexity & properties #

BestAverageWorstSpaceStable?SwapsComparisons
Θ(n²)Θ(n²)Θ(n²)O(1) No (by default)≤ n−1≈ n(n−1)/2
Why O(1) space? It sorts in-place, using only a few index variables and occasional swaps.

Variants & stability #

Min–Max (bidirectional)

On each pass, select the minimum and maximum and place them at both ends. Fewer passes, still Θ(n²) comparisons; useful if reducing pass count matters (cache/IO patterns).

def selection_minmax(a):
    l, r = 0, len(a)-1
    while l < r:
        min_i, max_i = l, l
        for j in range(l, r+1):
            if a[j] < a[min_i]: min_i = j
            if a[j] > a[max_i]: max_i = j
        a[l], a[min_i] = a[min_i], a[l]
        # fix max index if it was at l
        if max_i == l: max_i = min_i
        a[r], a[max_i] = a[max_i], a[r]
        l += 1; r -= 1
    return a

Stable Selection Sort

Instead of swapping the minimum into position i, remove it and shift the block right by one, preserving equal-element order.

def selection_sort_stable(a):
    n = len(a)
    for i in range(n-1):
        min_idx = i
        for j in range(i+1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        key = a[min_idx]
        while min_idx > i:
            a[min_idx] = a[min_idx-1]
            min_idx -= 1
        a[i] = key
    return a

Recursive style

Same work; shown for completeness.

def selection_sort_rec(a, i=0):
    n = len(a)
    if i >= n-1: return a
    min_idx = min(range(i, n), key=a.__getitem__)
    if min_idx != i:
        a[i], a[min_idx] = a[min_idx], a[i]
    return selection_sort_rec(a, i+1)
Selection sort vs insertion sort: Selection does fewer writes (≤ n−1 swaps) but a fixed Θ(n²) comparisons; insertion may do many writes but is adaptive and can be O(n) on nearly-sorted data.

Interactive playground #

Edit the Python code or the input array. Click Run to execute in-browser (Pyodide).

Output will appear here.

Quiz #

1. What is the time complexity of selection sort?
2. Maximum number of swaps on an array of length n?
3. Is selection sort stable by default?
4. Extra space required?
5. Best-case time complexity?
6. Choose the true statements.
7. How to make selection sort stable?
8. Selecting both min and max each pass mostly…
9. Compared to bubble sort, selection sort typically…
10. Quickselect is best described as…