Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.
С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.
Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).
HeapSort
Для тех кто не в теме, кратенько обрисую как работает пирамидальная сортировка.
Массив можно отсортировать, если на его основе строить и перестраивать сортирующее дерево, известное как двоичная куча или просто пирамида.
Что есть сортирующее дерево? Это дерево, у которого любой родитель больше (или меньше, смотря в какую сторону оно сортирующее) чем его потомки.
Как из обычного дерева сделать сортирующее дерево? Очень просто – нужно двигаться от потомков вверх к родителям и если потомок больше родителя, то менять местами. Если такой обмен произошёл, опустившегося на один уровень родителя нужно сравнить с потомками ниже – может и там тоже будет повод для обмена.
Преобразовывая неотсортированную часть массива в сортирующее дерево, в итоге в корень «всплывёт» наибольший элемент. Обмениваем максимум с последним ключом неотсортированного подмассива. Структура перестанет быть сортирующим деревом, но в качестве моральной компенсации его неотсортированная часть станет меньше на один узел. К этой неотсортированной части заново применим всю процедуру, то есть преобразуем её в сортирующее дерево с последующей перестановкой найденного максимума в конец. И так действуем до тех пор, пока неотсортированная часть не скукожится до одного-единственного элемента.
Подход, что и говорить, остроумный, но при этом специалисты по алгоритмам отмечают у сортировки кучей целую кучу недостатков, как-то: неустойчивость, хаотичность выборки, нечувствительность к почти упорядоченным массивам и пр. Смущает всех также неулучшаемая скорость O(n log n), демонстрируемая сортировкой абсолютно при любых наборах входящих данных.
Выдающиеся умы computer science предлагают различные мозговыносящие идеи (тернарные пирамиды, числа Леонардо, декартовы деревья) с помощью которых можно улучшить алгоритм. Джейсон Моррисон (Jason Morrison, сортировка названа в честь автора) предложил нечто противоположное – для оптимизации надо не усложнять, а максимально упрощать.
JSort
Канадский учёный пришёл к выводу, что заново перестраивать кучу для каждого элемента – дорогое удовольствие. Так уж ли необходимо массив из n элементов радикально перелопачивать n раз?
Если для массива построить всего пару куч (нисходящую и восходящую), то это значительно его упорядочит в обоих направлениях.
Сначала нужно осуществить построение невозрастающей кучи. В результате меньшие элементы повсплывают в верхние узлы пирамиды (что будет соответствовать левой половине массива), наименьший элемент вообще окажется в корне. Чем выше элементы находятся в сортирующем дереве – тем более упорядоченной будет соответствующая часть массива. Элементы находящиеся ближе к листьям дерева (им будет соответствовать вторая половина массива) будут иметь менее упорядоченный вид, поскольку они не сравнивались друг с другом, а просто были оттеснены на задворки в результате перемещения их родителей.
Для наведения относительного порядка в правой части массива следует построить кучу ещё раз, во всём противоположную первой. Во-первых, эта куча должна быть неубывающей (мы ведь теперь хотим разобраться с крупными по значению ключами). Во-вторых, она должна быть «зеркальной» к массиву, то есть её корень должен соответствовать не первому, а последнему элементу и выстраивать дерево следует, перебирая массив от конца к началу.
Соорудив такие себе близняшки-пирамидки, получаем во многом упорядоченный массив. Довершает дело сортировка вставками. Этот алгоритм имеет весьма скромную среднюю сложность по времени O(n2), но творит чудеса на массивах, которые уже почти отсортированы. Их сортировка вставками щёлкает как орешки.
Сложность по времени
Попробуем оценить при самом благоприятном раскладе. Однократное пирамидостроение – это O(n). Куч мы наложили две, так что получаем O(2n). Почти упорядоченный массив сортировка вставками может отсортировать за рекордные O(n). Общая сложность получается O(3n), что тоже самое что и O(n).
Впрочем, на практике всё выглядит скромнее. Возьмём, например, такой неотсортированный массив, содержащий числа от 1 до 30:
Построим обычную невозрастающую кучу:
Первая треть массива приняла вполне благообразный вид, в середине – кто в лес кто по дрова, конец массива пока тоже не впечатляет.
Построим теперь «зеркальную» неубывающую кучу:
Конец массива заметно похорошел. В середине наблюдаются некие зачатки упорядоченности, но выглядит не так гламурно, как левый и правый сектор. В принципе, массив вполне созрел, чтобы скормить его сортировке вставками.
Обратите внимание на ключ со значением 20.Почему этот элемент застрял в первой трети массива? Банально не повезло – перед построением «зеркальной» неубывающей кучи все родители вверх по ветке оказались больше по значению (в корне сейчас 17, но этот ключ утонет в левой половине дерева и уступит место 30). Поэтому в пирамиде ему не суждено возвыситься хотя бы на ступеньку.
Чем длиннее массив, тем чаще такие вырожденные узлы будет возникать. А значит, в средней полосе длинных массивов сортировке вставками придётся изрядно потрудиться. Подаваемый ей массив для обработки будет не то чтобы почти отсортированным, а скорее почти почти отсортированным. На очень длинных списках временная сложность у Insertion Sort будет, конечно, не её средние/худшие O(n2), но и до O(n) будет далеко.
Между прочим
Есть ещё один алгоритм сортировки с очень похожим наименованием – J sort, которую разработал Джон Коен (John Cohen). Это тоже гибридный алгоритм, используется для обработки двусвязных списков. Сочетает в себе нитевидную сортировку (Strand sort) и сортировку перетасовкой (Shuffle sort). Но это уже другая история.
Характеристики алгоритма
| Название | Jsort (J-сортировка) | |
|---|---|---|
| Автор | Джейсон Моррисон (Jason Morrison) | |
| Класс | Гибридная сортировка (кучей + вставками) | |
| Устойчивость | Неустойчивая | |
| Сравнения | Есть | |
| Временная сложность | лучшая | O(n) |
| средняя | ? | |
| худшая | O(n2) | |
| Сложность по памяти | всего | O(n) |
| дополнительные данные | O(1) | |
Дополнительно
Heap sort на Java
/**
* Демонстрационный алгоритм для пирамидальной сортировки
* Авторы алгоритма - J. W. J. Williams и R. W. Floyd
*
* SortAlgorithm.java, Thu Oct 27 10:32:35 1994
*
* @author Jason Harrison@cs.ubc.ca
* @version 1.0, 23 Jun 1995
*/
class HeapSortAlgorithm extends SortAlgorithm {
//Сортировка кучей
void sort(int a[]) throws Exception {
int N = a.length;
//Создаём из массива сортирующее дерево
//Максимальный элемент окажется в корне.
for (int k = N / 2; k > 0; k--) downheap(a, k, N);
//Избавляемся от максимумов
//и перетряхиваем сортирующее дерево
do {
//Меняем максимум с последним элементом...
int T = a[0];
a[0] = a[N - 1];
a[N - 1] = T;
//... и перестравиваем сортирующее дерево
//для неотсортированной части массива
N = N - 1;
downheap(a, 1, N);
} while (N > 1); //До последнего элемента
}
//Просматриваем ветку и в её корень перемещаем наибольший узел
void downheap(int a[], int k, int N) throws Exception {
//В корне поддерева
//запоминаем родителя
int T = a[k - 1];
//Смотрим потомков в пределах ветки
while (k <= N / 2) {
int j = k + k;//Левый потомок
//Если есть правый потомок,
//то сравниваем его с левым
//и из них выбираем наибольший
if ((j < N) && (a[j - 1] < a[j])) j++;
//Если родитель больше (или равен) наибольшего потомка...
if (T >= a[j - 1]) {
//... то значит всё в порядке в этой ветке
break;
} else { //Если родитель меньше наибольшего потомка...
//... то потомок становится на место родителя
a[k - 1] = a[j - 1];
k = j;
}
}
//Родитель в итоге меняется местами с наибольшим из потомков
//(или остаётся на своём месте, если все потомки меньше его)
a[k - 1] = T;
}
}
YouTube-версия анимации Heap sort
Jsort на Java
/**
* Демонстраицонный алгоритм для J-сортировки (JSort).
* Автор алгоритма - Джейсон Моррисон (Jason Morrison)
* <http://www.scs.carleton.ca/~morrison>
*
* JSortAlgorithm.java
*
* Автор реализации - Патрик Морин
* @author Patrick Morin
*/
class JSortAlgorithm extends SortAlgorithm {
//С помошью неполной НЕУБЫВАЮЩЕЙ кучи
//крупные элементы закидываем поближе к концу массива
void reheap (int a[], int length, int i) throws Exception {
//С этим родителем ещё не разобрались
boolean done = false;
//Запоминаем отдельно родителя
//и смотрим на его потомка слева
int T = a[i];
int parent = i;
int child = 2 * (i + 1) - 1;
//Просматриваем потомков, а также потомков потомков
//и сравниваем их с родителем (если что - передвигаем потомков влево)
//Цикл продолжается пока не выпадем за пределы массива
//или пока не обменяем какого-нибудь потомка на родителя.
while ((child < length) && (!done)) {
//Если правый потомок в пределах массива
if (child < length - 1) {
//То из левого и правого потомка выбираем наименьшего
if (a[child] >= a[child + 1]) {
child += 1;
}
}
//Родитель меньше потомков?
if (T < a[child]) {
//Тогда с этим родителем и его потомками разобрались
done = true;
//Родитель НЕ меньше чем наименьший из его потомков.
//Перемещаем потомка на место родителя
//и с родителем в цикле сравниваем уже потомков этого потомка
} else {
a[parent] = a[child];
parent = child;
child = 2 * (parent + 1) - 1;
}
}
//Родитель, с которого всё начиналось
//передвигается ближе к концу массива
//(или остаётся на месте если не повезло)
a[parent] = T;
}
//С помошью неполной НЕВОЗРАСТАЮЩЕЙ кучи
//мелкие элементы закидываем поближе к началу массива
void invreheap (int a[], int length, int i) throws Exception {
//С этим родителем ещё не разобрались
boolean done = false;
//Запоминаем отдельно родителя
//и смотрим на его потомка слева
int T = a[length - 1 - i];
int parent = i;
int child = 2 * (i + 1) - 1;
//Просматриваем потомков, а также потомков потомков
//и сравниваем их с родителем (если что - передвигаем потомков)
//Цикл продолжается пока не выпадем за пределы массива
//или пока не обменяем какого-нибудь потомка на родителя.
while ((child < length) && (!done)) {
//Если левый потомок в пределах массива
if (child < length - 1) {
//То из левого и правого потомка выбираем наибольшего
if (a[length - 1 - child] <= a[length - 1 - (child + 1)]) {
child += 1;
}
}
//Родитель больше потомков?
if (T > a[length - 1 - child]) {
//Тогда с этим родителем и его потомками разобрались
done = true;
} else {
//Родитель НЕ больше чем наибольший из его потомков.
//Перемещаем потомка на место родителя
//и с родителем в цикле сравниваем уже потомков этого потомка
a[length - 1 - parent] = a[length - 1 - child];
parent = child;
child = 2 * (parent + 1) - 1;
}
}
//Родитель, с которого всё начиналось
//передвигается ближе к началу массива
//(или остаётся на месте если не повезло)
a[length - 1 - parent] = T;
}
//Основная процедура сортировки
void sort(int a[]) throws Exception {
//Строим неубывающую кучу
//Большие элементы из начала массива
//закидываем поближе к концу
for (int i = a.length-1; i >= 0; i--)
reheap (a, a.length, i);
//Строим невозрастающую кучу
//Меньшие элементы из конца массива
//закидываем поближе к началу
for (int i = a.length - 1; i >= 0; i--)
invreheap (a, a.length, i);
//Массив ПОЧТИ упорядочен
//Досортировываем вставками
for (int j = 1; j < a.length; j++) {
int T = a[j];
int i = j - 1;
while (i >= 0 && a[i] > T) {
a[i + 1] = a[i];
i -= 1;
}
a[i + 1] = T;
}
}
}
YouTube-версия анимации Jsort
Ссылки
Jsort в Википедии
Страница Джейсона Моррисона на сайте Университета Манитобы
Страница Джейсона Моррисона на LinkedIn
