Гладкая сортировка - Smoothsort

Гладкая сортировка
Анимация, изображающая операцию сглаживания, показывающая, как создается и разбирается куча,
Smoothsort работает с массивом, который в основном в порядке. Полосы вверху показывают древовидную структуру.
Класс Алгоритм сортировки
Структура данных Множество
Наихудшая производительность O ( п войти п )
Лучшая производительность О ( п )
Средняя производительность O ( п войти п )
Сложность пространства в наихудшем случае O ( n ) всего, O (1) вспомогательных

В информатике , Плавная сортировка является сравнение на основе алгоритма сортировки . Вариант heapsort , он был изобретен и опубликован Edsger Dijkstra в 1981 году. Подобно heapsort, smoothsort - это алгоритм на месте с верхней границей O ( n log  n ) , но это не стабильная сортировка . Преимущество плавной сортировки заключается в том, что она приближается к времени O ( n ), если входные данные уже отсортированы в некоторой степени , тогда как heapsort усредняет O ( n log  n ) независимо от начального состояния сортировки.

Обзор

Как и heapsort , сглаженная сортировка организует входные данные в приоритетную очередь, а затем многократно извлекает максимум. Также как и heapsort, приоритетная очередь представляет собой неявную структуру данных в куче (неявное двоичное дерево с упорядочением в куче ), которая занимает префикс массива. Каждое извлечение сжимает префикс и добавляет извлеченный элемент к растущему отсортированному суффиксу. Когда префикс уменьшился до нуля, массив полностью отсортирован.

Heapsort сопоставляет двоичное дерево с массивом, используя обход дерева сверху вниз в ширину; массив начинается с корня дерева, затем с двух его дочерних элементов, затем с четырех внуков и так далее. Каждый элемент имеет четко определенную глубину ниже корня дерева, и каждый элемент, кроме корня, имеет своего родителя раньше в массиве. Однако его высота над листьями зависит от размера массива. Это имеет недостаток, заключающийся в том, что каждый элемент должен быть перемещен как часть процесса сортировки: он должен пройти через корень, прежде чем быть перемещенным в свое окончательное положение.

Smoothsort использует другое сопоставление - обход пост-порядка снизу вверх в глубину . За левым дочерним элементом следует поддерево с корнем у его брата, а за правым дочерним элементом следует его родитель. Каждый элемент имеет четко определенную высоту над листьями, и каждый элемент, не являющийся листом, имеет своих дочерних элементов раньше в массиве. Однако его глубина ниже корня зависит от размера массива. Алгоритм организован таким образом, что корень находится в конце кучи, и в момент извлечения элемента из кучи он уже находится в своем конечном месте и его не нужно перемещать. Кроме того, отсортированный массив уже является допустимой кучей, а многие отсортированные интервалы являются действительными упорядоченными по куче поддеревьями.

Более формально каждая позиция i является корнем уникального поддерева, узлы которого занимают непрерывный интервал, заканчивающийся на i . Начальным префиксом массива (включая весь массив) может быть такой интервал, соответствующий поддереву, но в целом он распадается как объединение ряда последовательных таких интервалов поддерева, которые Дейкстра называет «растяжками». Любое поддерево без родителя (т. Е. Укоренившееся в позиции, родительский элемент которой лежит за рассматриваемым префиксом) дает растяжение в разложении этого интервала, поэтому такое разложение является уникальным. Когда к префиксу добавляется новый узел, происходит один из двух случаев: либо позиция является листом и добавляет отрезок длины 1 к разложению, либо он объединяется с двумя последними отрезками, становясь родителем их соответствующих корней, таким образом заменяя два отрезка новым отрезком, содержащим их объединение плюс новую (корневую) позицию.

Дейкстра отметил, что очевидным правилом было бы комбинировать отрезки тогда и только тогда, когда они имеют равный размер, и в этом случае все поддеревья будут идеальными двоичными деревьями размером 2 k −1 . Однако он выбрал другое правило, которое дает больше возможных размеров деревьев. Это имеет ту же асимптотическую эффективность , но дает небольшой постоянный коэффициент эффективности, поскольку требует меньшего количества растяжек для покрытия каждого интервала.

Правило, которое использует Дейкстра, состоит в том, что последние два отрезка комбинируются тогда и только тогда, когда их размеры являются последовательными числами Леонардо L ( i +1) и L ( i ) (в этом порядке), которые определяются рекурсивно, очень похожим образом. к числам Фибоначчи , как:

  • L (0) = L (1) = 1
  • L ( к +2) = L ( к +1) + L ( к ) + 1

Как следствие, размер любого поддерева - это число Леонардо. Последовательность размеров растяжения, разлагающих первые n позиций для любого n , можно найти жадным способом: первый размер - это наибольшее число Леонардо, не превышающее n , а остаток (если есть) раскладывается рекурсивно. Размеры растяжек уменьшаются, строго так, за исключением, возможно, двух окончательных размеров 1 и избегания последовательных чисел Леонардо, за исключением, возможно, двух последних размеров.

В дополнение к тому, что каждый участок представляет собой дерево с упорядоченной кучей, корни деревьев поддерживаются в отсортированном порядке. Это эффективно добавляет третьего ребенка (которого Дейкстра называет «пасынок») к каждому корню, связывая его с предыдущим корнем. Это объединяет все деревья в одну глобальную кучу. с глобальным максимумом в конце.

Хотя местоположение пасынка каждого узла фиксировано, связь существует только для корней дерева, а это означает, что ссылки удаляются при объединении деревьев. Это отличается от обычных дочерних элементов, которые связаны, пока существует родительский элемент.

