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

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

Автор: Шуравин Александр, к. т. н., доцент, в 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)

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