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

[Iqorek]

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

[valemak]

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

[frobeniusfg]

Странный, на мой взгляд, термин — куча куч, скорее уж это стек (или связный список) куч.

[valemak]

Стек куч — очень удачный термин применительно к рассматриваемой ситуации. Я, во всяком случае, возьму его в использование применительно к подобным структурам.

Куча куч тоже вполне уместно звучит. Обратите внимание, что если в этом векторе куч взять размеры всех куч, то получим невозрастающую последовательность (или неубывающую, если двигаться по списку куч в обратном направлении). То есть, если смотреть не на значения элементов в корнях, а на количество узлов каждой кучи, то в этом контексте имеем дело тоже именно с кучей (частный случай бинарного дерева, у которого от корня идёт только одна ветка, однако отсутствует вторая — такое тоже допустимо для кучи). Так как узлы представляют из себя невозрастающую последовательность, то выполняется условия сортирующего дерева — каждый потомок больше (если это min-heap) чем родитель.

[frobeniusfg]

Если с этой точки зрения, то да. Спасибо.

[AlternativeSolution]

С коде есть ошибка, после сортировки некоторые значения расположены в неправильном порядке. Это так и было задумано?

[valemak]

Каюсь и признаю, питоновский код лично не проверял, взял тот, что нашёл в Интернете. Основная цель статьи — иллюстративно и доходчиво рассказать про сам алгоритм. Исходники с корректной сортировкой при желании можно найти самостоятельно.

[Kealon]

Понекроманщу:

Поэтому, на первом этапе наилучшая сложность по времени:для почти упорядоченных данных — O(n),для рандомных данных — O(n log n).

По аналогии с бинарной кучей это можно сделать за O(n).

На втором этапе наилучшая сложность по времени такая же как и на первом:для почти упорядоченных данных — O(n),для рандомных данных — O(n log n).

Тут ошибка, в лучшем случае будет так же - O(n log n), просто коэффициент ниже. Перебор списка куч никуда не деть, их количество для определённого размера в среднем log2(n) / 2.

[Kealon]

Понял в чём проблема, алгоритм в статье не соответствует оригинальному.

В оригинале каждая нода должна соединяться с вершиной предыдущего дерева. И по сути основная часть сортировки происходит при построении.

И тогда действительно будет O(N) в лучшем случае.

в среднем - O(N * log(N)), в худшем - O(N * log(N)^ 2)

Худший случай получается из наибольшего пути по всем вершинам (log(N) + ... +1)

И что печально, проигрывает она всем подряд

Array size = 1000000
SmoothSort (Original Djikstra's algorithm)
sorted array: Compare Count= 1 999 963 Swap Count= 0 
inverse array: Compare Count= 39 089 125 Swap Count= 17 049 406 
randomic array: Compare Count= 53 794 331 Swap Count= 23 882 961

SmoothSort ( то что описано в статье)
sorted array: Compare Count= 8 063 084 Swap Count= 0 
inverse array: Compare Count= 30 700 368 Swap Count= 12 211 388 
randomic array: Compare Count= 42 651 444 Swap Count= 18 093 007

SmoothSort (то же самое, что в статье, только для 2^k-1 nums)
sorted array: Compare Count= 9 885 024 Swap Count= 0 
inverse array: Compare Count= 30 822 280 Swap Count= 11 349 896 
randomic array: Compare Count= 42 424 646 Swap Count= 17 071 620

HeapSort
sorted array: Compare Count= 37 692 069 Swap Count= 19 787 792 
inverse array: Compare Count= 36 001 436 Swap Count= 18 333 408 
randomic array: Compare Count= 36 792 726 Swap Count= 19 047 502

QuickSort
sorted array: Compare Count= 19 000 019 Swap Count= 0 
inverse array: Compare Count= 19 000 036 Swap Count= 500 000 
randomic array: Compare Count= 25 250 205 Swap Count= 4 911 581