Идея алгоритма проста:
- Находим минимальный элемент в массиве.
- Меняем его местами с первым элементом.
- Повторяем то же самое для оставшегося подмассива (без первого элемента).
В результате минимальные элементы постепенно «выстраиваются» в начале массива, и весь список оказывается отсортирован.
Рекурсивная версия
def min_value_idx(arr):
"""Возвращает индекс минимального элемента массива"""
result = 0
for i in range(1, len(arr)):
if arr[i] < arr[result]:
result = i
return result
def choice_sort(arr):
"""Сортировка выбором (рекурсивная версия)"""
if len(arr) > 1:
idx = min_value_idx(arr)
# Меняем местами первый элемент и минимальный
arr[0], arr[idx] = arr[idx], arr[0]
# Рекурсивный вызов для хвоста массива
choice_sort(arr[1:])
# Проверка
A = [5, 3, 6, 2, 1, 4]
choice_sort(A)
print(A) # [1, 2, 3, 4, 5, 6]Важно: увидеть как работает рекурсия — мы выделили минимальный элемент, поставили его в начало и повторили процесс для оставшегося массива.
Итеративная версия
Чтобы сделать алгоритм более наглядным и практичным, перепишем его в виде цикла:
def choice_sort_iter(arr):
"""Сортировка выбором (итеративная версия)"""
n = len(arr)
for start in range(n - 1):
# Находим индекс минимального элемента в подмассиве
min_idx = start
for i in range(start + 1, n):
if arr[i] < arr[min_idx]:
min_idx = i
# Меняем элементы только если это действительно нужно
if start != min_idx:
arr[start], arr[min_idx] = arr[min_idx], arr[start]
# Проверка
B = [7, 2, 9, 1, 5, 3]
choice_sort_iter(B)
print(B) # [1, 2, 3, 5, 7, 9]Сложность
Хотя в рекурсивной версии нет циклов внутри функции, важно понимать:
- на каждом шаге мы ищем минимальный элемент (это O(n)),
- и таких шагов n.
В сумме получаем сложность O(n²).
Поэтому сортировка выбором относится к квадратичным сортировкам.