Remkomplekty.ru

IT Новости из мира ПК
32 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Итак, мы постепенно переходим от более-менее простых к сложным, но эффективным методам. Пирамидальная сортировка является первым из рассматриваемых методов, быстродействие которых оценивается как O(n log n).

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

Пример действий для массива a[0]. a[7]:

Вертикальной чертой отмечена левая граница уже отсортированной(правой) части массива.

Рассмотрим оценку количества операций подробнее.
Всего выполняется n шагов, каждый из которых состоит в выборе наибольшего элемента из последовательности a[0]..a[i] и последующем обмене. Выбор происходит последовательным перебором элементов последовательности, поэтому необходимое на него время: O(n). Итак, n шагов по O(n) каждый — это O(n 2 ).

Произведем усовершенствование: построим структуру данных, позволяющую выбирать максимальный элемент последовательности не за O(n), а за O(logn) времени. Тогда общее быстродействие сортировки будет n*O(logn) = O(n log n).

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

Итак, назовем пирамидой(Heap) бинарное дерево высоты k, в котором

  • все узлы имеют глубину k или k-1 — дерево сбалансированное.
  • при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо, т.е форма пирамиды имеет приблизительно такой вид:
  • выполняется «свойство пирамиды»: каждый элемент меньше, либо равен родителю.

Как хранить пирамиду? Наименее хлопотно — поместить ее в массив.

Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:

  • в a[0] хранится корень дерева
  • левый и правый сыновья элемента a[i] хранятся, соответственнно, в a[2i+1] и a[2i+2]

Таким образом, для массива, хранящего в себе пирамиду, выполняется следующее характеристическое свойство: a[i] >= a[2i+1] и a[i] >= a[2i+2].

Плюсы такого хранения пирамиды очевидны:

  • никаких дополнительных переменных, нужно лишь понимать схему.
  • узлы хранятся от вершины и далее вниз, уровень за уровнем.
  • узлы одного уровня хранятся в массиве слева направо.

Запишем в виде массива пирамиду, изображенную выше.. Слева-направо, сверху-вниз: 94 67 18 44 55 12 06 42. На рисунке место элемента пирамиды в массиве обозначено цифрой справа-вверху от него.

Восстановить пирамиду из массива как геометрический объект легко — достаточно вспомнить схему хранения и нарисовать, начиная от корня.

Hачать построение пирамиды можно с a[k]. a[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i,j: i = 2i+1 ( или j = 2i+2 ). Просто потому, что такие i,j находятся за границей массива.

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

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

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды a[i+1]..a[n] на элемент a[i] влево:

  1. Смотрим на сыновей слева и справа — в массиве это a[2i+1] и a[2i+2] и выбираем наибольшего из них.
  2. Если этот элемент больше a[i] — меняем его с a[i] местами и идем к шагу 2, имея в виду новое положение a[i] в массиве. Иначе конец процедуры.

Новый элемент «просеивается» сквозь пирамиду.

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

страницы: 1 2

Содержание

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность

N 2 , к улучшенным сортировкам относятся алгоритмы с общей сложностью

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N 1 базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл её состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить «правильное» место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний kt, kt-1. k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить её обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две «хорошие» последовательности расстояний:

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т. д. между её элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2 t -1.

Читать еще:  Паскаль считать массив из файла

Итак, длина нашего массива (N) должна попадать в такие границы:

Прологарифмируем эти неравенства (по основанию 2):

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придётся вспомнить знакомое из курса средней школы правило «превращения» логарифмов:

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить ещё на 1 шаг:

Расстояние между элементами в любой подпоследовательности вычисляется так:

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k + 1)–го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких «удлинённых» подпоследовательностей совпадает с длиной «хвоста» — остатка от деления N на шаг k:

Реализация алгоритма УлШелл

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

program shell_sort ;
const
n = 18 ;
a : array [ 1 .. n] of Integer =
( 18 , 17 , 16 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 ) ;
var ii , m , x , s , p , t , k , r , i , j : Integer ;
begin
t := Trunc ( Ln (n) / Ln ( 2 )) ;
repeat
t := t — 1 ;
k := ( 1 shl t) — 1 ;
p := n mod k ;
s := n div k ;
if p = 0 then
p := k
else
s := s + 1 ;

