Сортировка массива с использованием алгоритма пирамидальной сортировки

Сортировка массива с использованием алгоритма пирамидальной сортировки

Пирамидальная сортировка (англ. Heapsort , «Сортировка кучей» [1] ) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов. [2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

Содержание

История создания [ править | править код ]

Пирамидальная сортировка была предложена Дж. Уильямсом [en] в 1964 году. [1]

Алгоритм [ править | править код ]

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

  1. Каждый лист имеет глубину либо d <displaystyle d>, либо d − 1 <displaystyle d-1>, d <displaystyle d>— максимальная глубина дерева.
  2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array , что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2] .

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева [ источник не указан 1166 дней ] :

Array [ i ] ≥ Array [ 2 i + 1 ] <displaystyle < ext>[i]geq < ext>[2i+1]>

Array [ i ] ≥ Array [ 2 i + 2 ] <displaystyle < ext>[i]geq < ext>[2i+2]>

при 0 ≤ i n / 2 <displaystyle 0leq i .

Этот шаг требует O ( n ) <displaystyle O(n)> операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[0] и Array[n-1] , преобразовываем Array[0] , Array[1] , … , Array[n-2] в сортирующее дерево. Затем переставляем Array[0] и Array[n-2] , преобразовываем Array[0] , Array[1] , … , Array[n-3] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[0] , Array[1] , … , Array[n-1] — упорядоченная последовательность.

Этот шаг требует O ( n log ⁡ n ) <displaystyle O(nlog n)> операций.

Достоинства и недостатки [ править | править код ]

  • Имеет доказанную оценку худшего случая O ( n ⋅ log ⁡ n ) <displaystyle O(ncdot log n)>.
  • Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).
  • Неустойчив — для обеспечения устойчивости нужно расширять ключ.
  • На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
  • На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
  • Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.
  • Не распараллеливается.
Читайте также:  Fifa 19 uefa champions league

