J-сортировка
Пирамидальная сортировка (она же сортировка кучей) — классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) — O (n log n). Лучших и вырожденных случаев для неё нет.С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом — вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O (n log n). При этом данные методы весьма изощрённо реализованы.
Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O (n).
Для тех кто не в теме, кратенько обрисую как работает пирамидальная сортировка.
Массив можно отсортировать, если на его основе строить и перестраивать сортирующее дерево, известное как двоичная куча или просто пирамида.
Что есть сортирующее дерево? Это дерево, у которого любой родитель больше (или меньше, смотря в какую сторону оно сортирующее) чем его потомки.
Как из обычного дерева сделать сортирующее дерево? Очень просто — нужно двигаться от потомков вверх к родителям и если потомок больше родителя, то менять местами. Если такой обмен произошёл, опустившегося на один уровень родителя нужно сравнить с потомками ниже — может и там тоже будет повод для обмена.
Преобразовывая неотсортированную часть массива в сортирующее дерево, в итоге в корень «всплывёт» наибольший элемент. Обмениваем максимум в с последним ключом неотсортированного подмассива. Структура перестанет быть сортирующим деревом, но в качестве моральной компенсации его неотсортированная часть станет меньше на один узел. К этой неотсортированной части заново применим всю процедуру, то есть преобразуем её в сортирующее дерево с последующей перестановкой найденного максимума в конец. И так действуем до тех пор, пока неотсортированная часть не скукожится до одного-единственного элемента.
Подход, что и говорить, остроумный, но при этом специалисты по алгоритмам отмечают у сортировки кучей целую кучу недостатков, как-то: неустойчивость, хаотичность выборки, нечувствительность к почти упорядоченным массивам и пр. Смущает всех также неулучшаемая скорость O (n log n), демонстрируемая сортировкой абсолютно при любых наборах входящих данных.
Выдающиеся умы computer science предлагают различные мозговыносящие идеи (тернарные пирамиды, числа Леонардо, декартовы деревья) с помощью которых можно улучшить алгоритм. Джейсон Моррисон (Jason Morrison, сортировка названа в честь автора) предложил нечто противоположное — для оптимизации надо не усложнять, а максимально упрощать.
Канадский учёный пришёл к выводу, что заново перестраивать кучу для каждого элемента — дорогое удовольствие. Так уж ли необходимо массив из 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 [embedded content]
Jsort на Java
/**
* Демонстраицонный алгоритм для J-сортировки (JSort).
* Автор алгоритма — Джейсон Моррисон (Jason Morrison)
*
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 [embedded content]
Jsort в ВикипедииСтраница Джейсона Моррисона на сайте Университета МанитобыСтраница Джейсона Моррисона на LinkedIn
