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

[Все сортировки]

Предварительные темы:
1. Пирамидальная сортировка
2. Битовые операции

Теория: На русском языке мне, к сожалению, не удалось найти ни одного материала по этой теме. Поэтому общее представление об алгоритме можно получить из англоязычного источника, например здесь.
Рекомендую обратить внимание на gif’ку, представленную в статье. Лично мне она очень понравилась).



Итак, рассмотрим основные положения из представленной статьи:
Для начала узнаем(вспомним), что есть числа Леонардо, которые вычисляются по формуле:
L(0) = 1;
L(1) = 1;
L(n) = L(n-1) + L(n-2) + 1;

Формулировка задачи:
Отсортировать массив объектов в порядке неубывания. Для простоты рассмотрим массив целых чисел.

Общие положения:
1. Сортируемый массив делится на группу подмассивов. Каждый подмассив представляет собой структуру данных куча. Каждая куча имеет размер равный одному из чисел Леонардо. При этом левые элементы массива являются узлами самой большой возможной кучи. Оставшиеся элементы массива разбиваются на кучи по такому же жадному правилу. В дальнейшем эту группу подмассивов будем называть последовательность куч. При этом, элементы этой последовательности будут строго уменьшаться в размере с ростом порядкового номера.
2. Не существует двух куч, имеющих одинаковый размер.
Это утверждение можно доказать так: Числа Леонардо растут медленнее функции 2^N, поэтому для любого массива можно найти такое число Леонардо, которое будет больше середины. Исключением является массив длины 2.
3. Никакие две кучи не будут иметь размер равным двум последовательным числам Леонардо. Исключением могут быть только две последние кучи.
Если мы будем использовать подряд две кучи размерностью L(x) и L(x+1), то их можно будет заменить одной – размерностью L(x+2)

Следствия:
1. В вершине каждой кучи находится максимальный из узлов данной кучи.
2. Максимальный элемент массива нужно искать среди вершин сформированных куч.

Краткое описание алгоритма:
   Формирование последовательности куч:
В начале последовательность куч пуста. Последовательно добавляем элементы из исходного массива слева направо. Элемент, который будет добавляться в последовательность куч выступает либо в качестве вершины абсолютно новой кучи, либо в качестве вершины, которая объединит две последние кучи. Повторяем эту итерацию пока не закончатся элементы во входном массиве.
   Формирование отсортированного массива:
На каждой итерации определяем текущий максимум массива, используя следствие 2. Ставим максимальный элемент на последнее место и исключаем его из последовательности куч. Повторяем это действие, пока последовательность куч не окажется пуста.
Замечание:
При объединении двух куч в одну и и при обмене двух вершинных элементов нужно гарантировать сохранение свойства кучи, т.е. выполнять “просейку вниз” при необходимости.


Теперь рассмотрим вышеописанный процесс более детально и отсортируем массив:

{9, 5, 0, 4, 3, 6, 2, 1, 7, 8}

Условные обозначения:

	Новый элемент в последовательности куч
	Максимальный элемент в массиве
	Вершина кучи

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

Шаг 1

Состояние: 1

Комментарий: В начальный момент последовательность куч пуста. Добавление первого элемента влечет за собой создание первой кучи, состоящей из одного элемента.

 

Шаг 2

Состояние: 3

Комментарий: Второй элемент не может объединить две крайние правые кучи, т.к. их пока просто нет. Поэтому новый элемент просто образует еще одну кучу, вершиной которой он сам и является.

 

Шаг 3

Состояние: 4

Комментарий: Третий элемент объединяет две крайние правые кучи, образуя единую кучу. Т.к. добавление нового элемента привело к нарушению свойства кучи делаем “просейку вниз”

 

Шаг 4

Состояние: 5

 

Шаг 5

Состояние: 8

 

Шаг 6

Состояние: 9

 

Шаг 7

Состояние: 11

 

Шаг 8

