Изменения

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

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

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

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

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

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

* Нетрудно понять, что после таких вычислений, <tex>\mathtt{\dfrac{{n}}{minrun}} </tex> {{---}} минимальный размер подмассива, описанного в предыдущем пунктебудет степенью двойки.* Конец. '''int''' minRunLength(n): flag = 0 <font color=green>// будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой</font> '''while''' (n <tex> \geqslant</tex> 64) flag |= n & 1 n >>= 1 '''return''' n + flag

===Шаг №1. Вычисление minrun===Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов: * Не должно быть слишком большим, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах). * Оно не должно быть слишком маленьким, так как чем меньше подмассив {{---}} тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <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''' превращается в сортировку вставками. Таким образом, алгоритм расчета <tex> minrun </tex> не так уж сложен: берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой. int GetMinrun(int n) { int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */ while (n >= 64) { flag |= n & 1; n >>= 1; } return n + flag; } ===Шаг №2. Алгоритм разбиения на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <tex>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'''. Если конец входного массива не достигнут {{---}} переход к пункту 2шагу 1.

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

* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex> {{---}} <tex> < </tex>, размер подмассива<tex> > </tex>.* '''Шаг 1'''. Берется первый упорядоченный подмассив.* '''Шаг 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>Y 3</tex> и <tex>Z \leqslant X + Y</tex> {{---}} сливаем <tex>XY</tex> c <tex>Y\min(X,Z)</tex>. * Возвращаемся в п'''Шаг 5'''.6Переходим к шагу 2.

* Создается временный массив в размере меньшего из сливаемых подмассивовНачало.

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

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

* На каждом шаге рассматривается значение текущих элементов в большем '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элементвременного массива.

* Предыдущий пункт повторяется'''Шаг 3'''. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, пока один берется меньший из массивов не закончитсяних, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.

* Все элементы оставшегося массива добавляются в конец нового массива'''Шаг 4'''. Предыдущий пункт повторяется, пока один из массивов не закончится.

* '''Шаг 5'''.Все элементы оставшегося массива добавляются в конец нового массива. * Конец.===Пример===Возьмем <tex>n = 356</tex>. При таком <tex>n</tex> <tex>\mathtt{minrun}</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.Числа с закрывающей скобкой показывают номера шагов, на которых произошло сливание нижестоящих подмассивов.  [[Файл:Example.png|800px]] ==Модификация процедуры слияния подмассивов (Galloping Mode)===

<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''' предлагает в этом месте модификацию, которая получила называет '''«галоп»галоп'''. Алгоритм следующий:

* Начало.* '''Шаг 0'''. Начинается процедура слияния.* '''Шаг 1'''. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.* '''Шаг 2'''. Если уже некоторое количество элементов (например, в '''JDK 7''' это число равно 7) было взято из одного и того же массива {{---}} предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''галопа''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.* '''Шаг 3'''. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.* Конец.Для вышеописанных массивов <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{n}</tex> сравнений<tex>)</tex>. После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</tex> копируются в результирующий.

* == Доказательство времени работы алгоритма ==Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминаетсямалом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.Пусть <tex>k</tex> {{---}} число кусков, на которые разбился наш исходный массив, из какого именно подмассива был элементочевидно <tex>k</tex> = <tex> \left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil </tex>.

* Если уже некоторое количество элементов Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>O(в данной реализации алгоритма это число равно 7n \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>n</tex>, данные копируются целикомоткуда получаем оценку в <tex>O(n\log{n})</tex>.

Для вышеописанных массивов Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex> A, B \mathrm{run_i}</tex> : в нашем случае, алгоритм выглядит следующим образом:Первые 7 итераций сравниваются числа работает за <tex>1, 2, 3, 4, 5, 6, 7O(\mathtt{minrun + inv})</tex> из массива , где <tex>A\mathtt{inv}</tex> с числом {{---}} число обменов элементов входного массива, равное числу инверсий. C учетом значения <tex>20000k</tex>получим, так как что сортировка всех блоков может занять <tex>20000O(\mathtt{minrun + inv}) \cdot k = O(\mathtt{minrun + inv}) \cdot </tex> больше, то элементы массива <tex>A\left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil </tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит Что в режим '''«галопа»''': сравнивает с числом худшем случае <texdpi>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^(\mathtt{inv = \dfrac{i minrun(minrun - 1)}, ..., 10000 {2}} )</tex> массива может занимать <tex>AO(\mathtt{n \cdot minrun}) </tex>времени. (Откуда видно, что константа <tex> \thicksim\log_mathtt{2minrun}(n)</tex> сравнений). После того как конец массива играет немалое значение: при большом <tex>A\mathtt{minrun}</tex> достигнут слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и известно, что он весь меньше ещё после экспериментов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>B32</tex>, нужные данные из массива до <tex>A64</tex> копируются в результирующий.

== Доказательство времени работы алгоритма См. также==Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlog(n))</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. То есть подмассивы <tex>run_1</tex>, <tex>run_2</tex> такие, что <tex>run_1.size \gg run_2.size</tex> будут слиты только тогда, когда размеры соответствующих подмассивов, в которые они войдут будут примерно равны. Например, если на вход подан массив <tex>64, 32, 16, 8, 4, 2, 1</tex>, то, временно забыв про понятие <tex>minrun</tex>, '''Timsort''' сделает следующие слияния:# 64, 32, 16, 8, 4, 2, 1, 1# 64, 32, 16, 8, 4, 2, 2# 64, 32, 16, 8, 4, 4# 64, 32, 16, 8, 8# 64, 32, 16, 16# 64, 32, 32# 64, 64* [[Сортировка кучей]]# 128* [[Быстрая сортировка]]

При сливании двух подмассивов <tex>run_1</tex>,<tex>run_2</tex> будет произведенно <tex>O(run_1.size + run_2.size)</tex> операций сравнения. Результирующий подмассив <tex>run_{12}</tex> будет удовлетворять выражению <tex>run_{12}.size \approx 2run_1.size \approx 2run_2.size </tex>. Таким образом, каждый подмассив <tex>run_i</tex> может поучаствовать в не более <tex>O(log(n))</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(log(n))</tex> раз. Элементов <tex>n</tex>, откуда и получаем соответствующую оценку в <tex>O(nlog(n))</tex> == Источники информации==

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

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