Асимптотика на практике: Сравнение алгоритма сортировки вставками и выбором / Habr

Автор: Шуравин Александр, к. т. н., доцент, в IT более 20 лет.

Принято считать, что при определении временной сложности алгоритма константы не имеют значения. В теории алгоритмов мы оперируем так называемыми Big O, абстракциями типа O(n²), O(n log n), O(1). Но какие подводные камни кроются за ними продакшене? Насколько на самом деле критичны константы. И как это зависит от входных данных. Чтобы ответить на этот вопрос, были исследованы два классических алгоритма сортировки: сортировку выбором (Selection Sort) и сортировка вставками (Insertion Sort). Эти алгоритмы были проверены на трех типах данных: случайный массив, уже отсортированный массив (best case) и массив, отсортированный в обратном порядке (worst case). В качестве языка программирования для проведения эксперимента был выбран Python. Замеры производительности выполнялись для массива длиной от 100 до 1000 с шагом 100.

Сортировка выбором (Selection Sort). Идея состоит в том, что мы ищем минимальный элемент в массиве, затем ставим его на первое место. Затем, начиная со второго места, ищем следующий минимальный элемент и ставим его сразу за первым. Точно так же поступаем с третьим элементом, и так до конца массива. Получается цикл в цикле, классический O(n²) сравнений, константа 1/2. Вот исходный код этого алгоритма:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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

Временная сложность в данном алгоритме не зависит от данных, поэтому время его выполнения предсказуемое. Это одновременно и достоинство и недостаток. Достоинство потому что в real-time системах нам важно предсказуемое время выполнения. Недостаток - будет медленно работать на больших объемах данных.

Сортировка вставками (Insertion Sort). Этот алгоритм работает так: проходим по массиву и новые элементы вставляем в уже отсортированную часть в нужное место. Большие элементы при этом сдвигаются вправо. Вот классическая реализация этого алгоритма

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Здесь временная сложность уже зависит от данных:

Best case (когда список уже отсортирован): O(n) — одно сравнение за итерацию.
Average case: O(n²) — в среднем половина элементов сдвигается.
Worst case (обратный порядок): O(n²) — каждый элемент сдвигается на всю длину отсортированной части.

Технические сведения: эксперимент проводился на языке программирования Python 3.10 в IDE Visual Studio Code Version: 1.128.1; Размеры массива от 100 до 1000 включительно с шагом 100; типы данных: случайные (random.randint); отсортированные; обратно отсортированные; в качестве времени выполнения было взято среднее по 100 замерам. Для наглядности на графике отображено +/- среднеквадратичное отклонение.

Гипотезы исследования

Selection Sort: Время будет расти строго квадратично на всех типах данных.
Insertion Sort: На случайных данных — близко к квадратичному, но с меньшей константой, чем при Selection Sort; на отсортированных — линейное время; на обратно-отсортированных — максимально медленное, близкое к Selection Sort.

Полученные результаты

Случайные данные. Ниже представлены два графика зависимости скорости сортировки от количества элементов массива.

Рисунок 1 – зависимость времени выполнения сортировки методом вставки от количества элементов массива

Рисунок 2 – зависимость времени выполнения сортировки методом выбора от количества элементов массива

Глядя на эти графики, мы можем заметить следюущее:

Оба алгоритма демонстрируют параболический рост, что соответствует теории — сложность O(n²) для обоих алгоритмов.
Неожиданный результат: вопреки теории, Selection Sort оказался быстрее Insertion Sort на случайных данных во всех замерах (примерно на 30-40%).
При n=1000: Selection Sort ~0.018 сек, Insertion Sort ~0.025 сек.
Разница растёт с увеличением n, что указывает на систематическую причину, а не случайный разброс.

Вывод: На случайных данных в Python Selection Sort работает быстрее Insertion Sort, несмотря на теоретические ожидания. Это объясняется тем, что Insertion Sort выполняет значительно больше операций записи в память (~n²/4 против ~n у Selection Sort), а в интерпретируемых языках операции записи намного дороже сравнений. Данный эксперимент наглядно демонстрирует, почему инженер должен проверять теорию на практике и учитывать особенности языка и среды выполнения при выборе алгоритмов.

Отсортированный массив (Best Case). Теперь посмотрим графики зависимости скорости сортировки от количества элементов массива при заранее отсортированном массиве. Для Сортировки вставкой представлено два графика, на втором (рисунок 4) взято больше размеров, чтобы была видна линейность.

Рисунок 3 – зависимость времени выполнения сортировки методом вставки от количества элементов массива

Рисунок 4 – зависимость времени выполнения сортировки методом вставки от количества элементов массива (взято больше размеров, чтобы показать линейность графика)

Рисунок 5 – зависимость времени выполнения сортировки методом выбора от количества элементов массива

Вот что можно увидеть на данных иллюстрациях:

Selection Sort всё так же квадратична — 0.017 сек при n=1000.
Insertion Sort показывает линейный рост — всего 0.002 сек при n=20000.
На n=1000 (1.31E-05) разница в 1300 раз!

Вывод: Если ваши данные часто бывают почти отсортированными (логи, временные ряды, добавления в конец), Insertion Sort — идеальный выбор. Это причина, почему TimSort (стандарт в Python и Java) использует Insertion Sort на финальных этапах.

Обратно отсортированный массив (Worst Case). Теперь посмотрим на рисунки 6 и 7. Здесь мы видим две параболические кривые (то есть, при обратной сортировке оба алгоритма выполняются за O(n²) сравнений.

Рисунок 6 – зависимость времени выполнения сортировки методом вставки от количества элементов массива

Рисунок 7 – зависимость времени выполнения сортировки методом выбора от количества элементов массива

Наблюдения (что мы видим на данных скринах(:

Оба алгоритма показывают почти идентичную квадратичную кривую.
Insertion Sort тоже работает медленно, как и Selection Sort. Это объясняется тем, что п все элементы сдвигается на максимальное расстояние.
Insertion Sort и тут показал себя хуже, чем Selection Sort, его время выполнения на массиве из 1000 элементов ~0.05, а Selection Sort выполнился за ~0.025 сек.

Вывод: Когда массивы отсортированы в обратном порядке, оба алгоритма работаю одинаково плохо. В таком случае нужно использовать QuickSort или MergeSortЭто — классический сценарий.

Итоги. Сведем наши наблюдения в таблицу. Знаком * отмечены наблюдения, где практика противоречит теории

Сценарий	Selection Sort	Insertion Sort	Победитель
Случайные данные	Медленно	Медленнее на 30-40%	Selection Sort*
Отсортированные	Медленно (квадрат)	Мгновенно (линейно)	Insertion Sort
Обратный порядок	Медленно	Медленно	Selection Sort*

Практические выводы для разработчика

1. Выбор алгоритма зависит от данных. Никогда не выбирайте алгоритм в вакууме. Профилируйте свои данные:

Почти отсортированные (например, логи событий): Insertion Sort будет работать как O(n) — берите её.
Полностью случайные и большие массивы с числом элементов большем 1000. Для них не подходит ни одна из этих сортировок. Применяйте TimSort (встроенная sort() в Python) или QuickSort.
Real-time системы с ограниченным лимитом времени. Selection Sort даёт предсказуемое время. Insertion Sort может внезапно замедлиться на “плохих” данных.

2. Константы иногда имеют значение. На маленьких массивах (n < 100) даже O(n²) алгоритм может работать быстрее чем алгоритм с временной сложностью O(n log n). Почему? Из-за низкой константы. Это отлично видно на графиках: при n=100 оба алгоритма выполняются менее, чем за 0.001 сек. Тами образом, можно сформулировать золотое правило: Для n < 50 используйте Insertion Sort, для n > 1000 — переходите на сортировки слиянием или быструю сортировку.

3. Учитесь читать асимптотику на графиках

Квадратичный рост — это когда увеличение n в 2 раза даёт рост времени в ~4 раза.
Линейный рост (у Insertion Sort на отсортированных данных) — это когда время растёт прямо пропорционально n.
Приведенные выше графики это хорошо иллюстрируют: кривые Selection Sort всегда параболические, а Insertion Sort на отсортированных данных — прямая линия.

Заключение

Эксперимент подтвердил теоретические выкладки из главы 2 книги Стивена Скиены "Алгоритмы. Руководство по разработке":

Сортировка выбором — предсказуема.
Сортировка вставками — адаптивна: быстра на почти отсортированных данных, но так же плоха на обратных.

Эксперимент не подтвердил, что сортировка вставкой в целом немного быстрее на случайных данных – эксперимент показал обратное. Нужно сказать, что для Senior-разработчика эти эксперименты — не просто упражнения. Они формируют мышление, которое позволяет за 30 секунд оценить задачу: "Подходит ли здесь простой O(n²) алгоритм или нужно что-то серьёзнее?".

Дополнение

По просьбам читателей добавил совмещенные графики: сравнение алгоритма методов выбора и вставки для случайных данных (верхний рисунок) и для почти отсортированного массива (строгий порядок чисел, но в некоторые места случайно вставлены случайные числа):

ls=[random.randint(1, items_count) if random.randint(1, 10)==2 else x for x in range(items_count)]