Алгоритмы на Python

Сортировка выбором (selection sort) в Python

В этом уроке вы реализуете сортировку выбором, каждый раз находя наименьший элемент и ставя его на нужное место.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Некоторые алгоритмы сортировки стараются делать как можно меньше перемещений, что важно, когда перемещение элемента дорого. Сортировка выбором показывает стратегию, отличную от пузырьковой: сначала найти нужный элемент, потом переместить его один раз.

Пример из жизни

Сортировка выбором похожа на набор команды по росту. Вы осматриваете всех, кто ещё ждёт, вызываете самого низкого и ставите его на следующее место в ряду. Потом снова осматриваете остальных в поисках следующего самого низкого, пока никого не останется.

От набора команды к коду
for start in range(len(result)):📍 Следующее свободное место в ряду
minimum = start🤔 Считать этого человека самым низким
result[index] < result[minimum]🔎 Поискать среди остальных кого-то ниже
result[start], result[minimum] = ...🔄 Поставить самого низкого на свободное место
Один обмен на позицию после просмотра всей неотсортированной части.
Одним предложением

Сортировка выбором многократно находит наименьший элемент в неотсортированной части списка и меняет его на следующую позицию отсортированной части; это O(n²) сравнений, но не больше n - 1 обменов.

Главное

  1. Всё слева от start уже отсортировано; всё начиная с start - нет.
  2. minimum помнит индекс наименьшего значения, найденного пока в неотсортированной части.
  3. Внутренний цикл for index in range(start + 1, len(result)): просматривает остаток списка.
  4. result[start], result[minimum] = result[minimum], result[start] делает один обмен на позицию.

Когда это нужно?

  • Изучение и сравнение стратегий сортировки.
  • Ситуации, где запись или перемещение элементов дороги, а сравнения дёшевы.
  • Поиск k наименьших элементов с остановкой после k проходов.

Когда это не нужно

  • Настоящие программы: sorted() гораздо быстрее.
  • Почти отсортированные данные: сортировка выбором всё равно просматривает всё, а сортировка вставками заканчивает быстро.

Визуализация: Сортировка выбором (selection sort) в Python

O(n²)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
def selection_sort(values):
    result = values.copy()
    for start in range(len(result)):
        minimum = start
        for index in range(start + 1, len(result)):
            if result[index] < result[minimum]:
                minimum = index
        result[start], result[minimum] = result[minimum], result[start]
    return result

print(selection_sort([64, 25, 12, 22, 11]))
Получить кнопку запуска для этого примера

Результат выполнения

[11, 12, 22, 25, 64]

Разбор кода

Переменная minimum запоминает позицию наименьшего значения в оставшейся части списка. В конце каждого прохода это значение меняется местами с элементом на позиции start. Из-за большого числа сравнений сложность всегда O(n²), зато обменов не больше n.

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Обмен внутри внутреннего цикла

Это превращает её в более медленную и запутанную сортировку с множеством обменов.

Ошибка
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
Исправление
for index in range(start + 1, len(result)):
    if result[index] < result[minimum]:
        minimum = index
result[start], result[minimum] = result[minimum], result[start]

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи