Блок схема пирамидальной сортировки

Блок схема пирамидальной сортировки

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

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

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 шагов, сдвигающих элементы. Среднее число перемещений примерно равно

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

1. Полагаем

Рассмотрим механизм деления массива, выбрав в качестве эталона элемент .

1. Полагаем i = L (левая граница массива), j = R (правая граница массива).

2. Увеличиваем i до тех пор, пока не найдем элемент a[i] ≥ x.

3. Уменьшаем j до тех пор, пока не найдем элемент a[j] ≤ x.

4. Если ij, меняем местами элементы a[i] и a[j], увеличиваем i и уменьшаем j на 1.

5. Если ij, идем на шаг 2.

Теперь в части a[L], …, a[j] собраны все элементы, меньшие либо равные эталону x, а в части a[i], …, a[R] – все элементы, большие либо равные эталону. Далее этот же алгоритм применяем для массивов a[L], …, a[j] и a[i], …, a[R], то есть алгоритм является рекурсивным.

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

m = (0 + 9) / 2 = 9 / 2 = 4

i j
i j
i j
i j
i j
i j
j i

Теперь повторим действия для левой и правой частей массива.

m = (0+4)/2 = 2 m = (5+9)/2 = 7
i j i j
i j i j
i=j i=j
j i j i

Далее рекурсивно повторяем те же действия (уже для четырех частей массива)

m = (0+2)/2 = 1 m = (3+4)/2 = 3 m = (5+7)/2 = 6 m = (8+9)/2 = 8
i j i j i j i j
i j i j i j i j
j i j i j i j i

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

Читайте также:  Как переименовать песню в вк с телефона
m = (0+1)/2 = 0 m = (5+6)/2 = 5
i j i j
i=j i=j
j i j i

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

Алгоритм Хоара

1. i = L, j = R,

2. Полагаем i = L (левая граница массива), j = R (правая граница массива).

3. Увеличиваем i до тех пор, пока не найдем элемент a[i] ≥ x.

4. Увеличиваем j до тех пор, пока не найдем элемент a[j] ≤ x.

5. Если ij, меняем местами элементы a[i] и a[j], увеличиваем i и уменьшаем j на 1.

6. Если ij, идем на шаг 2.

7. Если L i, полагаем L = i и идем на шаг 1.

Блок-схема сортировки Хоара

Теперь поговорим о выборе эталона x. Сам Хоар предполагал, что выбор элемента для сравнения должен быть случайным. В нашем случае мы выбирали средний элемент. Однако почти с тем же успехом можно выбирать первый или последний элементы. В этих случаях хуже всего будет, если массив окажется первоначально уже упорядочен.

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

В лучшем случае общее число сравнений равно C = N log2 (N), а общее число обменов . Средняя производительность алгоритма быстрой сортировки при случайном выборе эталона обличается от оптимального случая лишь коэффициентом 2 log2(2). Наихудшая производительность алгоритма будет порядка N 2 .

Однако быстрой сортировке присущи некоторые недостатки. Главный из них – плохая производительность при небольших N, впрочем, это недостаток всех усовершенствованных методов. Но перед другими усовершенствованными методами этот алгоритм имеет то преимущество, что для обработки небольших частей (например, когда (RL) i, разбиение массива закончено. Он распадается на два массива:

91 11 42 92 70 43 и 144 217 191 181

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

левая часть ссылка1 правая часть ссылка2

L=0 i
R=5 j
L=0 i
R=5 j
L=0
i
j
R=5
L=0
j
i
R=5

Здесь j > i, массив распадается на два массива:

43 42 и 111 92 70 91

левая часть ссылка11 правая часть ссылка12

L=0 i
R=1 j
j
L=0
R=1 i

Здесь j > i, индекс j вышел за границу массива. Это произошло потому, что все элементы в пятом бите содержат единицу. В этом случае массив не распадается на два массива, то есть не меняется. Процедура вызывается рекурсивно для того же массива и следующего бита.

L=0 i
R=1 j
L=0 j
R=1
i

Здесь j > i, индекс i вышел за границу массива. Это произошло потому, что все элементы в четвертом бите содержат ноль. В этом случае тот же массив разбивается по следующему биту.

Читайте также:  Windows 10 интересное не работает

Для следующих трех битов разбиения также не происходит (приведем здесь только окончательные значения индексов i и j).

j
L=0
R=1 i
L=0 j
R=1
i
j
L=0
R=1 i

Рассмотрим разбиение по нулевому биту:

L=0 i
R=1 j
L=0 i
R=1 j
L=0 j
R=1 i

Произведено разбиение по последнему биту, значит, сортировка данной части исходного массива закончена.

Последнее изменение этой страницы: 2017-02-08; Нарушение авторского права страницы

Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».

Пирамидальная сортировка (или сортировка кучей, HeapSort) — это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча. Она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов.

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

Двоичная куча — это законченное двоичное дерево, в котором элементы хранятся в особом порядке: значение в родительском узле больше (или меньше) значений в его двух дочерних узлах. Первый вариант называется max-heap, а второй — min-heap. Куча может быть представлена двоичным деревом или массивом.

Поскольку двоичная куча — это законченное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения расхода памяти. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 I + 1, а правый дочерний элемент — как 2 I + 2 (при условии, что индексирование начинается с 0).

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

  1. Постройте max-heap из входных данных.
  2. На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
  3. Повторяйте вышеуказанные шаги, пока размер кучи больше 1.

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

Вывод:

Здесь предыдущий C-код для справки.

Замечания:
Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).

Временная сложность: Временная сложность heapify — O(Logn). Временная сложность createAndBuildHeap() равна O(n), а общее время работы пирамидальной сортировки — O(nLogn).

Применения пирамидальной сортировки:

Алгоритм пирамидальной сортировки имеет ограниченное применение, потому что Quicksort (Быстрая сортировка) и Mergesort (Сортировка слиянием) на практике лучше. Тем не менее, сама структура данных кучи используется довольно часто. См. Применения структуры данных кучи

Скриншоты:

— (Теперь, когда мы построили кучу, мы должны преобразовать ее в max-heap)


— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
10 больше 4. Поэтому мы меняем местами 4 и 10)

— (В max-heap родительский узел всегда больше или равен по отношению к дочерним
5 больше 4. По этому мы меняем местами 5 и 4)


— (Меняем местами первый и последний узлы и удаляем последний из кучи)

Пожалуйста, оставляйте комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

  • Скопировать ссылку
  • Facebook
  • Twitter
  • ВКонтакте
  • Telegram
  • Pocket
Читайте также:  Как сделать сквозную строку в ворде

Похожие публикации

  • 30 июня 2017 в 10:52

Использование Python и Excel для обработки и анализа данных. Часть 2: библиотеки для работы с данными

Использование Python и Excel для обработки и анализа данных. Часть 1: импорт данных и настройка среды

Запуск проекта Otus.ru

Комментарии 6

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

Я понимаю, что это всего лишь перевод статьи с geeksforgeeks (образовательные статьи с geeksforgeeks?) по очень избитой теме, но перевести ведь можно и получше, есть ведь какая-то общепринятая терминология в русском языке.

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

2. «Пирамидальная сортировка — это вполне годный алгоритм. Его типичная реализация не стабильна, но может быть таковой сделана».
Не стабильна, близка к распаду. Вроде бы обычно в русском языке термин «stable sort» называют «устойчивой сортировкой».

3. Описание алгоритма.
«Наконец, преобразуйте полученное дерево в max-heap с новым корнем.».
В оригинале ведь все куда более конкретно: «Finally, heapify the root of tree.» и затем идет описание того, что же такое «heapify». В переводе термин «heapify» потерян, из-за этого логика становится куда более размытой.
Также третий пункт описания алгоритма «Повторяйте вышеуказанные шаги, пока размер кучи больше 1.» в оригинале написан неудачно (не очень понятно. нужно повторять шаги 1 и 2 или только 2), и тут также оставлен без изменений (причем русскоязычный вариант субъективно еще менее понятный).
В результате по описанию этого простого алгоритма, на мой взгляд, вообще мало что понятно без чтения кода или дополнительного поиска информации (что возвращает нас к теме качества статей на geeksforgeeks).

Его типичная реализация не стабильна, но может быть таковой сделана (см. Здесь).

Так себе решение. Для достижения стабильности потребуется O(n) памяти и еще больше просадит производительность. Скорее всего получится хуже по всем параметрам, чем merge sort.
Идеального алгоритмя до сих пор нет (гарантированая сложность O(n * log n), константа (или хотя бы логарифм) по памяти, стабильность).

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Ссылка на основную публикацию
Безмолвные монахи в доме гарета
Похороненное прошлое – это побочный квест в Divinity: Original Sin 2. На борту Госпожи Мести Гарет рассказал нам, что собирался...
Touchpal bengali pack что это
Главным инструментом для ввода текстовой информации на ПК считается клавиатура. Для мобильных устройств аналогом возможно считать приложение TouchPal. Многие могут...
Usb vid 534d pid 0021 mi 00
1. Скачайте необходимый файл. Розархивируйте его в какую-нибудь директорию. 2. В диспетчере устройств выберите устройство, которое требует установки/обновления драйвера. 3....
Блок схема пирамидальной сортировки
Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева. Пирамидой ( кучей ) называется двоичное дерево...
Adblock detector