Сортировка выбором (Selection sort): как работает, код и анализ

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

Короткое определение

Сортировка выбором — алгоритм in-place с последовательным отбором максимального или минимального элемента для постановки его в нужную позицию. Определение сложности: O(n²) по времени, O(1) по дополнительной памяти.

Пошаговый пример

Начнём с массива:

[39, 82, 2, 51, 30, 42, 7]

1. Ищем наибольшее значение во всём массиве — это 82. Меняем 82 с элементом на последнем индексе (7).
2. После первой проходки массив становится: [39, 7, 2, 51, 30, 42, 82]. Теперь правая часть длиной 1 отсортирована.
3. Во второй проходке ищем наибольшее в неотсортированной части [39, 7, 2, 51, 30, 42] — это 51. Меняем 51 и элемент на позиции перед последним (42): [39, 7, 2, 42, 30, 51, 82].
4. Повторяем процесс до тех пор, пока не останется неотсортированных элементов.

Кажный полный обход массива называется «проход» (pass). В результате на каждом шаге растёт правая (или левая, в зависимости от реализации) отсортованная часть.

Важные свойства алгоритма

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

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

Анализ сложности (вывод O(n²))

На первом проходе алгоритм делает (n-1) сравнений, на втором — (n-2), и так далее, до 1 сравнения на предпоследнем проходе. В сумме это:

(n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n²)

Таким образом, количество сравнений растёт квадратично с размером входа.

Реализация — примеры кода

Ниже — две типичные реализации: на Python и Java. Комментарии переведены на русский для понятности.

Python

def selectionSort(mylist):
    # проходы: от конца к началу
    for x in range(len(mylist) - 1, 0, -1):
        max_idx = 0
        # ищем индекс максимального в подмассиве [0..x]
        for posn in range(1, x + 1):
            if mylist[posn] > mylist[max_idx]:
                max_idx = posn
        # меняем найденный максимум с элементом в позиции x
        temp = mylist[x]
        mylist[x] = mylist[max_idx]
        mylist[max_idx] = temp

Java

void selectionSort(int my_array[]) {
    // проходим справа налево: на каждой итерации ставим минимальный элемент на позицию x
    for (int x = 0; x < my_array.length - 1; x++) {
        int index = x;
        // ищем наименьший элемент в правой части
        for (int y = x + 1; y < my_array.length; y++){
            if (my_array[y] < my_array[index]){
                index = y; // найден новый минимальный индекс
            }
        }
        // меняем местами
        int temp = my_array[index];
        my_array[index] = my_array[x];
        my_array[x] = temp;
    }
}

Примечание: в примерах одна реализация ставит максимум в конец, другая — минимум в начало; обе семантически эквивалентны и дают отсортированный результат.

Когда использовать, а когда избегать

Когда подходит:

• Небольшие массивы (до сотен элементов) или образовательные цели.
• Когда нужно реализовать простое in-place решение без дополнительной памяти.

Когда не подходит:

• Большие данные или строгие требования к производительности.
• Когда важна стабильность сортировки (если требуется сохранить порядок равных элементов).

Альтернативы:

• Merge sort: стабильный, O(n log n), требует O(n) дополнительной памяти.
• Quicksort: в среднем O(n log n), in-place, но в худшем O(n²) (можно уменьшить риск с рандомизацией и хорошим выбором опорного элемента).
• Heapsort: O(n log n), in-place, но нестабильный.

Ментальная модель и эвристика

Ментальная модель: представьте, что вы сортируете карты в руке, каждый раз берёте самую большую карту и кладёте её в конец. Эвристика для выбора: если массив почти отсортирован, рассмотрите insertion sort; если данные большие — merge или quicksort.

Критерии приёмки

• Алгоритм корректно сортирует все входы длиной 0..N.
• Работает in-place (не создаёт массивы размером O(n)).
• Количество сравнений для размера n близко к n(n-1)/2 (проверка корректности реализаций).

Тестовые случаи для проверки

1. Пустой массив -> []
2. Один элемент -> [x]
3. Уже отсортированный (возрастающий) массив
4. Обратно отсортированный массив
5. Массив с повторяющимися элементами -> проверка стабильности (ожидается: порядок равных элементов может измениться)
6. Большой случайный массив -> совпадение с эталонной сортировкой

Сравнение с другими алгоритмами (кратко)

• Простота: Selection < Insertion < Merge/Quick
• Память: Selection, Quick, Heap — in-place; Merge требует O(n)
• Стабильность: Merge и Insertion стабильны; Selection и Heap — нет
• Производительность на больших данных: Merge/Quick > Insertion > Selection

Факт-бокс

• Тип: in-place, сравнивающий алгоритм
• Временная сложность: O(n²)
• Доп. память: O(1)
• Стабильность: нет

Важно: классическая сортировка выбором не пригодна для больших датасетов в продакшне — используйте O(n log n) алгоритмы.

Краткое резюме

Сортировка выбором — хороший учебный пример алгоритмической идеи «выбора экстремума» и полезна для понимания основных понятий сортировки. Для реальных задач с большими объёмами данных предпочтительнее использовать merge sort, quicksort или готовые библиотечные реализации.

Ключевые действия: понять инвариант (отсортованная + неотсортованная части), посчитать сложность и протестировать на крайних случаях.