Swapping

Swap the minimum to the front; count the rounds.

Full selection sort

Full selection sort uses an outer loop for each position; the inner search finds the minimum from that position onward and swaps.

The outer loop goes from 0 to n-2; the inner search goes from i to n-1. At each step, a minimum is found and swapped.

Complexity analysis

Selection sort's complexity is always O(n^2). Best, worst and average cases are the same because all remaining elements are always scanned.

The number of swaps is at most n-1, which is fewer than bubble sort. But the number of comparisons is always n(n-1)/2.

Exercise Selection sort

Write selection_sort(arr). Find minimum at each position and swap. Print [11, 12, 22, 25, 64] with print(selection_sort([64, 25, 12, 22, 11])).

Show example solution

def selection_sort(arr):
    # Sort the array
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr
print(selection_sort([64, 25, 12, 22, 11]))

Test yourself

Swapping: match the terms

Outer loop

0 to n-2
Inner search

i to n-1
Swap

n-1 times
O(n^2)

Always
How many comparisons does selection sort make in the best case?
- n
- n(n-1)/2
- 1
- 0
Show answer

n(n-1)/2 — Even in the best case, n(n-1)/2 comparisons.

Outer loop

The outer loop runs with ____ range(n - 1).

Show answer

The outer loop runs with for i in range(n - 1).

Next lesson: Summary - Selection sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies