пирамидальная сортировка
 Запуск пирамидальной сортировки массива случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи . Прежде чем произойдет фактическая сортировка, для иллюстрации кратко показана древовидная структура кучи. | |
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | |
| Лучшая производительность | (отдельные ключи) [1] [2] или (равные клавиши) |
| Средняя производительность | |
| Наихудшая пространственная сложность | общий вспомогательный |
В информатике , пирамидальная сортировка — это на основе сравнения алгоритм сортировки который можно рассматривать как «реализацию сортировки выбором с использованием правильной структуры данных ». [3] Подобно сортировке выбором, пирамидальная сортировка делит входные данные на отсортированную и несортированную область и итеративно сжимает неотсортированную область, извлекая из нее самый большой элемент и вставляя его в отсортированную область. В отличие от сортировки выбором, пирамидальная сортировка не тратит время на сканирование несортированной области в линейном времени; скорее, пирамидальная сортировка сохраняет несортированную область в структуре данных кучи, чтобы эффективно находить самый большой элемент на каждом этапе.
Хотя на практике на большинстве машин он несколько медленнее, чем хорошо реализованная быстрая сортировка , он имеет преимущества очень простой реализации и более благоприятного времени выполнения O ( n log n ) в худшем случае . Большинство реальных вариантов быстрой сортировки включают реализацию пирамидальной сортировки в качестве запасного варианта на случай, если они обнаружат, что быстрая сортировка становится вырождающейся. Пирамидальная сортировка — это алгоритм на месте , но он не является стабильной сортировкой .
Хипсорт был изобретен Дж. У. Дж. Уильямсом в 1964 году. [4] В документе также представлена двоичная куча как полезная структура данных сама по себе. [5] В том же году Роберт В. Флойд опубликовал улучшенную версию, которая могла сортировать массив на месте, продолжив свои более ранние исследования алгоритма сортировки деревьев . [5]
Обзор [ править ]
Алгоритм пирамидальной сортировки можно разделить на два этапа: построение кучи и извлечение кучи.
Куча — это неявная структура данных , которая не занимает места за пределами массива объектов, подлежащих сортировке; массив интерпретируется как полное двоичное дерево , где каждый элемент массива является узлом, а родительские и дочерние ссылки каждого узла определяются простой арифметикой над индексами массива. Для массива с отсчетом от нуля корневой узел хранится с индексом 0, а узлы, связанные с узлом i являются
iLeftChild(i) = 2⋅i + 1 iRightChild(i) = 2⋅i + 2 iParent(i) = floor((i−1) / 2)
где функция пола округляет до предыдущего целого числа. Более подробное объяснение см. в разделе «Двоичная куча § Реализация кучи» .
Это двоичное дерево представляет собой максимальную кучу, когда каждый узел больше или равен обоим своим дочерним элементам. Эквивалентно, каждый узел меньше или равен своему родителю. Это правило, применяемое ко всему дереву, приводит к тому, что максимальный узел располагается в корне дерева.
На первом этапе из данных создается куча (см. Двоичная куча § Построение кучи ).
На втором этапе куча преобразуется в отсортированный массив путем многократного удаления самого большого элемента из кучи (корня кучи) и помещения его в конец массива. Куча обновляется после каждого удаления, чтобы сохранить свойство кучи. После удаления всех объектов из кучи результатом является отсортированный массив.
Как правило, пирамидальная сортировка выполняется на месте. На первом этапе массив делится на несортированный префикс и суффикс, упорядоченный по куче (изначально пустой). Каждый шаг уменьшает префикс и расширяет суффикс. Когда префикс пуст, этот этап завершен. На втором этапе массив делится на упорядоченный в куче префикс и отсортированный суффикс (изначально пустой). Каждый шаг уменьшает префикс и расширяет суффикс. Когда префикс пуст, массив сортируется.
Алгоритм [ править ]
Алгоритм пирамидальной сортировки начинается с преобразования массива в двоичную максимальную кучу. Затем алгоритм неоднократно заменяет корень кучи (самый большой элемент, оставшийся в куче) его последним элементом, который затем объявляется частью отсортированного суффикса. Затем куча, поврежденная при замене корня, восстанавливается так, чтобы наибольший элемент снова оказался в корне. Это повторяется до тех пор, пока в куче не останется только одно значение.
Шаги:
- Позвоните в
heapify()функция в массиве. Это создает кучу из массива за O ( n ) операций. - Поменяйте местами первый элемент массива (самый большой элемент в куче) с последним элементом кучи. Уменьшите рассматриваемый диапазон кучи на единицу.
- Позвоните в
siftDown()функция в массиве, чтобы переместить новый первый элемент в правильное место в куче. - Возвращайтесь к шагу (2), пока оставшийся массив не станет одним элементом.
The heapify() Операция запускается один раз и имеет O ( n ) производительность . siftDown() Функция вызывается n раз и каждый раз требует работы O (log n ) из-за ее обхода, начиная с корневого узла. Следовательно, производительность этого алгоритма равна O ( n + n log n ) = O ( n log n ) .
Сердцем алгоритма является siftDown() функция. Это создает двоичные кучи из меньших куч и может рассматриваться двумя эквивалентными способами:
- учитывая две двоичные кучи и общий родительский узел, который не является частью ни одной из кучи, объединить их в одну большую двоичную кучу; или
- учитывая «поврежденную» двоичную кучу, где свойство max-heap (ни один дочерний узел не превышает родительский) сохраняется везде, за исключением, возможно, между корневым узлом и его дочерними узлами, восстановите ее, чтобы создать неповрежденную кучу.
Чтобы установить свойство max-heap в корне, необходимо сравнить до трех узлов (корень и два его дочерних узла), а наибольший из них должен быть сделан корнем. Легче всего это сделать, найдя наибольший дочерний элемент и затем сравнив его с корнем. Есть три случая:
- Если дочерних элементов нет (две исходные кучи пусты), свойство кучи тривиально сохраняется и никаких дальнейших действий не требуется.
- Если root больше или равен наибольшему дочернему элементу, свойство кучи сохраняется, и никаких дальнейших действий не требуется.
- Если корень меньше наибольшего дочернего узла, поменяйте местами два узла. Свойство кучи теперь сохраняется на вновь повышенном узле (оно больше или равно обоим его дочерним элементам и фактически больше, чем любой потомок), но может быть нарушено между недавно пониженным экс-корнем и его новыми дочерними элементами. Чтобы это исправить, повторите
siftDown()операция над поддеревом, корнем которого является недавно пониженный в должности бывший корень.
Количество итераций в любом siftdown() вызов ограничен высотой дерева, которая равна ⌊ log 2 n ⌋ = O (log n ) .
Псевдокод [ править ]
Ниже приведен простой способ реализации алгоритма в псевдокоде . Массивы начинаются с нуля и swap используется для обмена двумя элементами массива. Движение «вниз» означает от корня к листьям или от нижних индексов к более высоким. Обратите внимание, что во время сортировки самый большой элемент находится в корне кучи. a[0], а в конце сортировки самый большой элемент находится в a[end].
procedure heapsort(a, count) is
input: an unordered array a of length count
(Build the heap in array a so that largest value is at the root)
heapify(a, count)
(The following loop maintains the invariants that a[0:end−1] is a heap, and
every element a[end:count−1] beyond end is greater than everything before it,
i.e. a[end:count−1] is in sorted order.)
end ← count
while end > 1 do
(the heap size is reduced by one)
end ← end − 1
(a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
swap(a[end], a[0])
(the swap ruined the heap property, so restore it)
siftDown(a, 0, end)
Процедура сортировки использует две подпрограммы: heapify и siftDown. Первая — это обычная процедура построения кучи на месте, а вторая — обычная подпрограмма для реализации heapify.
(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
(start is initialized to the first leaf node)
(the last element in a 0-based array is at index count-1; find the parent of that element)
start ← iParent(count-1) + 1
while start > 0 do
(go to the last non-heap node)
start ← start − 1
(sift down the node at index 'start' to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count)
(after sifting down the root all nodes/elements are in heap order)
(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, root, end) is
while iLeftChild(root) < end do (While the root has at least one child)
child ← iLeftChild(root) (Left child of root)
(If there is a right child and that child is greater)
if child+1 < end and a[child] < a[child+1] then
child ← child + 1
if a[root] < a[child] then
swap(a[root], a[child])
root ← child (repeat to continue sifting down the child now)
else
(The root holds the largest element. Since we may assume the heaps rooted
at the children are valid, this means that we are done.)
return
The heapify Процедура работает путем создания небольших куч и многократного их объединения с использованием siftDown. Он начинается с листьев, отмечая, что они сами по себе являются тривиальными, но действительными кучами, а затем добавляются родители. Начиная с элемента n /2 и двигаясь в обратном направлении, каждый внутренний узел становится корнем допустимой кучи путем просеивания вниз. Последний шаг — отсеивание первого элемента, после чего весь массив подчиняется свойству кучи.
Чтобы увидеть, что это занимает время O ( n ) , посчитайте количество наихудших случаев. siftDown итерации. Последняя половина массива требует нулевых итераций, предыдущая четверть требует не более одной итерации, восьмая перед ней требует не более двух итераций, шестнадцатая до этого требует не более трех и так далее.
Взглянем по-другому, если предположить, что каждый siftDown вызов требует максимального количества итераций, первая половина массива требует одну итерацию, первая четверть требует еще одну (всего 2), первая восьмая требует еще одну (всего 3) и так далее.
Это составляет n /2 + n /4 + n /8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯) , где бесконечная сумма — это известная геометрическая прогрессия , сумма которой равна 1 , таким образом, продукт равен просто n .
Вышеупомянутое является приблизительным. Известно, что точное количество сравнений в наихудшем случае во время фазы построения пирамиды при пирамидальной сортировке равно 2 n − 2 s 2 ( n ) − e 2 ( n ) , где s 2 ( n ) — количество 1 битов. двоичном представлении n и e2 n ( в ) — это количество конечных нулевых битов . [6] [7]
Стандартная реализация [ править ]
Хотя удобно рассматривать эти две фазы по отдельности, большинство реализаций объединяют их, позволяя использовать один экземпляр siftDownбыть расширенным встроенным . [8] : Алгоритм H Две переменные (здесь start и end) отслеживать границы области кучи. Часть массива перед start не отсортирован, а часть, начинающаяся с end сортируется. Уменьшается строительство кучи start пока оно не станет равным нулю, после чего извлечение кучи уменьшается end пока оно не станет равным 1 и массив не будет полностью отсортирован.
procedure heapsort(a, count) is
input: an unordered array a of length count
start ← floor(count/2)
end ← count
while end > 1 do
if start > 0 then (Heap construction)
start ← start − 1
else (Heap extraction)
end ← end − 1
swap(a[end], a[0])
(The following is siftDown(a, start, end))
root ← start
while iLeftChild(root) < end do
child ← iLeftChild(root)
(If there is a right child and that child is greater)
if child+1 < end and a[child] < a[child+1] then
child ← child + 1
if a[root] < a[child] then
swap(a[root], a[child])
root ← child (repeat to continue sifting down the child now)
else
break (return to outer loop)
Вариации [ править ]
Уильямса Конструкция кучи
В приведенном выше описании используется улучшенный алгоритм построения кучи Флойда, который работает за время O ( n ) и использует тот же алгоритм построения кучи. siftDown примитивный, как фаза извлечения кучи. Хотя этот алгоритм, будучи более быстрым и простым в программировании, используется во всех практических реализациях пирамидальной сортировки, исходный алгоритм Уильямса может быть проще для понимания и необходим для реализации более общей очереди с приоритетами двоичной кучи .
Вместо объединения множества маленьких куч алгоритм Уильямса поддерживает одну кучу в начале массива и неоднократно добавляет дополнительный элемент, используя siftUp примитивный. Находясь в конце массива, новый элемент является листом и не имеет дочерних элементов, о которых стоит беспокоиться, но может нарушить свойство кучи, будучи больше своего родителя. В этом случае поменяйте его местами с его родителем и повторяйте проверку до тех пор, пока родительский элемент не станет больше или пока родительский элемент не исчезнет (мы достигли корня). В псевдокоде это так:
procedure siftUp(a, end) is
input: a is the array, which heap-ordered up to end-1.
end is the node to sift up.
while end > 0
parent := iParent(end)
if a[parent] < a[end] then (out of max-heap order)
swap(a[parent], a[end])
end := parent (continue sifting up)
else
return
procedure heapify(a, count) is
(start with a trivial single-element heap)
end := 1
while end < count
(sift up the node at index end to the proper place such that
all nodes above the end index are in heap order)
siftUp(a, end)
end := end + 1
(after sifting up the last node all nodes are in heap order)
Чтобы понять, почему этому алгоритму может потребоваться асимптотически больше времени для построения кучи ( O ( n log n ) против O ( n ) в худшем случае), обратите внимание, что в алгоритме Флойда почти все вызовы siftDown операции применимы к очень маленьким кучам. Половина куч — это тривиальные кучи высотой 1, и их можно полностью пропустить, половина остальных — это кучи высотой 2 и так далее. Только два вызова находятся в куче размера n /2 и только один siftDown операция выполняется над полной кучей из n элементов. Общий средний показатель siftDown операция занимает O (1) времени.
Напротив, алгоритм Уильямса большинство вызовов siftUp складываются на больших кучах высотой O (log n ) . Половина вызовов выполняется с размером кучи n /2 или более, три четверти — с размером кучи n /4 или более и так далее. Хотя среднее количество шагов похоже на технику Флойда, [9] : 3 предварительно отсортированный вход приведет к наихудшему случаю: каждый добавленный узел анализируется до корня, поэтому средний вызов siftUp потребуется примерно (log 2 n − 1)/2 + (log 2 n − 2)/4 + (log 2 n − 3)/8 + ⋯ = log 2 n − (1 + 1/2 + 1/4 + ⋯) = log 2 n − 2 итерации.
Поскольку в нем доминирует вторая фаза извлечения кучи, сам алгоритм пирамидальной сортировки имеет временную сложность O ( n log n ) при использовании любой версии heapify.
пирамидальная сортировка снизу вверх [ править ]
Пирамидальная сортировка снизу вверх — это вариант, который уменьшает количество сравнений, необходимых для значительного фактора. В то время как обычная пирамидальная сортировка «сверху вниз» требует 2 n log 2 n + O ( n ) сравнений в худшем случае и в среднем, [10] восходящий вариант требует в среднем n log 2 n + O (1) сравнений, [10] и 1,5 n log 2 n + O ( n ) в худшем случае. [11]
Если сравнения дешевы (например, целочисленные ключи), тогда разница неважна, [12] поскольку пирамидальная сортировка сверху вниз сравнивает значения, которые уже загружены из памяти. Однако если сравнения требуют вызова функции или другой сложной логики, тогда предпочтительна восходящая пирамидальная сортировка.
Это достигается за счет использования более сложной siftDown процедура. Это изменение немного улучшает фазу построения кучи с линейным временем. [13] но более значителен на втором этапе. Как и пирамидальная сортировка сверху вниз, каждая итерация второго этапа извлекает вершину кучи. a[0]и заполняет пробел, который он оставляет a[end], затем просеивает этот последний элемент в кучу. Но этот элемент взят с самого нижнего уровня кучи, то есть это один из самых маленьких элементов в куче, поэтому при сортировке вниз, скорее всего, потребуется много шагов, чтобы переместить его обратно вниз. [14] При пирамидальной сортировке сверху вниз каждый шаг siftDown требует двух сравнений, чтобы найти минимум три элемента: новый узел и два его дочерних элемента.
Сортировка снизу вверх концептуально заменяет корень значением −∞ и отсеивает его, используя только одно сравнение на уровень (поскольку ни один дочерний элемент не может быть меньше −∞), пока не будут достигнуты листья, а затем заменяет −∞ правильным значение и просеивает его вверх (опять же, используя одно сравнение на уровень), пока не будет найдена правильная позиция.
Это помещает корень в то же место, что и сверху вниз. siftDown, но для поиска этого местоположения требуется меньше сравнений. Для любого одиночного siftDown метод «снизу вверх» предпочтителен, если количество движений вниз не менее 2 ⁄ 3 высоты дерева (при числе сравнений 4/3 в раза больше высоты для обоих методов), и оказывается, что в среднем это более чем верно, даже для входных данных в худшем случае. [11]
Наивная реализация этого концептуального алгоритма привела бы к некоторому избыточному копированию данных, поскольку зелье просеивания вверх отменяет часть отсеивания вниз. Практическая реализация ищет лист вниз, где будет быть размещен корень расположен −∞, а затем вверх, где должен . Наконец, обход вверх продолжается до исходной позиции корня, не выполняя больше сравнений, а заменяя узлы для завершения необходимой перестановки. Эта оптимизированная форма выполняет такое же количество обменов, как и нисходящая. siftDown.
Поскольку он проходит весь путь вниз, а затем возвращается вверх, называют его пирамидальной сортировкой с отскоком . некоторые авторы [15]
function leafSearch(a, i, end) is
j ← i
while iRightChild(j) < end do
(Determine which of j's two children is the greater)
if a[iRightChild(j)] > a[iLeftChild(j)] then
j ← iRightChild(j)
else
j ← iLeftChild(j)
(At the last level, there might be only one child)
if iLeftChild(j) < end then
j ← iLeftChild(j)
return j
Возвращаемое значение leafSearch используется в модифицированном siftDown рутина: [11]
procedure siftDown(a, i, end) is
j ← leafSearch(a, i, end)
while a[i] > a[j] do
j ← iParent(j)
while j > i do
swap(a[i], a[j])
j ← iParent(j)
Пирамидальная сортировка снизу вверх была объявлена как быстрая быстрая сортировка (с выбором медианы из трех опорных точек) для массивов размером ≥16000. [10]
Переоценка этого алгоритма в 2008 году показала, что он не быстрее пирамидальной сортировки сверху вниз для целочисленных ключей, предположительно потому, что современное предсказание ветвей сводит к нулю стоимость предсказуемых сравнений, которых удается избежать пирамидальной сортировке снизу вверх. [12]
Дальнейшее уточнение выполняет двоичный поиск при поиске вверх и сортирует в худшем случае ( n +1)(log 2 ( n +1) + log 2 log 2 ( n +1) + 1,82) + O (log 2 n ) сравнений, приближаясь к теории информации нижней границе n log 2 n - 1,4427 n сравнений. [16]
Вариант, который использует два дополнительных бита на внутренний узел ( n всего -1 бит для кучи из n элементов) для кэширования информации о том, какой дочерний элемент больше (два бита необходимы для хранения трех случаев: левого, правого и неизвестного). [13] использует меньше n log 2 n + 1,1 n сравнения. [17]
Другие варианты [ править ]
- Тернарная пирамидальная сортировка использует троичную кучу вместо двоичной; то есть каждый элемент в куче имеет трех дочерних элементов. Его сложнее программировать, но он выполняет в постоянное число раз меньше операций замены и сравнения. Это связано с тем, что каждый шаг сортировки в троичной куче требует трех сравнений и одной замены, тогда как в двоичной куче требуются два сравнения и одна замена. Два уровня в троичной куче, покрывающей 3 2 = 9 элементов, выполняющих больше работы с тем же количеством сравнений, что и три уровня в двоичной куче, которые охватывают только 2 3 = 8. [ нужна ссылка ] Это в первую очередь академический интерес или в качестве студенческого упражнения. [18] поскольку дополнительная сложность не стоит незначительной экономии, а пирамидальная сортировка снизу вверх превосходит обе.
- Оптимизированная для памяти пирамидальная сортировка [19] : 87 улучшает локальность пирамидальной сортировки за счет еще большего увеличения числа дочерних элементов. Это увеличивает количество сравнений, но поскольку все дочерние элементы хранятся в памяти последовательно, уменьшается количество строк кэша, к которым осуществляется доступ во время обхода кучи, что приводит к чистому повышению производительности.
- Стандартная реализация алгоритма построения кучи Флойда вызывает большое количество промахов в кэше , когда размер данных превышает размер кэша ЦП . [19] : 87 Более высокую производительность при работе с большими наборами данных можно получить, объединяя в порядке глубины , объединяя подкучи как можно скорее, а не объединяя все подкучи на одном уровне, прежде чем переходить к предыдущему. [9] [20]
- Неуместная пирамидальная сортировка [21] [22] [14] улучшает пирамидальную сортировку снизу вверх, устраняя худший случай, гарантируя n log 2 n + O ( n ) сравнений. Когда максимум достигнут, вместо того, чтобы заполнять освободившееся пространство несортированным значением данных, заполните его контрольным значением -∞ , которое никогда не «отскакивает» назад. Оказывается, это можно использовать как примитив в локальном (и нерекурсивном) алгоритме «QuickHeapsort». [23] Сначала вы выполняете проход секционирования, подобный быстрой сортировке, но меняя порядок секционированных данных в массиве на обратный. Предположим ( без ограничения общности ), что меньший раздел — это тот, который больше опорного, который должен находиться в конце массива, но наш шаг обратного разделения помещает его в начало. Сформируйте кучу из меньшего раздела и выполните на нем пирамидальную сортировку, заменяя извлеченные максимумы значениями из конца массива. Они меньше опорного значения, то есть меньше любого значения в куче, поэтому служат контрольными значениями −∞ . Как только пирамидальная сортировка завершена (и ось переместилась непосредственно перед отсортированным концом массива), порядок разделов меняется на обратный, и более крупный раздел в начале массива может быть отсортирован таким же образом. (Поскольку нет хвостовой рекурсии быстрой сортировки , это также исключает использование стека O (log n ) .)
- Алгоритм сортировки гладкой [24] — это вариант пирамидальной сортировки, разработанный Эдсгером В. Дейкстрой в 1981 году. Как и пирамидальная сортировка, верхняя граница гладкой сортировки равна O ( n log n ) . Преимущество плавной сортировки заключается в том, что она приближается к времени O ( n ) , если входные данные уже отсортированы в некоторой степени , тогда как пирамидальная сортировка усредняет O ( n log n ) независимо от начального состояния сортировки. Из-за своей сложности гладкая сортировка используется редко. [ нужна ссылка ]
- Левкопулос и Петерссон [25] описать вариант пирамидальной сортировки, основанный на куче декартовых деревьев . строится декартово дерево Сначала из входных данных за время O ( n ) , а его корень помещается в одноэлементную двоичную кучу. Затем мы повторно извлекаем минимум из двоичной кучи, выводим корневой элемент дерева и добавляем в двоичную кучу его левых и правых дочерних элементов (если они есть), которые сами являются декартовыми деревьями. [26] Как они показывают, если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с небольшим количеством узлов, имеющими левых и правых дочерних элементов, в результате чего двоичная куча останется маленькой и позволит алгоритму сортировать быстрее, чем O ( n log n ) для входных данных, которые уже почти отсортированы.
- Некоторые варианты, такие как слабая пирамидальная сортировка, требуют в худшем случае n log 2 n + O (1) сравнений, близких к теоретическому минимуму, с использованием одного дополнительного бита состояния на узел. Хотя этот дополнительный бит делает алгоритмы не совсем уместными, если внутри элемента можно найти место для него, эти алгоритмы просты и эффективны. [9] : 40 но все же медленнее, чем двоичные кучи, если сравнения ключей достаточно дешевы (например, целочисленные ключи), поэтому постоянный коэффициент не имеет значения. [27]
- «Окончательная пирамидальная сортировка» Катаджайнена не требует дополнительной памяти, выполняет n log 2 n + O (1) сравнений и такое же количество перемещений элементов. [28] Однако это еще более сложно и неоправданно, если только сравнения не являются очень дорогостоящими.
Сравнение с другими сортами [ править ]
Heapsort в первую очередь конкурирует с быстрой сортировкой , еще одним очень эффективным алгоритмом нестабильной сортировки на месте общего назначения на основе сравнения.
Основными преимуществами пирамидальной сортировки являются ее простой, нерекурсивный код , минимальные требования к дополнительной памяти и надежно высокая производительность: ее лучшие и худшие случаи находятся в пределах небольшого постоянного коэффициента друг от друга и теоретической нижней границы сортировок сравнения . Хотя он не может работать лучше, чем O ( n log n ) для предварительно отсортированных входных данных, он не страдает от быстрой сортировки O ( n 2 ) в худшем случае.
Реальные реализации быстрой сортировки используют различные эвристики , чтобы избежать худшего случая, но это делает их реализацию намного более сложной, а такие реализации, как интросорт и быстрая сортировка с обходом шаблонов. [29] используйте пирамидальную сортировку в качестве запасного варианта в крайнем случае, если они обнаруживают вырожденное поведение. Таким образом, их производительность в худшем случае немного хуже, чем если бы пирамидальная сортировка использовалась с самого начала.
Основными недостатками пирамидальной сортировки являются ее плохая локальность отсчета и ее по своей сути серийный характер; доступы к неявному дереву широко разбросаны и в основном случайны, и не существует простого способа преобразовать его в параллельный алгоритм .
Гарантии производительности в наихудшем случае делают пирамидальную сортировку популярной в вычислениях в реальном времени и системах, связанных со злонамеренно выбранными входными данными. [30] например, ядро Linux. [31] Сочетание небольшой реализации и надежной «достаточно хорошей» производительности делает его популярным во встроенных системах и вообще в любых приложениях, где сортировка не является узким местом производительности . Например, пирамидальная сортировка идеально подходит для сортировки списка имен файлов для отображения, но система управления базами данных , вероятно, потребует более агрессивно оптимизированного алгоритма сортировки.
Хорошо реализованная быстрая сортировка обычно в 2–3 раза быстрее пирамидальной сортировки. [19] [32] Хотя быстрая сортировка требует меньшего количества сравнений, это несущественный фактор. (Результаты, требующие вдвое большего количества сравнений, измеряют версию сверху вниз; см. § пирамидальную сортировку снизу вверх .) Основное преимущество быстрой сортировки - ее гораздо лучшая локальность ссылки: разделение представляет собой линейное сканирование с хорошей пространственной локальностью, а рекурсивное подразделение имеет хорошую временную локальность. При дополнительных усилиях быстрая сортировка также может быть реализована в основном в коде без ветвей , а для параллельной сортировки подразделов можно использовать несколько процессоров. Таким образом, быстрая сортировка предпочтительна, когда дополнительная производительность оправдывает усилия по реализации.
Другой основной O ( n log n ) алгоритм сортировки — это сортировка слиянием , но он редко напрямую конкурирует с пирамидальной сортировкой, поскольку не выполняется на месте. Требование сортировки слиянием к дополнительному пространству Ω( n ) (примерно половина размера входных данных) обычно непомерно велико, за исключением ситуаций, когда сортировка слиянием имеет явное преимущество:
- Когда стабильная сортировка требуется
- При использовании (частично) предварительно отсортированного ввода
- Сортировка связанных списков (в этом случае сортировка слиянием требует минимального дополнительного пространства)
- Параллельная сортировка; сортировка слиянием распараллеливается даже лучше, чем быстрая сортировка, и позволяет легко добиться почти линейного ускорения
- Внешняя сортировка ; сортировка слиянием имеет отличную локальность ссылки
Пример [ править ]
В примерах значения { 6, 5, 3, 1, 8, 7, 2, 4 } сортируются в порядке возрастания с использованием обоих алгоритмов построения кучи. Сравниваемые элементы выделены жирным шрифтом. Обычно их бывает два при просеивании вверх и три при просеивании вниз, хотя при достижении вершины или низа дерева их может быть меньше.
Построение кучи (алгоритм Уильямса) [ править ]
| Куча | Несортированный | Поменять местами элементы |
|---|---|---|
| 6 | 5, 3, 1, 8, 7, 2, 4 | |
| 6 , 5 | 3, 1, 8, 7, 2, 4 | |
| 6 , 5, 3 | 1, 8, 7, 2, 4 | |
| 6, 5 , 3, 1 | 8, 7, 2, 4 | |
| 6, 5 , 3, 1, 8 | 7, 2, 4 | 5 ↔ 8 |
| 6 , 8 , 3, 1, 5 | 7, 2, 4 | 6 ↔ 8 |
| 8 , 6, 3, 1, 5 | 7, 2, 4 | |
| 8, 6, 3 , 1, 5, 7 | 2, 4 | 3 ↔ 7 |
| 8 , 6, 7 , 1, 5, 3 | 2, 4 | |
| 8, 6, 7 , 1, 5, 3, 2 | 4 | |
| 8, 6, 7, 1 , 5, 3, 2, 4 | 1 ↔ 4 | |
| 8, 6 , 7, 4 , 5, 3, 2, 1 |
Построение кучи (алгоритм Флойда) [ править ]
| Несортированный | Куча | Поменять местами элементы |
|---|---|---|
| 6, 5, 3, 1 | 8, 7, 2, 4 | |
| 6, 5, 3 | 1 , 8, 7, 2, 4 | 1 ↔ 4 |
| 6, 5, 3 | 4, 8, 7, 2, 1 | |
| 6, 5 | 3 , 4, 8, 7 , 2 , 1 | 3 ↔ 7 |
| 6, 5 | 7, 4, 8, 3 , 2, 1 | |
| 6 | 5 , 7, 4 , 8 , 3, 2, 1 | 5 ↔ 8 |
| 6 | 8, 7, 4, 5 , 3, 2, 1 | |
| 6 , 8 , 7 , 4, 5, 3, 2, 1 | 6 ↔ 8 | |
| 8, 6 , 7, 4 , 5 , 3, 2, 1 |
Извлечение кучи [ править ]
| Куча | Сортированный массив | Поменять местами элементы | Подробности |
|---|---|---|---|
| 8 , 6, 7, 4, 5, 3, 2, 1 | 8 ↔ 1 | Добавьте 8 в отсортированный массив, поменяв его местами на 1. | |
| 1 , 6 , 7 , 4, 5, 3, 2 | 8 | 1 ↔ 7 | Поменяйте местами 1 и 7, так как они не в порядке в куче. |
| 7, 6, 1 , 4, 5, 3 , 2 | 8 | 1 ↔ 3 | Поменяйте местами 1 и 3, так как они не в порядке в куче. |
| 7, 6, 3, 4, 5, 1 , 2 | 8 | 1 не имеет детей; siftDown завершен | |
| 7 , 6, 3, 4, 5, 1, 2 | 8 | 7 ↔ 2 | Добавьте 7 в отсортированный массив, поменяв его местами на 2. |
| 2 , 6 , 3 , 4, 5, 1 | 7, 8 | 2 ↔ 6 | Поменяйте местами 2 и 6, так как они не в порядке в куче. |
| 6, 2 , 3, 4 , 5 , 1 | 7, 8 | 2 ↔ 5 | Поменяйте местами 2 и 5, так как они не в порядке в куче. |
| 6, 5, 3, 4, 2 , 1 | 7, 8 | 2 не имеет детей; siftDown завершен | |
| 6 , 5, 3, 4, 2, 1 | 7, 8 | 6 ↔ 1 | Добавьте 6 в отсортированный массив, поменяв его местами на 1. |
| 1 , 5 , 3 , 4, 2 | 6, 7, 8 | 1 ↔ 5 | Поменяйте местами 1 и 5, так как они не в порядке в куче. |
| 5, 1 , 3, 4 , 2 | 6, 7, 8 | 1 ↔ 4 | Поменяйте местами 1 и 4, так как они не в порядке в куче. |
| 5, 5, 3, 1 , 2 | 6, 7, 8 | 1 не имеет детей; siftDown завершен | |
| 5 , 4, 3, 1, 2 | 6, 7, 8 | 5 ↔ 2 | Добавьте 5 в отсортированный массив, поменяв его местами на 2. |
| 2 , 4 , 3 , 1 | 5, 6, 7, 8 | 2 ↔ 4 | Поменяйте местами 2 и 4, так как они не в порядке в куче. |
| 4, 2 , 3, 1 | 5, 6, 7, 8 | 2 больше 1; siftDown завершен | |
| 4 , 2, 3, 1 | 5, 6, 7, 8 | Добавьте 4 в отсортированный массив, поменяв его местами на 1. | |
| 1 , 2 , 3 | 4, 5, 6, 7, 8 | 1 ↔ 3 | Поменяйте местами 1 и 3, так как они не в порядке в куче. |
| 3, 2, 1 | 4, 5, 6, 7, 8 | 1 не имеет детей; siftDown завершен | |
| 3 , 2, 1 | 4, 5, 6, 7, 8 | 1 ↔ 3 | Добавьте 3 в отсортированный массив, поменяв его местами на 1. |
| 1 , 2 | 3, 4, 5, 6, 7, 8 | 1 ↔ 2 | Поменяйте местами 1 и 2, так как они не в порядке в куче. |
| 2, 1 | 3, 4, 5, 6, 7, 8 | 1 не имеет детей; siftDown завершен | |
| 2 , 1 | 3, 4, 5, 6, 7, 8 | 2 ↔ 1 | Добавьте 2 в отсортированный массив, поменяв его местами на 1. |
| 1 | 2, 3, 4, 5, 6, 7, 8 | Добавить 1 в отсортированный массив | |
| 1, 2, 3, 4, 5, 6, 7, 8 | Завершенный |
Примечания [ править ]
- ^ Боллобас, Б.; Феннер, Техас; Фриз, AM (1996). «О лучшем случае пирамидальной сортировки» (PDF) . Журнал алгоритмов . 20 (11): 205–217. дои : 10.1006/jagm.1996.0011 .
- ^ Седжвик, Роберт ; Шаффер, Рассел В. (октябрь 1990 г.). Лучший случай пирамидальной сортировки (Технический отчет). Принстонский университет. ТР-293-90.
- ^ Скиена, Стивен (2008). «Поиск и сортировка». Руководство по разработке алгоритмов (3-е изд.). Спрингер. п. 116. дои : 10.1007/978-3-030-54256-6_4 . ISBN 978-3-030-54255-9 .
Обычное название этого алгоритма — пирамидальная сортировка — скрывает тот факт, что алгоритм представляет собой не что иное, как реализацию сортировки выбором с использованием правильной структуры данных.
- ^ Уильямс 1964
- ↑ Перейти обратно: Перейти обратно: а б Брасс, Питер (2008). Расширенные структуры данных . Издательство Кембриджского университета. п. 209. ИСБН 978-0-521-88037-4 .
- ^ Сученек, Марек А. (2012). «Элементарный, но точный анализ наихудшего случая программы Флойда по созданию кучи». Фундамента информатики . 120 (1): 75–92. дои : 10.3233/FI-2012-751 .
- ^ Сученек, Марек А. (7 апреля 2015 г.). «Полный анализ пирамидальной сортировки наихудшего случая с экспериментальной проверкой ее результатов, рукопись». arXiv : 1504.01459 [ cs.DS ].
- ^ Кнут 1997
- ↑ Перейти обратно: Перейти обратно: а б с Божесен, Йеспер; Катахайнен, Юрки; Спорк, Маз (2000). «Пример повышения производительности: конструкция кучи» (PostScript) . Журнал экспериментальной алгоритмики ACM . 5 (15): 15–с. CiteSeerX 10.1.1.35.3248 . дои : 10.1145/351827.384257 . S2CID 30995934 . Альтернативный источник PDF .
- ↑ Перейти обратно: Перейти обратно: а б с Вегенер, Инго (13 сентября 1993 г.). « ВНИЗОВАЯ HEAPSORT , новый вариант HEAPSORT , превосходящий в среднем QUICKSORT (если n не очень мало)» (PDF) . Теоретическая информатика . 118 (1): 81–98. дои : 10.1016/0304-3975(93)90364-у . Хотя это переиздание работы, впервые опубликованной в 1990 году (на конференции Mathematical Foundations of Computer Science), метод был опубликован Карлссоном в 1987 году. [16]
- ↑ Перейти обратно: Перейти обратно: а б с Флейшер, Рудольф (февраль 1994 г.). «Точная нижняя граница для худшего случая пирамидальной сортировки снизу вверх» (PDF) . Алгоритмика . 11 (2): 104–115. дои : 10.1007/bf01182770 . hdl : 11858/00-001M-0000-0014-7B02-C . S2CID 21075180 . Также доступен как Флейшер, Рудольф (апрель 1991 г.). Точная нижняя граница для наихудшего случая пирамидальной сортировки снизу вверх (PDF) (технический отчет). МПИ-ИНФ . МПИ-И-91-104.
- ↑ Перейти обратно: Перейти обратно: а б Мельхорн, Курт ; Сандерс, Питер (2008). «Приоритетные очереди» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов . Спрингер. п. 142. ИСБН 978-3-540-77977-3 .
- ↑ Перейти обратно: Перейти обратно: а б МакДиармид, CJH; Рид, бакалавр наук (сентябрь 1989 г.). «Быстрое строительство» (PDF) . Журнал алгоритмов . 10 (3): 352–365. дои : 10.1016/0196-6774(89)90033-3 .
- ↑ Перейти обратно: Перейти обратно: а б Маккей, Дэвид Дж. К. (декабрь 2005 г.). «Групповая сортировка, быстрая сортировка и энтропия» . Проверено 12 февраля 2021 г.
- ^ Море, Бернар ; Шапиро, Генри Д. (1991). «8.6 Пирамидальная сортировка». Алгоритмы от P до NP Том 1: Проектирование и эффективность . Бенджамин/Каммингс. п. 528. ИСБН 0-8053-8008-6 .
За неимением лучшего названия мы называем эту расширенную программу пирамидальной сортировкой с возвратом. '
- ↑ Перейти обратно: Перейти обратно: а б Карлссон, Сканте (март 1987 г.). «Вариант пирамидальной сортировки с почти оптимальным количеством сравнений» (PDF) . Письма об обработке информации . 24 (4): 247–250. дои : 10.1016/0020-0190(87)90142-6 . S2CID 28135103 . Архивировано из оригинала (PDF) 27 декабря 2016 года.
- ^ Вегенер, Инго (март 1992 г.). МакДиармида и Рида «Сложность в худшем случае варианта СНИЗУЮ СОРТИРОВКИ меньше n log n + 1,1 n » . Информация и вычисления . 97 (1): 86–96. дои : 10.1016/0890-5401(92)90005-Z .
- ^ Тененбаум, Аарон М.; Аугенштейн, Моше Дж. (1981). «Глава 8: Сортировка». Структуры данных с использованием Паскаля . Прентис-Холл. п. 405. ИСБН 0-13-196501-8 .
Напишите процедуру сортировки, аналогичную пирамидальной сортировке, за исключением того, что она использует троичную кучу.
- ↑ Перейти обратно: Перейти обратно: а б с ЛаМарка, Энтони; Ладнер, Ричард Э. (апрель 1999 г.). «Влияние кешей на производительность сортировки» (PDF) . Журнал алгоритмов . 31 (1): 66–104. CiteSeerX 10.1.1.456.3616 . дои : 10.1006/jagm.1998.0985 . S2CID 206567217 . См., в частности, рисунок 9c на стр. 98.
- ^ Чен, Цзинсен; Эделькамп, Стефан; Эльмасри, Амр; Катахайнен, Юрки (27–31 августа 2012 г.). «Построение кучи на месте с оптимизированными сравнениями, перемещениями и промахами в кэше» (PDF) . Математические основы информатики 2012 . 37-я международная конференция «Математические основы информатики». Конспекты лекций по информатике. Том. 7464. Братислава, Словакия. стр. 259–270. дои : 10.1007/978-3-642-32589-2_25 . ISBN 978-3-642-32588-5 . S2CID 1462216 . Архивировано из оригинала (PDF) 29 декабря 2016 г. См., в частности, рис. 3.
- ^ Кантоне, Доменико; Конкотти, Джанлука (1–3 марта 2000 г.). QuickHeapsort — эффективное сочетание классических алгоритмов сортировки . 4-я итальянская конференция по алгоритмам и сложности. Конспекты лекций по информатике. Том. 1767. Рим. стр. 150–162. ISBN 3-540-67159-5 .
- ^ Кантоне, Доменико; Конкотти, Джанлука (август 2002 г.). «QuickHeapsort, эффективное сочетание классических алгоритмов сортировки» (PDF) . Теоретическая информатика . 285 (1): 25–42. дои : 10.1016/S0304-3975(01)00288-2 . Збл 1016.68042 .
- ^ Дикерт, Волкер; Вайс, Армин (август 2016 г.). «QuickHeapsort: Модификации и улучшенный анализ». Теория вычислительных систем . 59 (2): 209–230. arXiv : 1209.4214 . дои : 10.1007/s00224-015-9656-y . S2CID 792585 .
- ^ Дейкстра, Эдсгер В. Smoothsort – альтернатива сортировке на месте (EWD-796a) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине . ( транскрипция )
- ^ Левкопулос, Христос; Петерссон, Ола (1989). «Групповая сортировка — адаптирована для предварительно отсортированных файлов». WADS '89: Материалы семинара по алгоритмам и структурам данных . Конспекты лекций по информатике. Том. 382. Лондон, Великобритания: Springer-Verlag. стр. 499–509. дои : 10.1007/3-540-51542-9_41 . ISBN 978-3-540-51542-5 . Пирамидальная сортировка — адаптирована для предварительно отсортированных файлов (Q56049336) .
- ^ Шварц, Кейт (27 декабря 2010 г.). "CartesianTreeSort.hh" . Архив интересного кода . Проверено 5 марта 2019 г.
- ^ Катахайнен, Юрки (23 сентября 2013 г.). В поисках очереди с лучшим приоритетом: извлеченные уроки . Алгоритмическая инженерия (семинар 13391). Дагштуль. стр. 19–20, 24.
- ^ Катахайнен, Юрки (2–3 февраля 1998 г.). Окончательная пирамидальная сортировка . Компьютерные технологии: 4-й Австралазийский теоретический симпозиум. Австралийские средства связи в области компьютерных наук . Том. 20, нет. 3. Перт. стр. 87–96.
- ^ Питерс, Орсон Р.Л. (9 июня 2021 г.). «Быстрая сортировка, побеждающая шаблон». arXiv : 2106.05123 [ cs.DS ].
Питерс, Орсон Р.Л. «pdqsort» . Гитхаб . Проверено 2 октября 2023 г. - ^ Моррис, Джон (1998). «Сравнение быстрой и пирамидальной сортировки» . Структуры данных и алгоритмы (Конспекты лекций). Университет Западной Австралии . Проверено 12 февраля 2021 г.
- ^ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Исходный код ядра Linux
- ^ Маус, Арне [на норвежском языке] (14 мая 2014 г.). «Сортировка путем создания перестановки сортировки и влияние кэширования на сортировку» . См. рис. 1 на с. 6.
Ссылки [ править ]
- Уильямс, JWJ (1964). «Алгоритм 232 – Пирамидальная сортировка». Коммуникации АКМ . 7 (6): 347–348. дои : 10.1145/512274.512284 .
- Флойд, Роберт В. (1964). «Алгоритм 245 — Сортировка дерева 3» . Коммуникации АКМ . 7 (12): 701. дои : 10.1145/355588.365103 . S2CID 52864987 .
- Карлссон, Сванте [на шведском языке] (1987). «Средние результаты пирамидальной сортировки». БИТ Численная математика . 27 (1): 2–17. дои : 10.1007/bf01937350 . S2CID 31450060 .
- Кнут, Дональд (1997). «§5.2.3, Сортировка по выбору». Искусство компьютерного программирования . Том. 3: Сортировка и поиск (3-е изд.). Аддисон-Уэсли. стр. 144–155. ISBN 978-0-201-89685-5 .
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03293-7 . Главы 6 и 7 соответственно: пирамидальная сортировка и очереди по приоритетам
- PDF-файл оригинальной статьи Дейкстры о Smoothsort
- Учебное пособие по кучам и пирамидальной сортировке , Дэвид Карлсон, Колледж Сент-Винсент
Внешние ссылки [ править ]
- Анимированные алгоритмы сортировки: сортировка кучей на Wayback Machine (архивировано 6 марта 2015 г.) - графическая демонстрация
- Курсы по пирамидальной сортировке от Univ. Ольденбург – с текстом, анимацией и интерактивными упражнениями.
- Словарь алгоритмов и структур данных NIST: пирамидальная сортировка
- Пирамидальная сортировка реализована на 12 языках.
- К вопросу о сортировке Пола Се
- Презентация PowerPoint, демонстрирующая работу пирамидальной сортировки , предназначенная для преподавателей.
- Структуры открытых данных – Раздел 11.1.3 – Куча-сортировка , Пэт Морин