Зарождение компьютеров, активное развитие точных наук, появление дисциплин на стыке направлений потребовали создания принципов работы с данными, в том числе способов упорядочивания. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают один из самых быстрых алгоритмов сортировки, созданный в стенах МГУ.
В 1960 году британский учёный Энтони Хоар, работавший в Московском государственном университете (МГУ), разрабатывает быстрый алгоритм сортировки (quick sort, qsort). В нём заложен принцип «разделяй и властвуй», знакомый по методу фон Неймана: задача раскладывается на подзадачи, затем идут расчёты.
Идея такова: определяется опорный элемент (pivot), массив делится по принципу «значения больше или меньше выбранного». Процедура повторяется, пока не останутся единичные составляющие. Затем следуют вычисления и обратная сборка.
Рассмотрим на примере: массив из шести чисел [19, 56, 2, 87, 61, 33]. Отсортируем так, чтобы части выстроились в лесенку «по росту».
Опорным элементом принято брать самый правый. Сравним остальные значения с 33: 19 и 2 меньше – уходят влево; 56, 87 и 61 больше – вправо. Чтобы не потерять последовательность, перенесём 33 в середину.
Получились два подмассива: [19, 2] и [56, 87, 61]. Рассмотрим первый. Pivot-элементом выделим число 2. 19 больше – переводим вправо.
Для наглядности поставим двойку перед 19.
Следующим шагом разберём правый малый массив. 61 становится опорным элементом. 56 как младший остаётся в левой части, а 87 уходит вправо. Основание деления переносим на уровень ниже, чтобы не сбиться.
Исходный массив полностью разложен на атомы – соберём конструктор в обратном порядке по правилу: левая часть + опорный элемент + правая часть. Сначала вернём два подмассива: [2, 19, 33] и [56, 61, 87].
Заключительным шагом восстановим общий массив со всеми значениями – [2, 19, 33, 56, 61, 87].
Таким образом, массив из шести элементов упорядочен по возрастанию быстрой сортировкой: [19, 56, 2, 87, 61, 33] превратился в [2, 19, 33, 56, 61, 87]. Задача решена.
Скорость метода варьируется от квадратичной зависимости, когда опорные элементы не сбалансированы (например, правило «всегда правый»), до линейно-логарифмической оценки:
T = O(n2) – для худшего случая,
T = O(n·log n) – для остальных,
где T – время работы, n – число элементов.
Алгоритм работает в рекурсии (вызывает сам себя) и без спроса на дополнительное место, потому затраты памяти растут логарифмически:
Q = O(log n),
где Q – требуемый объём.
Подход Хоара избыточен для малых массивов. Но хорош, когда доступной памяти немного, важен кэш (qsort обращается к данным последовательно) или содержимое набора находится в неизвестном порядке. В последнем случае поможет доработка: случайный опорный элемент или медиана за основу.