Зарождение компьютеров, активное развитие точных наук, появление дисциплин на стыке направлений потребовали создания принципов работы с данными, в том числе способов упорядочивания. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают один из базовых методов группировки, производимый через вставки.
С древних времён человечество имеет дело с данными. В Античности люди классифицировали богов и элементы природы, в Средние века углублялись в религию и сословия. Середина ХХ века создала инструменты для использования двоичной системы и задала требования к цифровой информации. На таком фоне получила развитие теория алгоритмов.
Одним из простейших алгоритмов стала сортировка вставками. Идея – сравнивать каждый новый элемент массива с предыдущими, пока выполняется условие: значение больше или меньше соседнего. Как только предпосылка нарушается, место для изучаемого числа найдено.
Рассмотрим на примере. Возьмём массив из восьми составляющих [17, 15, 51, 19, 50, 85, 49, 46]. Выстроим части в лесенку «по росту».
Элемент на позиции 0 считаем уже отсортированным, поэтому работу начинаем с первого места.
Сравниваем текущий элемент с предшествующим.
Число 15 меньше, чем 17. Поэтому меняем значения местами: 15 становится на позицию 0, а 17 – на 1. Метод переходит к следующей паре: 51 и 17.
Поскольку 51 больше, порядок сохраняется. Двигаемся дальше.
19 должно встать туда, где находится 51. Но перед последним элементом есть предшествующий. Значит, сравнить придётся и с ним – только так убедимся в верности позиционирования. После проверки берём следующую пару.
Здесь происходит аналогичное двойное сравнение. А число 85 остаётся на месте как самое большое из представленных.
Здесь происходит аналогичное двойное сравнение. А число 85 остаётся на месте как самое большое из представленных…
А заключительный атом будет сравниваться уже с пятью составляющими массива.
Таким образом, массив из 8 элементов [17, 15, 51, 19, 50, 85, 49, 46] отсортирован по возрастанию: [15, 17, 19, 46, 49, 50, 51, 85]. Задача решена.
Скорость метода имеет квадратичную зависимость:
T = O(n2),
где T – время работы, n – число элементов.
Алгоритм работает с исходным массивом на месте и в моменте, поэтому хватает одной постоянной ячейки памяти для временного хранения выбранного элемента при перестановке:
Q = O(1),
где Q – требуемый объём.
Историчный метод прекрасно подходит для финализации крупной сортировки, когда остальные собратья уже потрудились. На массивах из 20–50 элементов – рекордсмен по скорости. Также пригодится, когда данные поступают поэтапно и нужно поддерживать порядок в реальном времени.