Finding the minimum

Find the index of the minimum in a slice.

Swapping

Once the minimum is found, you swap it with the first element of the unsorted part. This places that element in its correct position.

Swapping takes O(1) time: only two elements are exchanged. In total, n-1 swaps are performed.

Sorted part growth

After each swap, the sorted part grows by one element. Selection sort expands the sorted part from the start to the end.

At step i, the first i elements are sorted and the rest are unsorted. At the last step, the whole array is sorted.

Exercise Swap elements

Write swap_min(arr, i, min_idx). Swap arr[i] and arr[min_idx], return arr. Print [1, 3, 2] with print(swap_min([3, 1, 2], 0, 1)).

Show example solution

def swap_min(arr, i, min_idx):
    # Swap two elements
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
print(swap_min([3, 1, 2], 0, 1))

Test yourself

Swap

Swap two elements: arr[i], arr[min_idx] = ____

Show answer

Swap two elements: arr[i], arr[min_idx] = arr[min_idx]

Finding the minimum: match the terms

Swap

Exchange
min_idx

Minimum index
O(1)

Swap time
n-1

Swap count
How long does a swap take?
- O(log n)
- O(n^2)
- O(n)
- O(1)
Show answer

O(log n) — A swap is O(1).

Next lesson: Swapping

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies