Изменения

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

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

* По специальному алгоритму входной массив разделяется на подмассивы. * Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]] или [[Сортировка выбором | сортировкой выбором]]. * Отсортированные подмассивы собираются Рассмотрим теперь каждый шаг в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].  Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных '''Timsort''' существенно быстрее многих дргугих алгоритмов сортировкиотдельности.

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

* <tex>n</tex> — {{---}} размер входного массива.* <tex>\mathtt {run}</tex> {{---}} подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:** строго по убыванию <tex>\mathtt {a_{i} > a_{i + 1} > \dots} </tex>. ** нестрого по возрастанию <tex>\mathtt {a_{i} \leqslant a_{i + 1} \leqslant \dots} </tex>. * <tex>\mathtt {minrun} </tex> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.

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

# строго по убыванию Нетрудно понять, что после таких вычислений, <tex> a_\mathtt{\dfrac{{in}} > a_{i + 1minrun}} </tex> будет равно степени двойки или немного меньше степени двойки.* Конец.. '''int''' minRunLength(n): flag = 0 <font color=green>// будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой</texfont>. # нестрого по возрастанию '''while''' (n <tex> a_{i} \le a_{i + 1} \le ... geqslant</tex>. 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‎ |400px|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. Слияние ===Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно ''объединять подмассивы примерно равного размера''и 'Timsort'cохранять стабильность алгоритма'' состоит из нескольких шагов. [[Файл:Merge2mas.png|400px|right]]* Начало.* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex> индекс начала подмассива, размер подмассива <tex> > </tex>.===* '''Шаг 1'''. Берется первый упорядоченный подмассив.* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex> индекс начала текущего подмассива, его размер <tex> > </tex>.* '''Шаг 3'''. Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека (если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами).* '''Шаг №14'''. Повторяем пока выражение (<tex>Z > X + Y \wedge Y > X</tex>) не станет истинным ** Если размер стека не меньше <tex>2</tex> и <tex>Y \leqslant X </tex> {{---}} сливаем <tex>X</tex> c <tex>Y</tex>. Вычисление minrun===Число ** Если размер стека не меньше <tex>minrun3</tex> определяется на основе и <tex> n Z \leqslant X + Y</tex>{{---}} сливаем <tex>Y</tex> c <tex>\min(X, исходя из принципов:Z)</tex>. * '''Шаг 5'''. Переходим к шагу 2.* Конец