Состояние: 12

 

Шаг 9

Состояние: 16

 

Шаг 10

Состояние: 17

Итак, на текущем шаге мы сформировали последовательность куч по всем вышеперечисленным правилам. Теперь наша задача получить отсортированный массив. На каждом шаге 11 – 20 будем получать максимальный элемент, который будет находится в конце массива и удалять его из дальнейшего рассмотрения.

Шаг 11

Состояние: 17

Комментарий: Просматривая вершины куч (8 и 9) находим максимальный элемент и ставим его на последнее место. При замене вершины левой кучи просейка вниз не нужна, т.к. новая вершина не нарушила главного свойства кучи.

 

Шаг 12

Состояние: 16

Комментарий: Т.к. в текущий момент последовательность куч содержит, только одну кучу, то максимальный элемент будет находится в в вершине этой кучи.

 

Шаг 13

Состояние: 12

 

Шаг 14

Состояние: 11

Комментарий: После обмена элементов 6 и 2 необходимо сделать просейку.

 

Шаг 15

Состояние: 9

 

Шаг 16

Состояние: 8

 

Шаг 17

Состояние: 5

 

Шаг 18

Состояние: 4

 

Шаг 19

Состояние: 3

 

Шаг 20

Состояние: 1

Блочное представление ни что иное, как альтернативное представление связей узлов в кучах. Если спроецировать все элементы блочного представления на ось X, то получим состояние массива на каждом шаге.
Состояние меток представлено двумя рядами. Верхний состоит из чисел Леонардо, записанных справа налево. В нижнем ряду под соответствующим числом Леонардо стоит 1, если в текущей последовательности куч имеется куча данного размера. Если имеется куча единичной размерности, то сначала отмечаем самую правую метку (L(0)).
Текущее состояние можно получить, если перевести двоичное представление нижнего ряда состояния меток в десятичную систему счисления.

После этого рекомендую еще раз проглядеть все 20 шагов с учетом полученной информации.

На этом будем считать что общую суть и идею алгоритма мы уловили. Давайте перейдем к реализации.
Этап 1. Реализация функций с прототипами:

1. typedef long long INT;
2. ...
3. int NextState(INT &curState);
4. void PrevState(INT &curState);

* This source code was highlighted with Source Code Highlighter.

Переменная curState – это текущее состояние последовательности куч, двоичное представление которой задает размерности этих куч.
Функция PrevState изменяет текущее состояние с учетом того, что вершина последней кучи исключена из рассмотрения.
Функция NextState, как можно догадаться, делает обратную операцию, но при этом она еще возвращает номер бита, соответствующий вершине последней кучи, если та состоит более чем из одного элемента. В противном случае функция возвращает –1. 
Говоря другими словами, нужно уметь спускаться и подниматься по первому столбцу нижеприведенной таблицы:

Этап 2. Реализация функции просейки вниз, которая может выглядеть так:

1. // Просейка вниз
2. // mas - массив
3. // posHeapItemsAmount - число LeoNum[posHeapItemsAmount] - число элементов в текущей кучи
4. // indexLastTop - индекс вершины последней кучи
5. void shiftDown(vector<int> &mas, int posHeapItemsAmount, int indexLastTop)
6. {
7.   // позиция текущего узла (вершина кучи)
8.   int posCurNode = indexLastTop;
9.   while (posHeapItemsAmount>1)
10.   {
11.     // позиция правого сына
12.     int  posR = posCurNode - 1;
13.     // позиция левого сына
14.     int  posL = posR - LeoNum[posHeapItemsAmount-2]; 
15.  
16.     int posMaxChild = posL;
17.     int posNextTop = posHeapItemsAmount - 1;
18.     if (mas[posR] > mas[posL])
19.     {
20.       posMaxChild = posR;
21.       posNextTop = posHeapItemsAmount- 2;
22.     }
23.     if (mas[posCurNode] < mas[posMaxChild])
24.     {
25.       swap(mas[posCurNode],mas[posMaxChild]);
26.       posHeapItemsAmount = posNextTop;
27.       posCurNode = posMaxChild;
28.     }
29.     else
30.       break;
31.   }
32. }

