Изменения

'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слияниемразличные подходы.

Данный алгоритм является относительно новым и был изобретен в 2002 году придуман Тимом Петерсом(в честь него и назван) и основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таким массивах данных , которые содержат упорядоченный подмасивы, алгоритм Тима Петерса существенно быстрее многих показывает себя намного лучше других алгоритмов сортировкисортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''.

Алгоритм '''Timsort''' состоит из нескольких шаговчастей:* Начало.* '''Шаг №11''': по специальному алгоритму входной . Входной массив разделяется на подмассивыфиксированной длины, вычисляемой определённым образом. * '''Шаг №22''': каждый . Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка пузырьком | сортировкой пузырьком]] или любой другой устойчивой сортировкой.* '''Шаг 3'''. Отсортированные подмассивы объединяются в один массив с помощью модифицированной [[Сортировка выбором слиянием | сортировкой выборомсортировки слиянием]].* Конец.

* '''Шаг №3''': отсортированные подмассивы собираются Рассмотрим теперь каждый шаг в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]]отдельности.

===Используемые понятия и комментарииОбозначения ===

===Шаг 1. Вычисление minrun===* Начало.* '''Шаг 0'''. Число <tex>\mathtt{minrun}</tex>runопределяется на основе <tex>n</tex> {{---}} некоторый подмассив во входном массиве, который обязан быть упорядоченным одним исходя из двух способовследующих принципов:** строго по убыванию Не должно быть слишком большим, поскольку к подмассиву размера <tex> a_\mathtt{iminrun} </tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).** Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> a_\mathtt{\dfrac{i + 1n}{minrun}} </tex> {{---}} ''степень двойки''.Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.. ** Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex> [32; 65) </tex>(подробнее о том, почему так, будет сказано ниже). ** нестрого по возрастанию Исключение: если <tex> a_{i} n < 64 </tex>, тогда <tex> n = \le a_mathtt{i + 1minrun} \le ... </tex>и '''Timsort''' превращается в сортировку вставками.  * '''Шаг 1'''. Берем старшие 6 бит числа <tex>minrunn</tex> {{---}} минимальный размер подмассиваи добавляем единицу, описанного если в предыдущем пунктеоставшихся младших битах есть хотя бы один ненулевой.

