Сортировка выбором: как работает, сложность и код на Python

Коротко

Особенность алгоритма: сложность не зависит от входных данных вообще. Отсортированный массив, случайный или перевёрнутый — всегда одно и то же число сравнений.

Идея

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

Аналогия — вы раскладываете книги по высоте. Просматриваете всю стопку, находите самую низкую, ставите первой. Потом просматриваете оставшиеся, находите самую низкую среди них, ставите второй. И так далее.

Разберём [64, 25, 12, 22, 11]:

шаг 1: минимум среди всех = 11  → меняем с 64
       [11 | 25, 12, 22, 64]
шаг 2: минимум среди [25,12,22,64] = 12 → меняем с 25
       [11, 12 | 25, 22, 64]
шаг 3: минимум среди [25,22,64] = 22 → меняем с 25
       [11, 12, 22 | 25, 64]
шаг 4: минимум среди [25,64] = 25 → уже на месте
       [11, 12, 22, 25 | 64]
готово: [11, 12, 22, 25, 64]

Обратите внимание: обменов было всего три, хотя сравнений — десять.

Код на Python

def selection_sort(arr: list[int]) -> list[int]:
    n = len(arr)

    for i in range(n - 1):          # последний элемент встанет сам
        min_index = i

        # ищем минимум в неотсортированной части
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # меняем местами, только если нашли что-то меньше
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr


print(selection_sort([64, 25, 12, 22, 11]))  # [11, 12, 22, 25, 64]

Два момента, которые отличают аккуратную реализацию от небрежной.

Внешний цикл идёт до n - 1, а не до n. Когда все элементы кроме последнего расставлены, последний автоматически оказывается максимальным. Лишняя итерация ничего не изменит.

Мы запоминаем индекс минимума, а не меняем местами на каждом сравнении. Именно это даёт всего O(n) обменов вместо O(n²).

То же на JavaScript

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

Почему сложность всегда одинакова

Внешний цикл делает n−1 итераций. Внутренний на i-м шаге просматривает n−i−1 элементов. Суммарно:

(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 ≈ n²/2

Здесь нет ни одного условия, которое могло бы прервать поиск досрочно — минимум в неотсортированной части нельзя найти, не просмотрев её целиком. Поэтому лучший, средний и худший случаи совпадают: O(n²).

Это отличает её от сортировки вставками и пузырьковой, которые на отсортированных данных ускоряются до O(n).

Единственное преимущество: мало обменов

Обменов ровно n−1 в худшем случае — по одному на итерацию внешнего цикла. Для сравнения, пузырьковая сортировка в худшем случае делает O(n²) обменов.

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

Во всех остальных случаях сортировка вставками лучше при той же асимптотике.

Почему она неустойчива

Обмен переставляет элементы через весь массив, и равные элементы могут поменяться местами. Пример:

[3a, 3b, 1]
шаг 1: минимум = 1, меняем с первым элементом
[1, 3b, 3a]   ← 3a и 3b поменялись порядком

Исходный относительный порядок двух троек нарушен. Это можно исправить, заменив обмен на сдвиг, — но тогда мы фактически получим сортировку вставками и потеряем единственное преимущество в виде малого числа записей.

Сравнение с соседями

Вывод для практики: сортировка выбором проигрывает вставкам почти везде. Её ценность в первую очередь учебная — она проще всех для понимания и хорошо показывает идею разделения массива на отсортированную и неотсортированную части.

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

Обмен внутри внутреннего цикла. Если менять элементы местами при каждом найденном меньшем значении, алгоритм всё равно отсортирует массив, но обменов станет O(n²) — исчезнет единственное преимущество.

Внутренний цикл с i вместо i + 1. Сравнивать элемент сам с собой бессмысленно, но не смертельно; а вот начать с нуля — значит каждый раз просматривать уже отсортированную часть и потерять смысл алгоритма.

Поиск максимума вместо минимума при сортировке по возрастанию. Работать будет, если ставить максимум в конец, но новички часто путают направление и получают массив, отсортированный наоборот.

Что запомнить

• На каждом шаге ищем минимум в неотсортированной части и ставим его в начало.
• O(n²) всегда — досрочно выйти невозможно, минимум нужно искать целиком.
• Делает минимум обменов: O(n). Это единственное её реальное преимущество.
• Неустойчива из-за обменов через весь массив.
• На практике почти всегда стоит предпочесть сортировку вставками.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→