* This source code was highlighted with Source Code Highlighter.

Этап 3. Функция создания последовательности куч из произвольного массива. Она может выглядеть так:

1. void make_heap_pool(vector<int> &mas)
2. {
3.   for (size_t i=0;i<mas.size();i++)
4.   {
5.     int posHeapItemsAmount = NextState(curState);
6.     if (posHeapItemsAmount != -1)
7.       shiftDown(mas,posHeapItemsAmount,i);
8.   }
9. }

* This source code was highlighted with Source Code Highlighter.

Этап 4. Функция поиска максимального элемента среди вершин куч:

1. // Среди вершин куч находим максимальный элемент
2. // mas - массив
3. // curState - число, двоичное представление которого описывает текущий массив куч
4. // indexLastTop - индекс крайней вершины
5. // &nextPosHeapItemsAmount - количество элементво в кучи, вершина которой оказалось максимальной из всех вершин куч
6. // Возврат: индекс элемента(одной из вершин кучи), который больше чем остальные вершины куч
7. int findPosMaxElem(vector<int> &mas, INT curState, int indexLastTop, int &nextPosHeapItemsAmount)
8. {
9.   int pos = 0;
10.   // ищим позицию первого единичного бита
11.   while (!(curState&1))
12.   {
13.     curState>>=1;
14.     pos++;
15.   }
16.  
17.   int posMaxTopElem = indexLastTop;
18.   nextPosHeapItemsAmount = pos;
19.  
20.   int curTopElem = indexLastTop - LeoNum[pos];
21.  
22.   curState>>=1;
23.   pos++;
24.   while (curState)
25.   {
26.     if (curState&1)
27.     {
28.       if (mas[curTopElem] > mas[posMaxTopElem])
29.       {
30.         posMaxTopElem = curTopElem;
31.         nextPosHeapItemsAmount = pos;
32.       }
33.       curTopElem -= LeoNum[pos];
34.     }
35.     curState >>=1;
36.     pos++;
37.   }
38.  
39.   return posMaxTopElem;
40. }

* This source code was highlighted with Source Code Highlighter.

Этап 5. Реализация Плавной Сортировки на основе предыдущих наработок:

1. void smooth_sort(vector<int> &mas)
2. {
3.   make_heap_pool(mas);
4.  
5.   for (int i=mas.size()-1;i>=0;i--)
6.   {
7.     int nextPosHeapItemsAmount;
8.     int posMaxTopElem = findPosMaxElem(mas,curState,i,nextPosHeapItemsAmount);
9.     if (posMaxTopElem != i)
10.     {
11.       swap(mas[i],mas[posMaxTopElem]);
12.       shiftDown(mas, nextPosHeapItemsAmount, posMaxTopElem);
13.     }
14.     PrevState(curState);
15.   }
16. }

* This source code was highlighted with Source Code Highlighter.

Как можно было заметить, последовательность куч не требует дополнительного места для своего хранения. Алгоритмическая сложность O(N*logN) (такая же, что и у пирамидальной сортировкой). Главное отличие от пирамидальной сортировки заключается в том, что если в качестве входных данных будет дан отсортированный массив, то при выполнении плавной сортировки не будут происходить обмены элементов, стоящих на нужных позициях.

Полный исходный код: здесь

P.S: Я думаю у многих давно созрел вопрос: зачем сделан магических тип INT? Так вот, если заранее известно, что количество элементов в массиве
a)меньше 4356617, то INT можно заменить на int
b)меньше 7049155 - на unsigned int

Т.к. в работе алгоритма возникает 2*N раз несколько битовых операций с числом curState, то минимизация количества его битов приведет с ускорению работы программы.