Сортировка слиянием при расходе памяти O(n) быстрее ( O ( n ⋅ log ⁡ n ) <displaystyle O(ncdot log n)> с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Применение [ править | править код ]

Алгоритм «сортировка кучей» активно применяется в ядре Linux.

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

Пирамидой ( кучей ) называется двоичное дерево такое, что

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

Подробнее

a[0] — минимальный элемент пирамиды.

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

Выполнение алгоритма разбивается на два этапа.

1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.

Например, массив для сортировки

24, 31, 15, 20, 52, 6

Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.

Результат просеивания элемента 15 через пирамиду.

Следующий просеиваемый элемент – 1, равный 31.

Затем – элемент 0, равный 24.

Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.

2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.

Продолжим процесс. В итоге массив будет отсортирован по убыванию.

Реализация пирамидальной сортировки на Си

Анализ алгоритма пирамидальной сортировки

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log2n шагов, сдвигающих элементы. Среднее число перемещений примерно равно

и отклонения от этого значения относительно невелики.

В некоторых приложениях (например, в задачах управления оборудованием в реальном времени) крайне важно иметь гарантию, что время работы критических ветвей программы даже в самом плохом случае не превысит некоторой заданной величины. Для таких задач использование QuickSort может оказаться неприемлемым ввиду названного выше недостатка этого алгоритма – времени работы порядка O(n 2 ) в худшем случае. В этой ситуации следует использовать такой алгоритм, который работает гарантированно быстро даже в худшем случае.

Читайте также:  Slim framework на русском

Наиболее известным из таких алгоритмов является HeapSort, который по-русски принято называть пирамидальной сортировкой.

В основе алгоритма лежит понятие пирамиды.

Массив A называется пирамидой, если для всех его элементов выполнены следующие неравенства:

(3.1)

Смысл неравенств (3.1) можно наглядно пояснить на рис. 3.1.

Рис. 3.1. Представление пирамиды в виде дерева

На рисунке массив-пирамида из 10 элементов изображен в виде сбалансированного бинарного дерева, вершины которого пронумерованы сверху вниз и слева направо. При этом элемент ak всегда будет в дереве «отцом» элементов a2k и a2k+1 (если такие элементы имеются). Тогда неравенства (3.1) означают, что значение «отца» должно быть не меньше, чем значения каждого из «сыновей».

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

Пирамида вовсе не обязательно является сортированным массивом, однако она служит удобным промежуточным результатом при сортировке. Отметим, что первый элемент пирамиды (a1) всегда является максимальным элементом массива.

Работа алгоритма HeapSort состоит из двух последовательных фаз. На первой фазе исходный массив перестраивается в пирамиду, а на второй фазе из пирамиды строится сортированный массив.

Основной операцией, используемой как на первой, так и на второй фазах сортировки, является так называемое просеивание элемента сквозь пирамиду.

Предположим, что неравенства (3.1) выполнены для элементов пирамиды, начиная с индекса k+1 (т.е. для элементов ak+1, ak+2, … , an). Процедура просеивания элемента ak должна обеспечить выполнение (3.1) для ak и при этом не нарушить этих неравенств для ak+1, ak+2, … , an.

Алгоритм просеивания заключается в следующем.

1. Если ak не имеет сыновей (т.е. 2k > n), то просеивание закончено.

2. Если ak имеет ровно одного сына (т.е. 2k = n), то присвоить l := n и перейти к шагу 4.

3. Сравнить значения двух сыновей вершины ak: если a2k > a2k+1, то l := 2k, иначе l := 2k + 1 (т.е. l – это индекс большего из сыновей ak).

4. Сравнить значения элемента ak со значением его большего сына al: если ak

4. Если n > 1, то перейти к шагу 1, иначе сортировка завершена.

Читайте также:  Мотивация картинки с цитатами

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

Оценим время работы каждой фазы алгоритма HeapSort. Первая фаза состоит из n/2 операций просеивания, каждая из которых включает не более log2(n) итераций цикла. Отсюда можем легко получить для первой фазы оценку Tмакс(n) = O(n×log(n)). Однако эта оценка чересчур грубая. В дальнейшем нам понадобится более точная оценка времени работы первой фазы HeapSort. Чтобы получить такую оценку, рассмотрим рис. 3.2.

Рис. 3.2. Число итераций просеивания при построении пирамиды

Из числа всех n элементов массива A примерно половина (n/2) не имеет сыновей и не требует просеивания (т.е. число итераций просеивания равно 0). Четверть элементов (n/4) имеет сыновей, но не имеет внуков, для этих элементов может быть выполнено не больше одной итерации просеивания. Для одной восьмой части элементов (n/8) могут быть выполнены две итерации, для одной шестнадцатой (n/16) – три итерации и т.д. Суммарное число итераций просеивания определится формулой: n (0×1/2 + 1×1/4 + 2×1/8 + 3×1/16 + …). Тряхнув воспоминаниями о матанализе, можно вычислить значение суммы ряда в скобках; это значение равно 1. Таким образом, получаем линейную оценку времени для первой фазы: Tмакс(n) = O(n).

Вторая фаза алгоритма в основном представляет собой просеивание элементов сквозь уменьшающуюся пирамиду. Число итераций цикла можно примерно оценить как сумму log2(n) + log2(n–1) + log2(n–2) + … + log2(3) + log2(3). Поверим без доказательства, что с точностью до O-большого эта сумма дает Tмакс(n) = O(n×log(n)).

Время работы алгоритма в целом определяется более трудоемкой второй фазой и удовлетворяет оценке Tмакс(n) = O(n×log(n)). Можно доказать, что такая же оценка справедлива и для среднего времени сортировки: Tср(n) = O(n×log(n)). Таким образом, HeapSort представляет собой алгоритм сортировки, который гарантирует достаточно быструю работу даже в случае самых неудачных исходных данных. Этим HeapSort выгодно отличается от QuickSort, который такой гарантии не дает. С другой стороны, практика показывает, что в среднем алгоритм HeapSort работает примерно вдвое медленнее, чем QuickSort.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8556 — | 7410 — или читать все.

Ссылка на основную публикацию
Adblock detector