Сортировка выбором (selection sort) в Python
В этом уроке вы реализуете сортировку выбором, каждый раз находя наименьший элемент и ставя его на нужное место.
Введение
Какую задачу это решает
Некоторые алгоритмы сортировки стараются делать как можно меньше перемещений, что важно, когда перемещение элемента дорого. Сортировка выбором показывает стратегию, отличную от пузырьковой: сначала найти нужный элемент, потом переместить его один раз.
Пример из жизни
Сортировка выбором похожа на набор команды по росту. Вы осматриваете всех, кто ещё ждёт, вызываете самого низкого и ставите его на следующее место в ряду. Потом снова осматриваете остальных в поисках следующего самого низкого, пока никого не останется.
for start in range(len(result)):📍 Следующее свободное место в рядуminimum = start🤔 Считать этого человека самым низкимresult[index] < result[minimum]🔎 Поискать среди остальных кого-то нижеresult[start], result[minimum] = ...🔄 Поставить самого низкого на свободное местоСортировка выбором многократно находит наименьший элемент в неотсортированной части списка и меняет его на следующую позицию отсортированной части; это O(n²) сравнений, но не больше n - 1 обменов.
Главное
- Всё слева от
startуже отсортировано; всё начиная сstart- нет. minimumпомнит индекс наименьшего значения, найденного пока в неотсортированной части.- Внутренний цикл
for index in range(start + 1, len(result)):просматривает остаток списка. result[start], result[minimum] = result[minimum], result[start]делает один обмен на позицию.
Когда это нужно?
- Изучение и сравнение стратегий сортировки.
- Ситуации, где запись или перемещение элементов дороги, а сравнения дёшевы.
- Поиск k наименьших элементов с остановкой после k проходов.
Когда это не нужно
- Настоящие программы:
sorted()гораздо быстрее. - Почти отсортированные данные: сортировка выбором всё равно просматривает всё, а сортировка вставками заканчивает быстро.
Визуализация: Сортировка выбором (selection sort) в Python
O(n²)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Обмен внутри внутреннего цикла
Это превращает её в более медленную и запутанную сортировку с множеством обменов.
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]
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Минимум в массиве Найдите наименьшее значение в списке. Легко
- K-th Smallest Element Find the k-th smallest value without fully sorting. Средне