Асимптотика на практике: Сравнение алгоритма сортировки вставками и выбором
Асимптотика на практике: Сравнение алгоритма сортировки вставками и выборомАвтор: Шуравин Александр, к. т. н., доцент, в 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)Идея: На каждой итерации находим минимальный элемент в неотсортированной части массива и меняем его с первым элементом этой части. Читать далее