* Оно не должно быть слишком большимОсновная цель этой процедуры {{---}} сохранение баланса. Изменения будут выглядеть как на картинке, поскольку к подмассиву размера <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Шаг 0''' превращается . Создается временный массив в сортировку вставкамиразмере меньшего из сливаемых подмассивов.

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

===* '''Шаг №22'''. Разбиения Ставятся указатели текущей позиции на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: [[Файл:MinrunExample.png‎ |300px|thumb|right]]# Указатель текущего элемента ставится в начало входного массива.# Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так, чтобы они шли по возрастанию.# Если размер текущего <tex>run</tex> меньше <tex>minrun</tex>, тогда выбираются следующие за найденным подмассивом <tex>run</tex> первые элементы в количестве <tex> minrun - size(run) </tex>. Таким образом, на выходе будет получен подмассив размером большим или равный <tex>minrun</tex>, часть которого (в лучшем случае — он весь) упорядочена.# К данному подмассиву применяем сортировка вставками. Так как размер подмассива невелик большего и часть его уже упорядочена — сортировка работает эффективно. # Указатель текущего элемента ставится на следующий за подмассивом элемент. # Если конец входного временного массива не достигнут — переход к пункту 2, иначе — конец данного шага.

===* '''Шаг №33'''. Слияние===Если данные изначального массива достаточно близки к случайнымНа каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, то размер упорядоченных подмассивов близок к <tex>minrun</tex>копируется в новый отсортированный массив. Если Указатель текущего элемента перемещается в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размермассиве, превышающий <tex>minrun</tex>из которого был взят элемент.

* Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива'''Шаг 4'''. Для достижения эффективностиПредыдущий пункт повторяется, объединение должно удовлетворять требованиям:# Объединять подмассивы примерно равного размера# Сохранить стабильность алгоритма (пока один из массивов не делать бессмысленных перестановок). [[Файл:Merge2masзакончится.png|400px|right]]

Алгоритм шага №3:* Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>'''Шаг 5'''.* Берется первый упорядоченный подмассив.* Добавляется в стек пара данных <индекс начала текущего подмассива> <tex>-</tex> <его размер>.* Затем правило следующее. Пусть <tex>X,Y,Z - </tex> длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> – это последний элемент стека. # Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>Y > X</tex>) не станет истинным # Если количество элементов Все элементы оставшегося массива добавляются в стеке не меньше 3 и <tex>Z \leqslant X + Y</tex> – сливаем <tex>Y</tex> c <tex>min(X,Z)</tex>. Иначе Если <tex>Y \leqslant X </tex> – сливаем <tex>X</tex> c <tex>Y</tex>. # Возвращаемся в п.1конец нового массива.

Основная цель этой процедуры — сохранение баланса* Конец. Изменения будут выглядеть как ===Пример===Возьмем <tex>n = 356</tex>. При таком <tex>n</tex> <tex>\mathtt{minrun}</tex> оказался равным <tex>45</tex>. Ниже представлена работа алгоритма.Числа с закрывающей скобкой показывают номера шагов, на картинке, а значит и размеры которых произошло сливание нижестоящих подмассивов в стеке эффективны для дальнейшей сортировки слиянием.

===Описание процедуры слияния===* Создается временный массив в размере меньшего из сливаемых подмассивов. * Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>-</tex> правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.  * Ставятся указатели текущей позиции на первые элементы большего и временного массива[[Файл:Example.png|800px]]

* На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент. * Предыдущий пункт повторяется, пока один из массивов не закончится. * Все элементы оставшегося массива добавляются в конец нового массива. ===Модификация процедуры слияния подмассивов (Galloping Mode)===

<tex>A = {1, 2, 3, ...\dots, 9999, 10000}</tex> <tex>B = {20000, 20001, 20002, ..., 29999, 30000}</tex> Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»'''. Алгоритм следующий: * Начинается процедура слияния. * На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.

* Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается<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_log{2n}(n)</tex> сравнений<tex>)</tex>. После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</tex> копируются в результирующий.

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

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

Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в <tex> T(n) = T(run1\approx 2</tex> раза.size) + T(run2.size) + Таким образом получаем, что каждый подмассив <tex>\mathtt{run_i}</tex> может участвовать в не более <tex>O(run1.size + run2.size\log{n}) </tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex> \approx 2T(n/2) + O(\log{n}) \approx </tex> раз. Элементов <tex> 4T(n</4) + 2Otex>, откуда получаем оценку в <tex>O(n) \approx \dots \approx 2^log{kn}T(1) + kO(n) </tex>.

Осталось оценить Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>k\mathrm{run_i}</tex>. : в нашем случае, алгоритм работает за <tex>nO(\mathtt{minrun + inv})</minruntex>, где <tex>\mathtt{inv}</tex> {{--- количество сливаемых блоков}} число обменов элементов входного массива, откуда следуетравное числу инверсий. C учетом значения <tex>k</tex> получим, что сортировка всех блоков может занять <tex>2^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> k = logO(\mathtt{n\cdot minrun}) </tex> времени. Откуда видно, что константа <tex>\mathtt{minrun)}</tex> играет немалое значение: при большом <tex>\mathtt{minrun}</tex> слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после экспериментов на различных значениях и был выбран оптимальный диапазон {{---}} от <tex>32</tex> до <tex>64</tex>.

<tex>T(n) \approx 2^{k}T(1) + kO(n) </tex> = <tex> log(n/minrun) + </tex><tex>log(n/minrun)O(n)</tex> <tex> = O(nlog(n))См. </tex>также==* [[Сортировка кучей]] * [[Быстрая сортировка]]

== Источники информации==

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

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