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

Сортировка выбором: как расставить книги по росту

Два года назад я решил расставить книги на полке по высоте — от самой низкой к самой высокой. Без плана: просто брал самую низкую книгу из всей кучи и ставил первой. Потом искал следующую самую низкую среди оставшихся и ставил следом. Повторял, пока куча не закончилась. Это и есть сортировка выбором. Никакой сложной математики — вы уже выполнили этот алгоритм в реальной жизни.

Как работает сортировка выбором

Алгоритм делит массив на две части: отсортированную в начале и неотсортированную в конце. На каждом проходе он просматривает всю неотсортированную часть, находит минимальный элемент и меняет его местами с первым элементом неотсортированной части.

Разберём пошагово на массиве [29, 10, 14, 37, 13]:

• Проход 1: просматриваем весь массив, находим 10, меняем с 29. Массив: [10, 29, 14, 37, 13].
• Проход 2: просматриваем с индекса 1, находим 13, меняем с 29. Массив: [10, 13, 14, 37, 29].
• Проход 3: просматриваем с индекса 2, 14 уже минимальное, обмен не нужен.
• Проход 4: просматриваем с индекса 3, находим 29, меняем с 37. Массив: [10, 13, 14, 29, 37].

Пять элементов — четыре прохода. Для n элементов сортировка выбором всегда выполняет n-1 проходов.

Реализация на Python

def selection_sort(arr):
    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([29, 10, 14, 37, 13]))  # [10, 13, 14, 29, 37]

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

Почему сортировка выбором всегда медленная

В отличие от пузырьковой сортировки, которая на уже отсортированном массиве может завершиться быстро, сортировка выбором не имеет таких оптимизаций. Даже если массив уже отсортирован, алгоритм всё равно просматривает всю неотсортированную часть на каждом проходе, чтобы убедиться, что найден минимальный элемент.

Временная сложность в лучшем, среднем и худшем случае — O(n²). Количество сравнений всегда равно n(n-1)/2. Для массива из 10 000 элементов потребуется около 50 миллионов сравнений независимо от начального порядка.

Где сортировка выбором действительно выигрывает

Алгоритм проигрывает по скорости, но выигрывает по количеству записей. Он выполняет не более n-1 обменов — всегда ровно один обмен за проход. Пузырьковая сортировка и сортировка вставками могут делать гораздо больше обменов на тех же данных.

Это важно там, где запись данных дороже чтения. Flash-память имеет ограниченное количество циклов записи, а встраиваемые системы часто работают с жёсткими ограничениями по памяти. В таких средах предсказуемый алгоритм с малым числом обменов может быть разумным выбором, несмотря на медленные сравнения.

В остальных случаях сортировка выбором используется в основном в обучении и на собеседованиях как ступенька к более быстрым алгоритмам вроде сортировки слиянием или быстрой сортировки.

Проблема устойчивости

Устойчивая сортировка сохраняет относительный порядок равных элементов. Сортировка выбором не гарантирует этого, потому что обмен может переставить равные элементы.

Пример: массив [4a, 4b, 3], где 4a и 4b равны, но отслеживают исходный порядок. Сортировка выбором находит 3 как минимальный и меняет его с 4a. Массив становится [3, 4b, 4a]. Теперь 4b стоит перед 4a — порядок нарушен.

Если вам нужно сортировать данные, где важен порядок среди равных (например, студентов с одинаковыми баллами), используйте сортировку слиянием или вставками.

Сравнение с ближайшими родственниками

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

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

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

Часто задаваемые вопросы

• Что такое сортировка выбором простыми словами? Это метод сортировки, который многократно находит минимальный оставшийся элемент и перемещает его в начало списка.
• Какова временная сложность сортировки выбором? O(n²) в лучшем, среднем и худшем случае, так как она всегда просматривает всю неотсортированную часть на каждом проходе.
• Устойчива ли сортировка выбором? Нет. Обмен может нарушить относительный порядок равных элементов.
• Является ли сортировка выбором сортировкой на месте? Да. Она сортирует в исходном массиве, используя O(1) дополнительной памяти.
• Сколько обменов выполняет сортировка выбором? Не более n-1, что меньше, чем у пузырьковой сортировки или сортировки вставками на тех же данных.
• Когда стоит использовать сортировку выбором? Для небольших наборов данных, в учебных целях, на собеседованиях или в средах, где запись дорога (например, flash-память).

Практический вывод

Откройте редактор и реализуйте сортировку выбором самостоятельно. Затем сравните её с пузырьковой сортировкой на случайном массиве из 1000 чисел — замерьте время. Вы увидите разницу. А после попробуйте оптимизировать: например, на каждом проходе искать одновременно минимум и максимум, чтобы сократить число проходов вдвое. Удачи!