Сортировка выбором в Python: понятный учебный алгоритм

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

Сортировка выбором делит список на готовую левую часть и ещё не обработанный хвост. Для каждой позиции алгоритм находит минимальный элемент хвоста и меняет его местами с текущим. Это учебный способ увидеть индексы и обмен; в обычной программе лучше встроенный sort.

Один внешний шаг за другим

numbers = [5, 2, 4, 1]

for position in range(len(numbers) - 1):
    min_index = position
    for index in range(position + 1, len(numbers)):
        if numbers[index] < numbers[min_index]:
            min_index = index
    numbers[position], numbers[min_index] = (
        numbers[min_index],
        numbers[position],
    )

print(numbers)

Результат:

[1, 2, 4, 5]

После первого шага минимум всего списка находится на позиции 0. Затем поиск начинается с позиции 1, не разрушая готовую часть.

Ошибки индексов и обмена

Если min_index не сбрасывать в position перед внутренним циклом, он может указывать в уже отсортированную область. Если внутренний range начинать с нуля, алгоритм делает лишние сравнения и нарушает понятный инвариант. Обмен через временную переменную тоже корректен, но параллельное присваивание Python короче.

Алгоритм выполняет порядка n² сравнений даже для почти отсортированных данных. Это причина изучать его как модель, а не заменять им list.sort.

Трассировка проходов

Добавьте print(position, numbers) после обмена и вручную предскажите состояния для [3, 1, 2]. Проверьте повторы, уже отсортированный и обратный список. Затем измените сравнение для убывающего порядка. Убедитесь, что на каждой итерации готовая часть действительно содержит нужные элементы.

Сортировка на копии и инвариант

Перед каждым проходом сортировки сохраняйте копию и проверяйте, что мультимножество элементов не изменилось: sorted(before) равно sorted(after). Дополнительно убедитесь, что готовый префикс действительно отсортирован и не содержит элементов больше оставшегося минимума. Проведите трассировку на повторяющихся и отрицательных значениях. Затем сравните результат со встроенной sorted как с эталоном для малых тестов. Не заменяйте объяснение алгоритма этим сравнением: оно лишь обнаруживает ошибку реализации. После проверки удалите диагностические копии из финальной версии, оставив тесты рядом с учебной функцией.

Практикум: инвариант сортировки выбором

Отсортируйте 5, 2, 5, -1, 3 выбором минимума. После каждого внешнего шага записывайте готовый префикс и оставшуюся часть. Проверяйте, что префикс отсортирован, а набор элементов не изменился. Сравните итог со sorted как эталоном, но не заменяйте этим объяснение алгоритма. Посчитайте сравнения для длины 5 и выведите формулу для n. Затем исследуйте, сохраняется ли порядок равных пятёрок, если они имеют дополнительные метки.

Контрольная точка

Что гарантировано перед итерацией с индексом i? Первые i позиций уже содержат наименьшие элементы в правильном порядке; это определяет поиск и обмен на очередном шаге.

Частые вопросы

Зачем изучать простую сортировку, если есть sorted?

Для прикладного кода используют библиотечную сортировку. Учебная реализация показывает инварианты, вложенные циклы и квадратичную сложность, чтобы позже обоснованно сравнивать алгоритмы.