J-сортировка :: Jsort
Гибридная сортировка на основе сортировки кучей.
Построение кучи для неотсортированных подмассивов - достаточно дорогостоящая операция, имеющая среднюю временную сложность O(log n). Канадский учёный в области информатики Джейсон Моррисон предлагает формировать сортирующее дерево всего 2 раза - чтобы небольшие элементы переместить в левую часть массива, а крупные - в правую. Это в значительной степени упорядочит массив, после чего к нему можно будет применить сортировку вставками.
Алгоритм
Сначала однократно строится невозрастающая двоичная куча.В результате минимальный элемент оказывается в корне дерева (то есть перемещается на первую позицию в массиве), небольшие по значению элементы перебираются в верхнюю часть пирамиды, то есть в левую половину массива.
Затем однократно строится ещё одна двоичная куча. Эта куча во всём противоположна предыдущей. Во-первых она неубывающая. Во-вторых, она является инвертированной - корень дерева соответствует последнему (а не первому) элементу массива, при формировании дерева массив перебирается от конца к началу (а не от начала к концу, как в обычной куче).
В результате максимальный элемент оказывается в корне "зеркального" дерева (то есть перемещается на последнюю позицию в массиве), крупные по значению элементы перебираются в верхнюю часть пирамиды, то есть в правую половину массива.
После этого получаем массив во многом упорядоченный в обоих направлениях. Почти отсортированный массив быстро доупорядочивается сортировкой вставками.
Сложность по времени
Однократное построение кучи - O(n). Двухкратное построение кучи - O(2n). Чем ближе массив к отсортированному состоянию, тем быстрее его обработает сортировка вставками, временная сложность при этом может достигать O(n). В итоге получаем лучший показатель O(3n), что то же самое что и O(n).
Характеристики алгоритма
| Название | J-сортировка (Jsort) | |
|---|---|---|
| Автор | Джейсон Моррисон (Jason Morrison) | |
| Класс | Гибридные сортировки (кучей + вставками) | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Лучшая | O (n) |
| Худшая | O (n2) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Jsort