stringtranslate.com

пирамидальная сортировка

В информатике пирамидальная сортировка — это алгоритм сортировки на основе сравнения , который можно рассматривать как «реализацию сортировки выбором с использованием правильной структуры данных ». [3] Подобно сортировке выбором, пирамидальная сортировка делит входные данные на отсортированную и несортированную область и итеративно сжимает неотсортированную область, извлекая из нее самый большой элемент и вставляя его в отсортированную область. В отличие от сортировки выбором, пирамидальная сортировка не тратит время на сканирование несортированной области в линейном времени; скорее, пирамидальная сортировка сохраняет несортированную область в структуре данных кучи , чтобы эффективно находить самый большой элемент на каждом этапе.

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

Пирамидная сортировка была изобретена Дж. Уильямсом в 1964 году. [4] В статье также была представлена ​​двоичная куча как самостоятельная полезная структура данных. [5] В том же году Роберт Флойд опубликовал улучшенную версию, которая могла сортировать массив на месте, продолжив свои более ранние исследования алгоритма сортировки деревьев . [5]

Обзор

Алгоритм пирамидальной сортировки можно разделить на два этапа: построение кучи и извлечение кучи.

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

 iLeftChild(i) = 2⋅i + 1 iRightChild(i) = 2⋅i + 2 iParent(i) = пол((i−1)/2)

где функция пола округляет до предыдущего целого числа. Более подробное объяснение см. в разделе «Двоичная куча § Реализация кучи» .

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

На первом этапе из данных создается куча (см. Двоичная куча § Построение кучи ).

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

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

Алгоритм

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

Шаги:

  1. Вызовите heapify()функцию в массиве. Это создает кучу из массива за O ( n ) операций.
  2. Поменяйте местами первый элемент массива (самый большой элемент в куче) с последним элементом кучи. Уменьшите рассматриваемый диапазон кучи на единицу.
  3. Вызовите siftDown()функцию массива, чтобы переместить новый первый элемент в правильное место в куче.
  4. Возвращайтесь к шагу (2), пока оставшийся массив не станет одним элементом.

Операция heapify()запускается один раз и имеет производительность O ( n ) . Функция siftDown()вызывается n раз и каждый раз требует O (log n ) работы из-за ее обхода, начиная с корневого узла. Следовательно, производительность этого алгоритма равна O ( n + n log n ) = O ( n log n ) .

Сердцем алгоритма является siftDown()функция. Это создает двоичные кучи из меньших куч и может рассматриваться двумя эквивалентными способами:

Чтобы установить свойство max-heap в корне, необходимо сравнить до трех узлов (корень и два его дочерних узла), а самый большой из них должен быть сделан корнем. Это проще всего сделать, найдя наибольший дочерний элемент и затем сравнив его с корнем. Есть три случая:

  1. Если дочерних элементов нет (две исходные кучи пусты), свойство кучи тривиально сохраняется и никаких дальнейших действий не требуется.
  2. Если root больше или равен наибольшему дочернему элементу, свойство кучи сохраняется, и никаких дальнейших действий не требуется.
  3. Если корень меньше наибольшего дочернего узла, поменяйте местами два узла. Свойство кучи теперь сохраняется на вновь повышенном узле (оно больше или равно обоим его дочерним элементам и фактически больше, чем любой потомок), но может быть нарушено между недавно пониженным экс-корнем и его новыми дочерними элементами. Чтобы исправить это, повторите siftDown()операцию с поддеревом, корнем которого является недавно пониженный в должности бывший корень.

Количество итераций в любом siftdown()вызове ограничено высотой дерева, которая равна ⌊ log 2 n ⌋ = O (log n ) .

Псевдокод

Ниже приведен простой способ реализации алгоритма в псевдокоде . Массивы начинаются с нуля и swapиспользуются для обмена двумя элементами массива. Движение «вниз» означает от корня к листьям или от нижних индексов к более высоким. Обратите внимание, что во время сортировки самый большой элемент находится в корне кучи в a[0], а в конце сортировки самый большой элемент находится в a[end].

Вводится  процедура heapsort(a, count) : неупорядоченный массив a длиной count  (Постройте кучу в массиве a так, чтобы наибольшее значение было в корне) heapify(a, count) (Следующий цикл поддерживает инварианты , согласно которым a[0:end-1] является кучей, и  каждый элемент a[end:count-1] за end больше, чем все, что находится перед ним,  т. е. a[end:count-1] в отсортированном порядке.) конец ← счет while end > 1 do  (размер кучи уменьшается на единицу) конец ← конец − 1 (a[0] — это корневое и наибольшее значение. При обмене оно перемещается перед отсортированными элементами.) своп(а[конец], а[0]) (своп разрушил свойство кучи, поэтому восстановите его) siftDown(а, 0, конец)

Процедура сортировки использует две подпрограммы heapify: siftDown. Первая — это обычная процедура построения кучи на месте, а вторая — обычная подпрограмма для реализации heapify.

( Помещайте элементы 'a' в порядке кучи , на  месте ) найдите родителя этого элемента)  начало ← iParent(count-1) + 1  while start > 0 do  (перейти к последнему узлу без кучи) старт ← старт − 1 (отсеивайте узел с индексом «start» в нужное место, чтобы все узлы ниже  начального индекса находились в куче) siftDown(а, начало, счет) (после просеивания корня все узлы/элементы располагаются в куче) ( Восстановить кучу, корневой элемент которой находится в индексе «start», предполагая, что кучи, корни которых лежат в ее дочерних элементах , действительны )  дочерний) дочерний ← iLeftChild(root) (Левый дочерний элемент корня) (Если есть правый дочерний элемент и этот дочерний элемент больше), если child+1 < end и a[child] < a[child+1] тогда    ребенок ← ребенок + 1  если a[корень] <a[ребёнок] , то своп(а[корень], а[дочерний]) root ← дочерний элемент (повторите, чтобы продолжить сортировку дочернего элемента)  else  (Корень содержит самый большой элемент. Поскольку мы можем предположить, что кучи, укорененные  в дочерних элементах, действительны, это означает, что мы закончили.)  return

Процедура 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, и массив не будет полностью отсортирован.

Вводится  процедура heapsort(a, count) : неупорядоченный массив a длиной count  начало ← этаж(кол/2) конец ← счет while end > 1, do  if start > 0 then  (построение кучи) старт ← старт − 1 else  (извлечение кучи) конец ← конец − 1 своп(а[конец], а[0])  (Далее siftDown(a, start, end)) корень ← начало в то время как iLeftChild(root) <end do дочерний элемент ← iLeftChild(корень) (Если есть правильный дочерний элемент и этот дочерний элемент больше),  если child+1 < end и a[child] < a[child+1] , тогда ребенок ← ребенок + 1  если a[корень] <a[ребёнок] , то своп(а[корень], а[дочерний]) root ← дочерний элемент (повторите, чтобы продолжить сортировку дочернего элемента)  else  Break  (возврат во внешний цикл)

Вариации

Конструкция кучи Уильямса

В приведенном выше описании используется улучшенный алгоритм построения кучи Флойда, который работает за время O ( n ) и использует тот же siftDownпримитив, что и фаза извлечения кучи. Хотя этот алгоритм, будучи более быстрым и простым в программировании, используется во всех практических реализациях пирамидальной сортировки, исходный алгоритм Уильямса может быть проще для понимания и необходим для реализации более общей очереди с приоритетами двоичной кучи .

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

 Вводится  процедура siftUp(a, end) :  a — это массив, упорядоченный в куче до конца-1.  end — это узел для сортировки.  в то время как конец > 0 родитель:= iParent(конец) если a[parent] < a[end] тогда  (вне максимального порядка кучи) своп(а[родительский], а[конец]) end := родительский (продолжить сортировку)  else  return  процедура heapify(a, count) ( начните  с тривиальной одноэлементной кучи) конец := 1  while end < count (отсеять узел в конце индекса в нужное место так, чтобы  все узлы выше конечного индекса находились в куче) siftUp(а, конец) конец := конец + 1 (после просеивания последнего узла все узлы располагаются в куче)
Разница во временной сложности между версиями «siftDown» и «siftUp».

Чтобы понять, почему этому алгоритму может потребоваться асимптотически больше времени для построения кучи ( 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]

функция LeafSearch(a, i, end ) j ← я while iRightChild(j) < end do  (Определите, какой из двух дочерних элементов j является большим),  если a[iRightChild(j)] > a[iLeftChild(j)] , то j ← iRightChild(j) еще j ← iLeftChild(j) (На последнем уровне может быть только один дочерний элемент),  если iLeftChild(j) < end then j ← iLeftChild(j) вернуть j

Возвращаемое значение leafSearchиспользуется в модифицированной siftDownпроцедуре: [11]

процедура siftDown(a, i, end ) j ← LeafSearch(a, i, end) в то время как a[i] > a[j] делают j ← iParent(j) пока j > я делаю своп(а[i], а[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]

Другие варианты

Сравнение с другими сортами

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

Основными преимуществами пирамидальной сортировки являются ее простой, нерекурсивный код , минимальные требования к дополнительной памяти и надежно высокая производительность: ее лучшие и худшие случаи находятся в пределах небольшого постоянного коэффициента друг от друга и теоретической нижней границы сортировок сравнения . Хотя он не может работать лучше, чем O ( n log n ) для предварительно отсортированных входных данных, он также не страдает от худшего случая быстрой сортировки O ( n 2 ) .

Реальные реализации быстрой сортировки используют различные эвристики , чтобы избежать наихудшего случая, но это делает их реализацию намного более сложной, а такие реализации, как интросорт и быстрая сортировка с отклонением шаблона [29], используют пирамидальную сортировку в качестве запасного варианта в качестве запасного варианта в случае обнаружения вырождения. поведение. Таким образом, их производительность в худшем случае немного хуже, чем если бы пирамидальная сортировка использовалась с самого начала.

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

Гарантии производительности в наихудшем случае делают пирамидальную сортировку популярной в вычислениях в реальном времени и в системах, связанных со злонамеренно выбранными входными данными [30], таких как ядро ​​Linux. [31] Сочетание небольшой реализации и надежной «достаточно хорошей» производительности делает его популярным во встроенных системах и вообще в любых приложениях, где сортировка не является узким местом производительности . Например, пирамидальная сортировка идеально подходит для сортировки списка имен файлов для отображения, но система управления базами данных , вероятно, потребует более агрессивно оптимизированного алгоритма сортировки.

Хорошо реализованная быстрая сортировка обычно в 2–3 раза быстрее пирамидальной сортировки. [19] [32] Хотя быстрая сортировка требует меньшего количества сравнений, это несущественный фактор. (Результаты, требующие вдвое большего количества сравнений, измеряют версию сверху вниз; см. § пирамидальную сортировку снизу вверх.) Основное преимущество быстрой сортировки - ее гораздо лучшая локальность ссылки: разделение представляет собой линейное сканирование с хорошей пространственной локальностью, а рекурсивное подразделение имеет хорошую временную локальность. При дополнительных усилиях быстрая сортировка также может быть реализована в коде, в основном не имеющем ветвей , [33] [34] , а для параллельной сортировки подразделов можно использовать несколько процессоров. Таким образом, быстрая сортировка предпочтительна, когда дополнительная производительность оправдывает усилия по реализации.

Другой основной алгоритм сортировки O ( n log n ) — это сортировка слиянием , но он редко напрямую конкурирует с пирамидальной сортировкой, поскольку не выполняется на месте. Требование сортировки слиянием к дополнительному пространству Ω( n ) (примерно половина размера входных данных) обычно непомерно велико, за исключением ситуаций, когда сортировка слиянием имеет явное преимущество:

Пример

В примерах значения { 6, 5, 3, 1, 8, 7, 2, 4 } сортируются в порядке возрастания с использованием обоих алгоритмов построения кучи. Сравниваемые элементы выделены жирным шрифтом. Обычно их два при просеивании вверх и три при просеивании вниз, хотя при достижении вершины или низа дерева их может быть меньше.

Построение кучи (алгоритм Уильямса)

Пример пирамидальной сортировки с использованием алгоритма построения кучи Уильямса.

Построение кучи (алгоритм Флойда)

Извлечение кучи

Примечания

  1. ^ Боллобас, Б.; Феннер, Техас; Фриз, AM (1996). «О лучшем случае пирамидальной сортировки» (PDF) . Журнал алгоритмов . 20 (11): 205–217. дои : 10.1006/jagm.1996.0011.
  2. ^ Седжвик, Роберт ; Шаффер, Рассел В. (октябрь 1990 г.). Лучший случай пирамидальной сортировки (Технический отчет). Университет Принстон. ТР-293-90.
  3. ^ Скиена, Стивен (2008). «Поиск и сортировка». Руководство по разработке алгоритмов (3-е изд.). Спрингер. п. 116. дои : 10.1007/978-3-030-54256-6_4. ISBN 978-3-030-54255-9. Обычное название этого алгоритма — пирамидальная сортировка — скрывает тот факт, что алгоритм представляет собой не что иное, как реализацию сортировки выбором с использованием правильной структуры данных.
  4. ^ Уильямс 1964
  5. ^ Аб Брасс, Питер (2008). Расширенные структуры данных . Издательство Кембриджского университета. п. 209. ИСБН 978-0-521-88037-4.
  6. ^ Сученек, Марек А. (2012). «Элементарный, но точный анализ наихудшего случая программы Флойда по созданию кучи». Фундамента информатика . 120 (1): 75–92. дои : 10.3233/FI-2012-751.
  7. ↑ Сученек, Марек А. (7 апреля 2015 г.). «Полный анализ пирамидальной сортировки наихудшего случая с экспериментальной проверкой ее результатов, рукопись». arXiv : 1504.01459 [cs.DS].
  8. ^ Кнут 1997
  9. ^ abc Божесен, Йеспер; Катахайнен, Юрки; Спорк, Маз (2000). «Пример повышения производительности: конструкция кучи» (PostScript) . Журнал экспериментальной алгоритмики ACM . 5 (15): 15–с. CiteSeerX 10.1.1.35.3248 . дои : 10.1145/351827.384257. S2CID  30995934. Альтернативный источник PDF.
  10. ^ abc Wegener, Инго (13 сентября 1993 г.). «ВЫСТРОИТЕЛЬНАЯ СОРТИРОВКА СНИЗУ, новый вариант HEAPSORT, превосходящий в среднем БЫСТРУЮ СОРТИРОВКУ (если n не очень мало)» (PDF) . Теоретическая информатика . 118 (1): 81–98. дои : 10.1016/0304-3975(93)90364-у .Хотя это переиздание работы, впервые опубликованной в 1990 году (на конференции Mathematical Foundations of Computer Science), методика была опубликована Карлссоном в 1987 году. [16]
  11. ^ abc Флейшер, Рудольф (февраль 1994 г.). «Точная нижняя граница для худшего случая пирамидальной сортировки снизу вверх» (PDF) . Алгоритмика . 11 (2): 104–115. дои : 10.1007/bf01182770. hdl : 11858/00-001M-0000-0014-7B02-C . S2CID  21075180.Также доступен как Фляйшер, Рудольф (апрель 1991 г.). Точная нижняя граница для наихудшего случая пирамидальной сортировки снизу вверх (PDF) (технический отчет). МПИ-ИНФ . МПИ-И-91-104.
  12. ^ аб Мельхорн, Курт ; Сандерс, Питер (2008). «Приоритетные очереди» (PDF) . Алгоритмы и структуры данных: базовый набор инструментов. Спрингер. п. 142. ИСБН 978-3-540-77977-3.
  13. ^ аб МакДиармид, CJH; Рид, бакалавр наук (сентябрь 1989 г.). «Быстрое строительство» (PDF) . Журнал алгоритмов . 10 (3): 352–365. дои : 10.1016/0196-6774(89)90033-3.
  14. ^ Аб Маккей, Дэвид Дж. К. (декабрь 2005 г.). «Групповая сортировка, быстрая сортировка и энтропия» . Проверено 12 февраля 2021 г.
  15. ^ Море, Бернар ; Шапиро, Генри Д. (1991). «8.6 Пирамидальная сортировка». Алгоритмы от P до NP Том 1: Проектирование и эффективность . Бенджамин/Каммингс. п. 528. ИСБН 0-8053-8008-6. За неимением лучшего названия мы называем эту расширенную программу пирамидальной сортировкой с возвратом. '
  16. ^ аб Карлссон, Сканте (март 1987 г.). «Вариант пирамидальной сортировки с почти оптимальным количеством сравнений» (PDF) . Письма об обработке информации . 24 (4): 247–250. дои : 10.1016/0020-0190(87)90142-6. S2CID  28135103. Архивировано из оригинала (PDF) 27 декабря 2016 года.
  17. ^ Вегенер, Инго (март 1992 г.). «Сложность варианта МакДиармида и Рида СНИЗУЮ-ВВЕРХ составляет менее n log n + 1,1n». Информация и вычисления . 97 (1): 86–96. дои : 10.1016/0890-5401(92)90005-Z .
  18. ^ Тененбаум, Аарон М.; Аугенштейн, Моше Дж. (1981). «Глава 8: Сортировка». Структуры данных с использованием Паскаля . Прентис-Холл. п. 405. ИСБН 0-13-196501-8. Напишите процедуру сортировки, аналогичную пирамидальной сортировке, за исключением того, что она использует троичную кучу.
  19. ^ abc Ламарка, Энтони; Ладнер, Ричард Э. (апрель 1999 г.). «Влияние кешей на производительность сортировки» (PDF) . Журнал алгоритмов . 31 (1): 66–104. CiteSeerX 10.1.1.456.3616 . дои : 10.1006/jagm.1998.0985. S2CID  206567217. См., в частности, рисунок 9c на стр. 98.
  20. ^ Чен, Цзинсен; Эделькамп, Стефан; Эльмасри, Амр; Катахайнен, Юрки (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.
  21. ^ Кантоне, Доменико; Конкотти, Джанлука (1–3 марта 2000 г.). QuickHeapsort — эффективное сочетание классических алгоритмов сортировки. 4-я итальянская конференция по алгоритмам и сложности. Конспекты лекций по информатике. Том. 1767. Рим. стр. 150–162. ISBN 3-540-67159-5.
  22. ^ Кантоне, Доменико; Конкотти, Джанлука (август 2002 г.). «QuickHeapsort, эффективное сочетание классических алгоритмов сортировки» (PDF) . Теоретическая информатика . 285 (1): 25–42. дои : 10.1016/S0304-3975(01)00288-2 . Збл  1016.68042.
  23. ^ Дикерт, Волкер; Вайс, Армин (август 2016 г.). «QuickHeapsort: Модификации и улучшенный анализ». Теория вычислительных систем . 59 (2): 209–230. arXiv : 1209.4214 . doi : 10.1007/s00224-015-9656-y. S2CID  792585.
  24. ^ Дейкстра, Эдсгер В. Smoothsort - альтернатива сортировке на месте (EWD-796a) (PDF) . Архив Э. В. Дейкстры. Центр американской истории Техасского университета в Остине .(транскрипция)
  25. ^ Левкопулос, Христос; Петерссон, Ола (1989). «Групповая сортировка — адаптирована для предварительно отсортированных файлов». WADS '89: Материалы семинара по алгоритмам и структурам данных . Конспекты лекций по информатике. Том. 382. Лондон, Великобритания: Springer-Verlag. стр. 499–509. дои : 10.1007/3-540-51542-9_41. ISBN 978-3-540-51542-5.Heapsort — адаптирован для предварительно отсортированных файлов (Q56049336).
  26. ↑ Шварц, Кейт (27 декабря 2010 г.). «CartesianTreeSort.hh». Архив интересного кода . Проверено 5 марта 2019 г.
  27. ^ Катаджайнен, Юрки (23 сентября 2013 г.). В поисках очереди с лучшим приоритетом: извлеченные уроки. Алгоритмическая инженерия (семинар 13391). Дагштуль. стр. 19–20, 24.
  28. ^ Катаджайнен, Юрки (2–3 февраля 1998 г.). Окончательная пирамидальная сортировка. Компьютерные технологии: 4-й Австралазийский теоретический симпозиум. Австралийские коммуникации в области компьютерных наук . Том. 20, нет. 3. Перт. стр. 87–96.
  29. ↑ Питерс, Орсон Р.Л. (9 июня 2021 г.). «Быстрая сортировка, побеждающая шаблон». arXiv : 2106.05123 [cs.DS].
    Питерс, Орсон Р.Л. «pdqsort». Гитхаб . Проверено 2 октября 2023 г.
  30. ^ Моррис, Джон (1998). «Сравнение быстрой и пирамидальной сортировки». Структуры данных и алгоритмы (Конспекты лекций). Университет Западной Австралии . Проверено 12 февраля 2021 г.
  31. ^ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Исходный код ядра Linux
  32. ↑ Маус, Арне [на норвежском языке] (14 мая 2014 г.). «Сортировка путем создания перестановки сортировки и влияние кэширования на сортировку».См. рис. 1 на с. 6.
  33. ^ Эделькамп, Стефан; Вайс, Армин (30 января 2019 г.). «BlockQuicksort: предотвращение неправильных предсказаний ветвей при быстрой сортировке» (PDF) . Журнал экспериментальной алгоритмики . 24 1.4. arXiv : 1604.06697 . дои : 10.1145/3274660.
  34. ^ Аумюллер, Мартин; Хасс, Николай (7–8 января 2019 г.). Простая и быстрая блочная быстрая сортировка с использованием схемы секционирования Ломуто. Двадцать первый семинар по разработке алгоритмов и экспериментам (ALENEX). Сан Диего. arXiv : 1810.12047 . дои : 10.1137/1.9781611975499.2 .

Рекомендации

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

В реализации алгоритма Wikibook есть страница на тему: пирамидальная сортировка.