Сортировка выбором

Сортировка выбором (Selection Sort): идея поиска минимума, пошаговый разбор, код на Python, сложность O(n²) и отличие от пузырьковой.

Сортировка выбором делит массив на две части: отсортированную (слева) и неотсортированную (справа). На каждом шаге она находит минимальный элемент в правой части и ставит его в конец левой.

Сложность: O(n²) во всех случаях; O(n) памяти — in-place.

Идея алгоритма

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

Пошаговый разбор

Массив [29, 10, 14, 37, 13]:

Проход	Минимум найден	Ставим на позицию	Массив
1	10 (индекс 1)	0	[10, 29, 14, 37, 13]
2	13 (индекс 4)	1	[10, 13, 14, 37, 29]
3	14 (индекс 2)	2	[10, 13, 14, 37, 29]
4	29 (индекс 4)	3	[10, 13, 14, 29, 37]

После 4 проходов (n−1) массив отсортирован.

Код

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):        # ищем минимум в правой части
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]   # обмен
    return arr

data = [29, 10, 14, 37, 13]
print(selection_sort(data))

Вывод:

[10, 13, 14, 29, 37]

Сложность и свойства

Случай	Сравнений	Перестановок
Лучший	O(n²)	O(n)
Средний	O(n²)	O(n)
Худший	O(n²)	O(n)

Память: O(1) — in-place. Алгоритм неустойчивый: при перестановке равные элементы могут поменяться местами.

Ключевое преимущество перед пузырьковой: selection sort делает не более n−1 перестановок. Это важно, когда сама перестановка дорогостоящая операция (например, большие объекты на диске).

Когда применять

Как и пузырьковая, сортировка выбором эффективна только для очень маленьких массивов. Её главное достоинство — минимальное число физических перестановок. В остальных случаях выбирают более быстрые алгоритмы.

Коротко

Selection sort на каждом шаге находит минимальный элемент в неотсортированной части и ставит его на нужное место.
Сложность O(n²) во всех случаях, но перестановок всего O(n).
In-place (O(1) памяти), неустойчивый.
Применяется редко — только для маленьких массивов или когда перестановка дорогостоящая.