1
правка
Изменения
м
== Timsort ==
** Иначе Если <tex>Y \leqslant X </tex> {{---}} сливаем <tex>X</tex> c <tex>Y</tex>. * '''Шаг 5'''. Если всего осталось <tex> 3 </tex> подмассива, которые сейчас в стеке, то сливаем их в правильном порядке, иначе же переходим Переходим к шагу 2.
* [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
→Шаг 3. Слияние
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий различные подходы.
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченный подмасивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
== Основная идея алгоритма ==
=== Обозначения ===
* <tex>\mathtt {n}</tex> {{---}} размер входного массива.
* <tex>\mathtt {run}</tex> {{---}} подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
** строго по убыванию <tex>\mathtt {a_{i} > a_{i + 1} > \dots} </tex>.
* <tex>\mathtt {minrun} </tex> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
===Шаг №11. Вычисление minrun===
* Начало.
* '''Шаг 0'''. Число <tex>\mathtt{minrun}</tex> определяется на основе <tex>\mathtt{n}</tex>, исходя из следующих принципов:
** Не должно быть слишком большим, поскольку к подмассиву размера <tex>\mathtt{minrun}</tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).
** Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex dpi = 150> \fracmathtt{\dfrac{n}{minrun}} </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
** Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex> [32; 65) </tex> (подробнее о том, почему так, будет сказано ниже).
** Исключение: если <tex> n < 64 </tex>, тогда <tex> n = \mathtt{minrun } </tex> и '''Timsort''' превращается в сортировку вставками.* '''Шаг 1'''. Берем старшие 6 бит числа <tex>\mathtt {n} </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
Нетрудно понять, что после таких вычислений, <tex dpi = 150> \fracmathtt{\dfrac{{n}}{minrun}} </tex> будет степенью двойки.
* Конец.
'''int''' minRunLength(n): flag = 0 <font color=green>// будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой</font>
'''while''' (n <tex> \geqslant</tex> 64)
flag |= n & 1
===Шаг 2. Алгоритм разбиения на подмассивы и их сортировка===
На данном этапе у нас есть входной массив, его размер <tex>\mathtt{n}</tex> и вычисленное число <tex>\mathtt{minrun}</tex>. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>\mathtt{minrun}</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>\mathtt{minrun}</tex>. [[Файл:MinrunExample.png |300px|thumb400px|right]]
* Начало.
* '''Шаг 0'''. Указатель текущего элемента ставится в начало входного массива.
* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>\mathtt{run}</tex>. По определению, в <tex>\mathtt{run}</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления <tex>\mathtt{run}</tex> для текущего массива элементы переставляются так, чтобы они шли по возрастанию.
* '''Шаг 2'''. Если размер текущего <tex>\mathtt{run}</tex> меньше <tex>\mathtt{minrun}</tex>, тогда выбираются следующие за найденным подмассивом <tex>\mathtt{run}</tex> элементы в количестве <tex> \mathtt{minrun - size(run) } </tex>. Таким образом, на выходе будет получен подмассив размером большим или равный равным <tex>\mathtt{minrun}</tex>, часть которого (в лучшем случае {{---}} он весь) упорядочена.* '''Шаг 3'''. К данному подмассиву применяем сортировка сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена {{---}} сортировка работает эффективно.
* '''Шаг 4'''. Указатель текущего элемента ставится на следующий за подмассивом элемент.
* '''Шаг 5'''. Если конец входного массива не достигнут {{---}} переход к шагу 1.
=== Шаг 3. Слияние ===
Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно нужно ''объединять подмассивы примерно равного размера'' и ''cохранять стабильность алгоритма''.
[[Файл:Merge2mas.png|400px|right]]
* Начало.
* '''Шаг 1'''. Берется первый упорядоченный подмассив.
* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex> индекс начала текущего подмассива, его размер <tex> > </tex>.
* '''Шаг 3'''. Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека(если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами). * '''Шаг 4'''. Повторяем пока выражение (<tex>Z > X + Y ~and~ \wedge Y > X</tex>) не станет истинным ** Если размер стека не меньше <tex>2</tex> и <tex>Y \leqslant X </tex> {{---}} сливаем <tex>X</tex> c <tex>Y</tex>.
** Если размер стека не меньше <tex>3</tex> и <tex>Z \leqslant X + Y</tex> {{---}} сливаем <tex>Y</tex> c <tex>\min(X,Z)</tex>.
* Конец
* '''Шаг 0'''. Создается временный массив в размере меньшего из сливаемых подмассивов.
* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>{{-</tex> --}} правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
* '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
* Конец.
===Пример===
Возьмем <tex>n = 356</tex>. При таком <tex>\mathtt{n}</tex> <tex>\mathtt{minrun}</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.
Числа с закрывающей скобкой показывают номера шагов, на которых произошло сливание нижестоящих подмассивов.
* Конец.
Для вышеописанных массивов <tex>\mathtt{A, B}</tex> алгоритм выглядит следующим образом:
Первые <tex>7</tex> итераций сравниваются числа <tex>1, 2, 3, 4, 5, 6, 7</tex> из массива <tex>\mathtt{A}</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> больше, то элементы массива <tex>\mathtt{A}</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''галопа''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i - 1}, \dots, 10000 </tex> массива <tex>\mathtt{A}</tex> <tex>( \thicksim\log{n}</tex> сравнений<tex>)</tex>. После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, что он весь меньше <tex>\mathtt{B}</tex>, нужные данные из массива <tex>\mathtt{A}</tex> копируются в результирующий.
== Доказательство времени работы алгоритма ==
Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.
Пусть <tex>\mathtt{k}</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex>\mathtt{k} </tex> = <tex dpi=150> \left\lceil \fracmathtt{\dfrac{n}{minrun}} \right\rceil </tex>.
Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>O(n \log{n})</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длину. Можно сказать больше: пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной <tex>\mathtt{minrun}</tex> последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы <tex>\mathtt{minrun}</tex>.
Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex>\approx 2</tex> раза. Таким образом получаем, что каждый подмассив <tex>\mathtt{run_i}</tex> может участвовать в не более <tex>O(\log{n})</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(\log{n})</tex> раз. Элементов <tex>\mathtt{n}</tex>, откуда получаем оценку в <tex>O(n\log{n})</tex>.
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>\mathrm{run_i}</tex>: в нашем случае, алгоритм работает за <tex>O(\mathtt{minrun + inv})</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>\mathtt{k}</tex> получим, что сортировка всех блоков может занять <tex>O(\mathtt{minrun + inv}) \cdot k = O(\mathtt{minrun + inv}) \cdot </tex><tex dpi=150>\left\lceil \fracmathtt{\dfrac{n}{minrun}} \right\rceil </tex>. Что в худшем случае <tex dpi=150 >(\mathtt{inv = \fracdfrac{minrun(minrun - 1)}{2}} )</tex> может занимать <tex>O(\mathtt{n \cdot minrun}) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после эксперементов экспериментов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>. ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]]
== Источники информации==
* Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
* [http://ru.wikipedia.org/wiki/Timsort Wikipedia {{- --}} Timsort] * [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr {{---}} Алгоритм сортировки Timsort]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]
