Как сравнивать пузырьковую сортировку, выбор и вставки?

Квадратичные сортировки выполняют порядка n² сравнений или перемещений в неблагоприятном случае, но устроены по-разному. Их полезно изучать через инвариант и тип входа: один метод постепенно ставит максимумы в конец, другой выбирает минимум, третий поддерживает отсортированный префикс.

Пузырьковый проход

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

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

На шаге i алгоритм ищет минимум суффикса и ставит его в позицию i. Число сравнений почти не зависит от исходного порядка, зато обменов обычно не больше n. Метод удобен, когда запись дороже сравнения, но классическая реализация не гарантирует стабильность.

Сортировка вставками

Очередной элемент вставляется в подходящее место отсортированного префикса, сдвигая большие значения вправо. Почти отсортированный массив обрабатывается быстро, потому что сдвигов мало. На обратном порядке возникает максимальное число перемещений.

Стабильность

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

Сравнительный эксперимент

Возьмите упорядоченный, обратный и случайный массивы одинаковой длины. Посчитайте отдельно сравнения и записи для трёх алгоритмов. Затем объясните результат через инварианты, а не только через время запуска: такой анализ показывает, какая операция формирует стоимость на конкретном типе входа.

Сравнение по данным, а не только по формуле O(n²)

Сортировка вставками поддерживает отсортированный префикс и хорошо работает на почти упорядоченных данных. Выбор делает мало обменов, но всегда ищет минимум в остатке. Пузырьковая сортировка перемещает крупные элементы вправо соседними обменами; флаг отсутствия обменов позволяет рано завершить уже отсортированный вход.

def insertion_sort(values: list[int]) -> list[int]:
    result = values.copy()
    for index in range(1, len(result)):
        current = result[index]
        position = index
        while position > 0 and result[position - 1] > current:
            result[position] = result[position - 1]
            position -= 1
        result[position] = current
    return result

assert insertion_sort([4, 2, 2, 1]) == [1, 2, 2, 4]

Строгое сравнение > сохраняет порядок равных элементов и делает реализацию стабильной. Замена на >= изменит это свойство, хотя числа останутся отсортированы.

Практика: лаборатория сравнений и обменов

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