Selection sort - Introduction to Programming - Python

Selection sort

Sorting by repeatedly finding the minimum of the unsorted suffix and placing it in its correct position.

Selection Sort

Selection Sort divides the list into a sorted prefix and an unsorted suffix. In each of the $n-1$ iterations, it finds the smallest element in the unsorted suffix and swaps it into the next position of the sorted prefix. After $i$ iterations, the first $i$ elements are in their final sorted positions.

Example

How It Works Step by Step

For a = [5, 3, 8, 1, 9, 2]:

Summary

Case	Complexity
Worst / Average / Best	$O(N^2)$

Up next

Insertion sort

Sorting by maintaining a sorted prefix and inserting each new element into its correct position, with adaptive O(N) behavior on nearly sorted data.

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

i=0: min is 1 at index 3 → swap a[0] and a[3] → [1, 3, 8, 5, 9, 2]
i=1: min is 2 at index 5 → swap a[1] and a[5] → [1, 2, 8, 5, 9, 3]
i=2: min is 3 at index 5 → swap a[2] and a[5] → [1, 2, 3, 5, 9, 8]
i=3: min is 5 at index 3 → no swap needed     → [1, 2, 3, 5, 9, 8]
i=4: min is 8 at index 5 → swap a[4] and a[5] → [1, 2, 3, 5, 8, 9]