Сортировка выбором хранит слева отсортированный префикс, справа неотсортированный остаток. На каждом шаге она находит минимум остатка и меняет его с первым элементом остатка. Сравнений много, но обменов не больше n - 1. Свойства описаны в уроке свойства сортировок.

Сортировка выбором для 64 25 12 22 11
Сортировка выбором для 64 25 12 22 11

Инвариант

После i шагов a[:i] содержит i наименьших элементов массива в отсортированном порядке, а каждый элемент остатка не меньше любого элемента префикса. При i = n - 1 последний элемент автоматически на месте.

python
a = [64, 25, 12, 22, 11]
n = len(a)
for i in range(n - 1):
    m = i
    for j in range(i + 1, n):
        if a[j] < a[m]:
            m = j
    a[i], a[m] = a[m], a[i]
    print("i =", i, "min at", m, a)
text
i = 0 min at 4 [11, 25, 12, 22, 64]
i = 1 min at 2 [11, 12, 25, 22, 64]
i = 2 min at 3 [11, 12, 22, 25, 64]
i = 3 min at 3 [11, 12, 22, 25, 64]