Введение

Алгоритм сортировки на основе сравнения

В информатике, smoothsort — это алгоритм сортировки на основе сравнения. Являясь вариантом сортировки кучей (heapsort), он был изобретен и опубликован Эдсгером Дейкстрой в 1981 году. Как и heapsort, smoothsort является алгоритмом, выполняемым на месте, с верхней границей сложности O(n) (см. нотацию «большое O»), но не является стабильной сортировкой. Преимущество smoothsort заключается в том, что при некоторой предварительной отсортированности входных данных он приближается к времени работы O(n), в то время как heapsort в среднем имеет сложность O(n log n) независимо от начального состояния сортировки.

Просеивание

Операция "просеивания вниз" (которую Дайкстра называет "триклом") восстанавливает инвариант кучи, когда он может быть нарушен только в корневом узле. Если коренной узел меньше любого из своих дочерних узлов, он меняется местами с наибольшим из них, и процесс повторяется с коренным узлом в его новом поддереве. Отличие smoothsort от бинарной кучи максимума заключается в том, что корень каждого участка должен быть упорядочен относительно третьего элемента – "пасынка": корня предыдущего участка. Поэтому процедура просеивания начинается с серии сравнений в четыре стороны (коренной узел и три дочерних узла), пока пасынок не перестанет быть максимальным элементом, затем следует серия сравнений в три стороны (корень плюс два дочерних узла), пока коренной узел не займет свое окончательное место и инварианты не будут восстановлены. Каждое дерево является полным двоичным деревом: каждый узел имеет два дочерних узла или не имеет их вовсе. Нет необходимости учитывать специальный случай с одним дочерним узлом, который возникает в стандартной неявной бинарной куче. (Но особый случай связей с пасынками с лихвой компенсирует эту простоту.) Поскольку существует O(log n) участков, каждый из которых представляет собой дерево глубины O(log n), время выполнения каждой операции просеивания ограничено O(log n).

Увеличение области кучи путем включения элемента справа

Когда дополнительный элемент рассматривается для включения в последовательность растяжек (список несвязанных кучных структур), он либо формирует новую растяжку из одного элемента, либо объединяет две правые растяжки, становясь родителем корней обеих и формируя новую растяжку, которая заменяет их в последовательности. Что именно произойдет, зависит только от размеров текущих растяжек (и, в конечном счете, только от индекса добавляемого элемента). Дикстра установил, что растяжки объединяются тогда и только тогда, когда их размеры равны L(k+1) и L(k) для некоторого k, то есть являются последовательными числами Леонардо; новая растяжка будет иметь размер L(k+2). В любом случае, новый элемент необходимо просеять вниз до своего правильного места в кучной структуре. Даже если новый узел представляет собой растяжку из одного элемента, его все равно необходимо упорядочить относительно корня предыдущей растяжки.

Оптимизация

Алгоритм Дейкстры экономит вычислительные ресурсы, отмечая, что полный инвариант кучи необходим лишь в конце фазы построения, но не на каждом промежуточном шаге. В частности, требование, чтобы элемент был больше своего потомка, важно только для элементов, которые станут конечными корнями дерева. Поэтому, при добавлении элемента, следует вычислить позицию его будущего родителя. Если эта позиция находится в пределах диапазона оставшихся неотсортированных значений, следует действовать так, как будто потомка нет, и выполнять только просеивание вниз в текущем дереве.

Уменьшение области кучи, отделяя самый правый элемент от нее

В течение этой фазы форма последовательности растяжек проходит изменения фазы роста в обратном порядке. При отделении листового узла никакая работа не требуется, но для нелистового узла его два дочерних узла становятся корнями новых растяжек и должны быть перемещены на свои места в последовательности корней растяжек. Это достигается двойным применением просеивания вниз: сначала для левого дочернего узла, а затем для правого дочернего узла (чьим "приёмным сыном" был левый дочерний узел). Поскольку половина всех узлов в полном двоичном дереве – это листья, в среднем выполняется одна операция просеивания вниз на узел.

Оптимизация

Уже известно, что вновь открытые корни расположены в правильном порядке относительно своих прямых потомков; под вопросом лишь порядок относительно их сводных братьев. Следовательно, при уменьшении кучи первый шаг просеивания вниз можно упростить до одного сравнения со сводным братом. Если происходит обмен, последующие шаги должны выполнять полное четырехстороннее сравнение.

Анализ

Smoothsort занимает O(n) времени для обработки предварительно отсортированного массива, O(n log n) в худшем случае и достигает почти линейной производительности на многих почти отсортированных входных данных. Однако он не обрабатывает оптимально все почти отсортированные последовательности. Используя количество инверсий в качестве меры несортированности (число пар индексов i и j, где i < j и A[i] > A[j]; для случайно отсортированных входных данных это примерно n²/4), существуют возможные входные последовательности с O(n log n) инверсиями, которые приводят к времени Ω(n log n), в то время как другие адаптивные алгоритмы сортировки могут решить эти случаи за O(n log log n) времени. Алгоритму Smoothsort необходимо иметь возможность хранить в памяти размеры всех деревьев в куче Леонардо. Поскольку они упорядочены по порядку, и все порядки различны, это обычно делается с использованием битового вектора, указывающего, какие порядки присутствуют. Более того, поскольку наибольший порядок не превышает O(log n), эти биты могут быть закодированы в O(1) машинных словах, при условии использования трансдихотомической модели машины. Следует отметить, что O(1) машинных слов – это не то же самое, что одно машинное слово. 32-битного вектора будет достаточно только для размеров меньше 1=L(32) = 7049155. 64-битный вектор подойдет для размеров меньше 1=L(64) = 34335360355129 ≈ 2⁴⁵. В общем случае, требуется 1/log₂ (Золотое сечение битов вектора на бит размера).

Сортировка тополя

Простейший алгоритм, вдохновлённый smoothsort, — это poplar sort (сортировка пополяром). Названный в честь рядов деревьев убывающего размера, часто встречающихся в голландских полдерах, он выполняет меньше сравнений, чем smoothsort для входных данных, которые не отсортированы в основном, но не может достичь линейного времени для отсортированных входных данных. Значительное изменение, внесённое poplar sort, заключается в том, что корни различных деревьев не поддерживаются в отсортированном порядке; нет "усыновленных" связей, объединяющих их в единую кучу. Вместо этого, каждый раз, когда куча сжимается во второй фазе, корни просматриваются для поиска максимального элемента. Поскольку существует n шагов сжатия, каждый из которых требует поиска максимума среди O(log n) корней деревьев, лучшее время работы poplar sort составляет O(n log n). Авторы также предлагают использовать полные двоичные деревья вместо деревьев Леонардо для дальнейшего упрощения, но это менее существенное изменение. Та же структура была предложена в качестве очереди приоритетов общего назначения под названием post-order heap (куча в порядке обхода), обеспечивая амортизированное время вставки O(1) в структуре, более простой, чем неявная биномиальная куча.

Приложения

Библиотека musl C использует smoothsort в своей реализации функции qsort.