Summary - Selection sort

Implement selection sort in a mini task.

Summary - Selection sort

In this group you learned selection sort's logic, finding minimum, swapping and full sorting. Complexity is always O(n^2).

Selection sort does few swaps (n-1) but many comparisons (n^2). It is simple but slow.

Exercise Selection sort step

Write selection_step(arr, i). Find minimum after i and swap with arr[i]. Print [1, 3, 2] with print(selection_step([3, 1, 2], 0)).

Show example solution

def selection_step(arr, i):
    # Do one step
    min_idx = i
    for j in range(i + 1, len(arr)):
        if arr[j] < arr[min_idx]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
print(selection_step([3, 1, 2], 0))

Test yourself

Summary - Selection sort: match the terms

Selection sort

Pick smallest
Minimum

Find index
Swap

Exchange
O(n^2)

Always

Selection sort

Selection sort finds the ____ at each step.

Show answer

Selection sort finds the smallest at each step.

How many swaps does selection sort make?
- n^2
- n log n
- 1
- n-1
Show answer

1 — At most n-1 swaps.

Next lesson: Insertion sort idea

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies