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

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

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

Введение

В теории алгоритмов мы привыкли оперировать абстракциями: O(n²), O(n log n), O(1). Но что скрывается за этими обозначениями в реальном продакшене? Насколько критичен выбор алгоритма для вашей системы?

В этой статье я исследую два классических алгоритма сортировки — сортировку выбором (Selection Sort) и сортировку вставками (Insertion Sort) — на трёх типах входных данных:

1. Случайный массив.

2. Уже отсортированный массив (best case).

3. Массив, отсортированный в обратном порядке (worst case).

 Эксперимент проведён на Python с замером времени выполнения для размеров массива от 100 до 1000 с шагом 100.

Теоретическая справка

Сортировка выбором (Selection Sort)

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

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

Сложность: Всегда O(n²) сравнений, независимо от состояния данных. Количество обменов — O(n) (не более n−1 перестановок).

Особенность: Предсказуемое время выполнения. Это одновременно и достоинство (для 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

— Размеры массива: 100, 200, 300, …, 1000

— Типы данных:

— Случайные (random.randint)

— Отсортированные (sorted)

— Обратно отсортированные (reverse=True)

— Количество замеров: 100 прогонов для каждого размера, взято среднее и для сравнения к графику добавлено +/- среднеквадратичное отклонение.

 

Гипотезы

1. Selection Sort: Время будет расти строго квадратично на всех типах данных.

2. Insertion Sort:

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

   — На отсортированных — линейное время.

   — На обратно-отсортированных — максимально медленное, близкое к Selection Sort.

 

Результаты

 

График 1: Случайные данные

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

Наблюдения:

– Оба алгоритма демонстрируют параболический рост — это соответствует теоретической сложности 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), а в интерпретируемых языках операции записи намного дороже сравнений. Данный эксперимент наглядно демонстрирует, почему инженер должен проверять теорию на практике и учитывать особенности языка и среды выполнения при выборе алгоритмов.

График 2: Отсортированный массив (Best Case)

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

 

 

 Наблюдения:

— 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 на финальных этапах.

 

График 3: Обратно отсортированный массив (Worst Case)

 

 Наблюдения:

— Оба алгоритма показывают почти идентичную квадратичную кривую.

— Insertion Sort в этом случае работает так же медленно, как Selection Sort, потому что каждый элемент сдвигается на максимальное расстояние.

— Время выполнения на n=1000 — ~0.025 сек для метода выбора и ~0.05 для метода вставки (так показал себя же так же хуже, чем Selection Sort)

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

 Ключевые инсайты

* Практика противоречит теории.

 

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

 1. Выбор алгоритма зависит от данных

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

 — Почти отсортированные (например, логи событий): Insertion Sort будет работать как O(n) — берите её.

— Полностью случайные и большие 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 книги Стивена Скиены «Алгоритмы. Руководство по разработке»:

 1. Сортировка выбором — предсказуема.

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

 Эксперимент не подтвердил следующие утверждения:

1. Сортировка вставкой в целом немного быстрее на случайных данных – эксперимент показал обратное.

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