На первом этапе сортировки (рост кучи) все большая начальная часть массива реорганизуется так, что поддерево для каждого из его участков представляет собой максимальную кучу: запись в любой позиции, не являющейся листом, по крайней мере, такой же большой, как записи в позициях, которые являются его дочерними элементами. К тому же все корни по размеру не меньше их пасынков.

На втором этапе (сжатие кучи) максимальный узел отсоединяется от конца массива (без необходимости его перемещать), и инварианты кучи восстанавливаются среди его дочерних узлов. (В частности, среди новоиспеченных пасынков.)

На практике часто требуется вычисление чисел Леонардо L ( k ) . Дейкстра предлагает умный код, который использует фиксированное количество целочисленных переменных для эффективного вычисления значений, необходимых в то время, когда они необходимы. В качестве альтернативы, если существует конечное ограничение N на размер сортируемых массивов, предварительно вычисленную таблицу чисел Леонардо можно сохранить в пространстве O (log  N ) .

Операции

Хотя две фазы процедуры сортировки противоположны друг другу в том, что касается развития структуры «последовательность куч», они реализуются с использованием одного базового примитива, что эквивалентно операции «отсеивания» в двоичном max- куча.

Просеивание вниз

Основная операция sift -down (которую Дейкстра называет " trinkle ") восстанавливает инвариант кучи, когда он, возможно, нарушается только в корневом узле. Если корневой узел меньше любого из его дочерних узлов, он заменяется его самым большим дочерним узлом, и процесс повторяется с корневым узлом в его новом поддереве.

Разница между smoothsort и двоичной max-heap состоит в том, что корень каждого участка должен быть упорядочен по отношению к третьему «пасынку»: корню предыдущего участка. Таким образом, процедура отсеивания начинается с серии четырехсторонних сравнений (корневой узел и три дочерних элемента) до тех пор, пока пасынок не станет максимальным элементом, затем серии трехсторонних сравнений (корень плюс два дочерних элемента) до тех пор, пока не будет корень. узел находит свой последний дом, и инварианты восстанавливаются.

Каждое дерево представляет собой полное двоичное дерево : у каждого узла есть два дочерних элемента или нет. Нет необходимости иметь дело с частным случаем одного дочернего элемента, который встречается в стандартной неявной двоичной куче . (Но особый случай ссылок пасынка более чем компенсирует эту экономию.)

Поскольку существует O (log  n ) отрезков, каждое из которых является деревом глубины O (log  n ) , время выполнения каждой операции отсеивания ограничено O (log  n ) .

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

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

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

Оптимизация

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

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

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

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

Поскольку половина всех узлов в полном двоичном дереве являются листьями, в среднем выполняется одна операция отсеивания на узел.

Оптимизация

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

Анализ

Smoothsort занимает O ( n ) времени для обработки предварительно отсортированного массива, O ( n log  n ) в худшем случае и обеспечивает почти линейную производительность на многих почти отсортированных входных данных. Однако он не обрабатывает все почти отсортированные последовательности оптимальным образом. Используя количество инверсий в качестве меры ун-sortedness (число пар индексов я и J с I < J и А [ я ]> [ J ] , ибо случайным образом отсортированного ввода это примерно п 2 /4 ), возможны входные последовательности с инверсиями O ( n log  n ), которые требуют времени Ω ( n log  n ) , тогда как другие алгоритмы адаптивной сортировки могут решить эти случаи за время O ( n log log  n ) .

Алгоритм плавной сортировки должен иметь возможность хранить в памяти размеры всех деревьев в куче Леонардо. Поскольку они сортируются по порядку и все порядки различны, это обычно делается с использованием битового вектора, указывающего, какие порядки присутствуют. Более того, поскольку наибольший порядок не превышает O (log  n ) , эти биты могут быть закодированы в O (1) машинных словах, предполагая трансдихотомическую машинную модель .

Обратите внимание, что O (1) машинных слов - это не то же самое, что одно машинное слово. 32-битного вектора будет достаточно для размеров меньше L (32) = 7049155 . 64-битный вектор подходит для размеров меньше L (64) = 34335360355129 ≈ 2 45 . Обычно требуется 1 / log 2 ( φ ) ≈ 1,44 бита вектора на бит размера.

Тополь сорт

Более простой алгоритм, вдохновленный гладкой сортировкой, - это сортировка тополей . Названный в честь рядов деревьев уменьшающегося размера, часто встречающихся в голландских польдерах , он выполняет меньше сравнений, чем плавная сортировка, для входных данных, которые в основном не отсортированы, но не может достичь линейного времени для отсортированных входных данных.

Значительное изменение, внесенное в сортировку тополя, состоит в том, что корни различных деревьев не отсортированы; нет звеньев "пасынок", связывающих их в одну кучу. Вместо этого каждый раз, когда куча сокращается на втором этапе, выполняется поиск в корнях, чтобы найти максимальную запись.

Поскольку существует n шагов сжатия, каждый из которых должен искать максимальное количество корней дерева O (log  n ) , оптимальное время выполнения для сортировки тополя составляет O ( n log  n ) .

Авторы также предлагают использовать идеальные бинарные деревья, а не деревья Леонардо, чтобы обеспечить дальнейшее упрощение, но это менее значительное изменение.

Та же самая структура была предложена в качестве очереди приоритетов общего назначения под названием « куча пост-порядка» , обеспечивающая амортизированное время вставки O (1) в структуре, более простой, чем неявная биномиальная куча .

Приложения

Библиотека musl C использует smoothsort для реализации qsort().

использованная литература

внешние ссылки