DSA Selection Sort

How Selection Sort Works

Selection sort splits the list into a sorted portion at the front and an unsorted portion at the back. On each pass, it scans the entire unsorted portion to find the smallest remaining value, then swaps that value into the first position of the unsorted portion, growing the sorted portion by exactly one element.

• Assume the first unsorted element is the minimum so far
• Scan the rest of the unsorted portion looking for a smaller value
• Track the index of the smallest value found, not the value itself
• After scanning the whole unsorted portion, swap that minimum into the first unsorted position
• Move the boundary between sorted and unsorted forward by one and repeat

Basic Implementation

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

print(selection_sort([5, 2, 4, 1, 3]))  # [1, 2, 3, 4, 5]

Trace selection_sort on [5, 2, 4, 1, 3]. Pass 1 (i=0) scans indices 1 through 4 looking for the smallest value: 2 beats the initial guess of 5, then 4 does not beat 2, then 1 beats 2, then 3 does not beat 1 - so the minimum is 1 at index 3, and it swaps with index 0 to give [1, 2, 4, 5, 3]. Pass 2 (i=1) scans indices 2 through 4 and finds nothing smaller than 2, so it swaps index 1 with itself, leaving the list unchanged. Pass 3 (i=2) scans indices 3 and 4 and finds 3 is smaller than 4, so it swaps index 2 with index 4 to give [1, 2, 3, 5, 4]. Pass 4 (i=3) compares index 4's value of 4 against index 3's value of 5 and swaps them to give the final result [1, 2, 3, 4, 5].

Unlike bubble sort, selection sort performs at most one swap per pass no matter how sorted the input already is, which makes it attractive when swaps are expensive - for example, writing to slow storage - even though it does not benefit from an early-exit optimization on nearly-sorted input.

def selection_sort_count_swaps(numbers):
    n = len(numbers)
    swaps = 0
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if numbers[j] < numbers[min_index]:
                min_index = j
        if min_index != i:
            numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
            swaps += 1
    return numbers, swaps

print(selection_sort_count_swaps([5, 2, 4, 1, 3]))  # ([1, 2, 3, 4, 5], 3)
print(selection_sort_count_swaps([1, 2, 3, 4, 5]))  # ([1, 2, 3, 4, 5], 0)

def selection_sort_count_comparisons(numbers):
    n = len(numbers)
    comparisons = 0
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            comparisons += 1
            if numbers[j] < numbers[min_index]:
                min_index = j
        numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
    return numbers, comparisons

print(selection_sort_count_comparisons([5, 2, 4, 1, 3]))  # ([1, 2, 3, 4, 5], 10)
print(selection_sort_count_comparisons([1, 2, 3, 4, 5]))  # ([1, 2, 3, 4, 5], 10)