J-сортировка :: Jsort

Гибридная сортировка на основе сортировки кучей.

Построение кучи для неотсортированных подмассивов — достаточно дорогостоящая операция, имеющая среднюю временную сложность O(log n). Канадский учёный в области информатики Джейсон Моррисон предлагает формировать сортирующее дерево всего 2 раза — чтобы небольшие элементы переместить в левую часть массива, а крупные — в правую. Это в значительной степени упорядочит массив, после чего к нему можно будет применить сортировку вставками.

J-сортировка || Jsort

Алгоритм

Сначала однократно строится невозрастающая двоичная куча.

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

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

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

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

Сложность по времени

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

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

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

Ссылки

Хабрахабр: J-сортировка

Jsort on Wikipedia
Страница Джейсона Моррисона на сайте Университета Манитобы
Страница Джейсона Моррисона на LinkedIn

Добавить комментарий