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

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени – . Лучших и вырожденных случаев для неё нет.[Источник 1]

История

С момента изобретения метода было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг . При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон в 1964 году. При этом способ в некоторых случаях по скорости приближается к .

Алгоритм

Массив можно отсортировать, если на его основе строить и перестраивать сортирующее дерево, известное как двоичная куча или просто пирамида. Что есть сортирующее дерево? Это дерево, у которого любой родитель больше (или меньше, смотря в какую сторону оно сортирующее) чем его потомки.

Как из обычного дерева сделать сортирующее дерево? Очень просто – нужно двигаться от потомков вверх к родителям и если потомок больше родителя, то менять местами. Если такой обмен произошёл, опустившегося на один уровень родителя нужно сравнить с потомками ниже – может и там тоже будет повод для обмена. Преобразовывая неотсортированную часть массива в сортирующее дерево, в итоге в корень «всплывёт» наибольший элемент. Обмениваем максимум с последним ключом неотсортированного подмассива.

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

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

Свойство пирамиды сохраняется лишь в рамках исходного, основного массива . Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью. Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды на элемент влево: Смотрим на сыновей слева и справа - в массиве это и и выбираем наибольшего из них. Если этот элемент больше - меняем его с местами и идем к шагу 2, имея в виду новое положение в массиве. Иначе конец процедуры.

Новый элемент "просеивается" сквозь пирамиду. Hачать построение пирамиды можно с Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов или Просто потому, что такие находятся за границей массива. Следует заметить, что неправильно говорить о том, что является пирамидой как самостоятельный массив. Это, вообще говоря, не верно: его элементы могут быть любыми. Свойство пирамиды сохраняется лишь в рамках исходного, основного массива Далее будем расширять часть массива, обладающую столь полезным свойством, добавляя по одному элементу за шаг. Следующий элемент на каждом шаге добавления - тот, который стоит перед уже готовой частью. Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды на элемент влево: Смотрим на сыновей слева и справа - в массиве это и и выбираем наибольшего из них. Если этот элемент больше - меняем его с местами и идем к шагу 2, имея в виду новое положение в массиве. Иначе конец процедуры. Новый элемент "просеивается" сквозь пирамиду.

Строение пирамиды занимает операций, причем более точная оценка дает даже за счет того, что реальное время выполнения downheap зависит от высоты уже созданной части пирамиды. Вторая фаза занимает времени: раз берется максимум и происходит просеивание бывшего последнего элемента. Плюсом является стабильность метода: среднее число пересылок , и отклонения от этого значения сравнительно малы. Пирамидальная сортировка не использует дополнительной памяти.[Источник 2]

 1  void downHeap(T a[], long k, long n) {
 2   //  процедура просеивания следующего элемента 
 3   //  До процедуры: a[k+1]...a[n]  - пирамида 
 4   //  После:  a[k]...a[n]  - пирамида 
 5   T new_elem;
 6   long child;
 7   new_elem = a[k];
 8  while(k <= n/2) {  		// пока у a[k] есть дети 
 9     child = 2*k;
10     //  выбираем большего сына 
11     if( child < n && a[child] < a[child+1] ) 
12     child++;
13     if( new_elem >= a[child] ) break; 
14     // иначе 
15     a[k] = a[child]; 	// переносим сына наверх 
16     k = child;
17   }
18   a[k] = new_elem;
19  }

JSort

Канадский учёный пришёл к выводу, что заново перестраивать кучу для каждого элемента – дорогое удовольствие. Так уж ли необходимо массив из n элементов радикально перелопачивать раз? Если для массива построить всего пару куч (нисходящую и восходящую), то это значительно его упорядочит в обоих направлениях. Сначала нужно осуществить построение невозрастающей кучи. В результате меньшие элементы повсплывают в верхние узлы пирамиды (что будет соответствовать левой половине массива), наименьший элемент вообще окажется в корне.

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

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

Во-вторых, она должна быть «зеркальной» к массиву, то есть её корень должен соответствовать не первому, а последнему элементу и выстраивать дерево следует, перебирая массив от конца к началу. Соорудив такие себе близняшки-пирамидки, получаем во многом упорядоченный массив. Довершает дело сортировка вставками. Этот алгоритм имеет весьма скромную среднюю сложность по времени , но творит чудеса на массивах, которые уже почти отсортированы. Их сортировка вставками щёлкает как орешки.[Источник 3]

Характеристики алгоритма

Название Jsort (J-сортировка)
Автор Джейсон Моррисон (Jason Morrison)
Класс Гибридная сортировка (кучей + вставками)
Устойчивость Неустойчивая
Сравнения Есть
Временная сложность лучшая O(n) средняя ? худшая O(n2)
Сложность по памяти всего O(n) дополнительные данные O(1)

Источники

  1. Пирамидальная сортировка // Программирование. [2006—2019]. URL: https://prog-cpp.ru/sort-pyramid/ (дата обращения: 26.11.2018).
  2. Пирамидальная сортировка // Алгоритмы Методы Исходники. [2000—2019]. URL: http://algolist.manual.ru/sort/pyramid_sort.php (дата обращения: 26.11.2018).
  3. J-сортировка // Хабр. [2006—2019]. Дата обновления: 28.04.2014. URL: https://habr.com/post/221095/ (дата обращения: 26.11.2018).

Ссылки