===Шаг №1. Вычисление minrun===* Начало.* '''Шаг 0'''. Число <tex>minrun</tex> определяется на основе <tex> n </tex>Нетрудно понять, исходя из принципов:** Не должно быть слишком большимчто после таких вычислений, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).** Оно не должно быть слишком маленьким, так как чем меньше подмассив \mathtt{\dfrac{{---n}} тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> n / {minrun </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.** Согласно авторским экспериментам: *** При <tex> minrun > 256 </tex> нарушается пункт <tex>1</tex>.*** При <tex> minrun < 8 </tex> нарушается пункт <tex>2</tex>.*** Наиболее эффективные значения <tex> minrun </tex> из диапозона <tex> (32; 65) </tex>.*** Исключение — если <tex> n < 64 </tex>, тогда <tex> n = minrun </tex> и '''Timsort''' превращается в сортировку вставками.* '''Шаг 1'''. Берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевойбудет равно степени двойки или немного меньше степени двойки.

int GetMinrun(int n) { int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */ while (n >= 64) { flag |= n & 1; n >>= 1; } return n + flag; } ===Шаг №22. Алгоритм разбиения на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>\mathtt{minrun}</tex>. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>\mathtt{minrun}</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>\mathtt{minrun}</tex>. [[Файл:MinrunExample.png‎ |300px|thumb400px|right]]

* '''Шаг 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'''. К данному подмассиву применяем сортировка сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена {{---}} сортировка работает эффективно.

===Шаг №33. Слияние===Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно нужно ''объединять подмассивы примерно равного размера'' и ''cохранять стабильность алгоритма (не делать бессмысленных перестановок)''.

* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex> {{---}} <tex> < </tex>, размер подмассива<tex> > </tex>.

* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex>индекс начала текущего подмассива<tex> > </tex> {{---}} <tex> < </tex>, его размер<tex> > </tex>.* '''Шаг 3'''. Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека(если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами). * '''Шаг 4'''.Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>\wedge Y > X</tex>) не станет истинным ** Если размер стека не меньше 3 <tex>2</tex> и <tex>Z Y \leqslant X + Y</tex> {{---}} сливаем <tex>YX</tex> c <tex>min(X,Z)Y</tex>. ** Иначе Если размер стека не меньше <tex>3</tex> и <tex>Y Z \leqslant X + Y</tex> {{---}} сливаем <tex>XY</tex> c <tex>Y\min(X,Z)</tex>. ** Возвращаемся в п'''Шаг 5'''.6Переходим к шагу 2.

* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>{{-</tex> --}} правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.

Возьмем <tex>n = 356</tex>. При таком <tex>n</tex> <tex>\mathtt{minrun}</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.

<tex>A = {1, 2, 3, ...\dots, 9999, 10000}</tex>

<tex>B = {20000, 20001, 20002, ...\dots, 29999, 30000}</tex>

Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге <tex>10000 </tex> сравнений и <tex>10000 </tex> копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»галоп'''. Алгоритм следующий:

 * '''Шаг 1'''.На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент. * '''Шаг 2'''. Если уже некоторое количество элементов (например, в данной реализации алгоритма '''JDK 7''' это число равно 7) было взято из одного и того же массива {{---}} предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»галопа''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива. * '''Шаг 43'''. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.

Для вышеописанных массивов <tex> \mathtt{A, B }</tex> алгоритм выглядит следующим образом:Первые <tex>7 </tex> итераций сравниваются числа <tex>1, 2, 3, 4, 5, 6, 7</tex> из массива <tex>A</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> больше, то элементы массива <tex>A</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''«галопа»галопа''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i - 1}, ...\dots, 10000 </tex> массива <tex>A</tex>. (<tex> ( \thicksim\log_log{2n}(n)</tex> сравнений<tex>)</tex>. После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</tex> копируются в результирующий.

Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, очевидно <tex> k </tex> = <tex dpi=150> \ulcorner left\fraclceil \mathtt{\dfrac{n}{minrun}} \urcorner </tex>. Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlog(n))</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. Можно сказать больше {{---}} пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны (данный факт хорошо виден на примере). Безусловно, после разбения массива на блоки длинной <tex>minrun</tex> последний блок может быть отличен от данного значения практически в 2 раза, но эти 20-30 элементов разницы при <tex>n</tex> порядка <tex>10^6right\rceil </tex> практически не повлияют на время работы.

Мы выяснилиГлавный факт, что при слиянии, длинна образовавшегося слитого массива увеличивается <tex>\approx</tex> 2 раза. Таким образом получаем, что каждый подмассив <tex>run_i</tex> может участвовать который нам понадобится для доказательства нужной оценки времени работы в не более <tex>O(n \log({n)})</tex> операций слияния{{---}} это то, а значит и каждый элемент будет задействован в сравниниях не более что сливаемые массивы '''всегда''' имеют примерно одинаковую длину. Можно сказать больше: пока <tex>O(log(n))k > 3</tex> разсливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Элементов Безусловно, после разбиения массива на блоки длиной <tex>n\mathtt{minrun}</tex>последний блок может быть отличен от данного значения, откуда получаем оценку но число элементов в нём не превосходит константы <tex>O(nlog(n))\mathtt{minrun}</tex>.

Также нужно сказать про [[Сортировка вставками | сортировку вставками]]Мы выяснили, которая используется для сортировки подмассивов <tex>run_i</tex>: что при слиянии, длинна образовавшегося слитого массива увеличивается в нашем случае, алгоритм работает за <tex>O(minrun + inv)\approx 2</tex>раза. Таким образом получаем, где что каждый подмассив <tex>inv</tex> \mathtt{{---run_i}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>k</tex>, получим, что сортировка всех блоков может занять участвовать в не более <tex>O(minrun + inv) * k = O(minrun + inv\log{n}) * </tex>операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex dpi=150>O(\ulcorner \fraclog{n}{minrun} \urcorner )</tex>раз. Что в худшем случае (Элементов <tex>invn</tex> = <tex dpi=150 > \frac{minrun*(minrun - 1)}{2} </tex>) может занимать , откуда получаем оценку в <tex>O(n + \log{n*minrun}) </tex> времени. Откуда видно, что константа <tex>minrun</tex> играет не малое значение: при большом <tex>minrun</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функцию растут с разной скоростью, поэтому видимо и был выбран вот такой оптимальный диапазон {{---}} от 32 до 64.

Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>\mathrm{run_i}</tex>: в нашем случае, алгоритм работает за <tex>O(\mathtt{minrun + inv})</tex>, где <tex>\mathtt{inv}</tex> {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>k</tex> получим, что сортировка всех блоков может занять <tex>O(\mathtt{minrun + inv}) \cdot k = O(\mathtt{minrun + inv}) \cdot </tex><tex>\left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil </tex>. Что в худшем случае <tex dpi>(\mathtt{inv = \dfrac{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>. ==См. также==* [[Сортировка кучей]]* [[Быстрая сортировка]] == Источники информации==

* [http://ru.wikipedia.org/wiki/Timsort Wikipedia {{- --}} Timsort] * [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr {{---}} Алгоритм сортировки Timsort]

[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]