WriteLn (k , ‘-сортировка’ ) ;
for i := 1 to k do <берём и длинные, и короткие подпоследовательности>
begin
if i = p + 1 then
s := s — 1 ; <для коротких — уменьшаем длину>
for j := 1 to s — 1 do <метод ПрВст с шагом k>
if a[i + (j — 1 ) * k] > a[i + j * k] then
begin
x := a[i + j * k] ;
m := i + (j — 1 ) * k ;
while (m > 0 ) and (a[m] > x) do
begin
a[m + k] := a[m] ;
m := m — k ;
end ;
a[m + k] := x ;
end ;
for ii := 1 to n do
Write (a[ii] , ‘ ‘ ) ;
WriteLn ;
end ;
until k = 1 ;
end .

Результат работы

7–сортировки

3–сортировки

1–сортировка

Эффективность алгоритма УлШелл

Довольно сложными методами, в изложение которых мы не будем углубляться, показано, что алгоритм Шелла имеет сложность

N 3/2 . И хотя это несколько хуже, чем N*logN, всё–таки эта сортировка относится к улучшенным.

Пример сравнения сортировок: Вновь возьмём последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

  1. 3–сортировки:

Состояние массива Сдвиги Сравнения Пересылки данных

0 шаг: 1323645
1 шаг: 1 323645 0 1 0
2 шаг: 13 23645 1 1+1 1+2
3 шаг: 123 3645 0 1 0
4 шаг: 1233 645 0 1 0
5 шаг: 12336 45 1 1+1 1+2
6 шаг: 123346 5 1 1+1 1+2
результат: 1233456 3 9 9

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% — на сравнениях) 2 . Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет ещё заметнее.

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

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду — своеобразное бинарное дерево, — а затем искать минимум только среди тех элементов, которые находятся непосредственно «под» текущим вставляемым.

Просеивание

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

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

Сортировки массивов

Улучшенные сортировки

В отличие от простых сортировок, имеющих сложность

N 2 , к улучшенным сортировкам относятся алгоритмы с общей сложностью

Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N 9 Д. Л. Шелл назвал ее » сортировкой вставками с убывающим шагом». базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл ее состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить «правильное» место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

  1. вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
  2. каждую из этих подпоследовательностей отсортировать методом ПрВст.
Читать еще:  Scanf в си это

Нахождение убывающей последовательности расстояний kt, kt-1. , k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить ее обязательные свойства:

  • k1 = 1;
  • для всех t kt > kt-1;
  • желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две «хорошие» последовательности расстояний:

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т.д. между ее элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2 t -1.

Итак, длина нашего массива (N) должна попадать в такие границы:

или, что то же самое,

Прологарифмируем эти неравенства (по основанию 2):

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е ( натуральный логарифм ). Поэтому нам придется вспомнить знакомое из курса средней школы правило «превращения» логарифмов:

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть — и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:

Расстояние между элементами в любой подпоследовательности вычисляется так:

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких «удлиненных» подпоследовательностей совпадает с длиной «хвоста» — остатка от деления N на шаг k:

Реализация алгоритма УлШелл

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

Эффективность алгоритма УлШелл

Довольно сложными методами, в изложение которых мы не будем углубляться, показано, что алгоритм Шелла имеет сложность

N 3/2 . И хотя это несколько хуже, чем N*logN, все-таки эта сортировка относится к улучшенным.

Пример сравнения сортировок: Вновь возьмем последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):

Теперь применим к ней метод Шелла.

Здесь N = 7, поэтому:

  1. 3-сортировки:

При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% — на сравнениях ) 10 Для других входных данных это число может быть значительно меньше или же еще больше. . Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.

Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет еще заметнее.

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

Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.

Р. Флойд предложил перестроить линейный массив в пирамиду — своеобразное бинарное дерево , — а затем искать минимум только среди тех элементов, которые находятся непосредственно «под» текущим вставляемым.

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

Итак, будем рассматривать наш линейный массив как пирамидальную структуру:

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

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

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

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

Читать еще:  Неожиданный символ паскаль

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

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

Наиболее известным из таких алгоритмов является 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 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.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×