Изменения

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

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

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

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

* <tex>n</tex>{{---}} размер входного массива.*<tex>\mathtt {run}</tex> {{---}} подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:** строго по убыванию <tex>\mathtt {a_{i} > a_{i + 1} > \dots} </tex>n. ** нестрого по возрастанию <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> \mathtt{\dfrac{n}{minrun}} </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.** Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex>run[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> * </tex> Оно не должно быть слишком большимОсновная цель этой процедуры {{---}} сохранение баланса. Изменения будут выглядеть как на картинке, поскольку к подмассиву размера <tex> minrun </tex> будет а значит и размеры подмассивов в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивахстеке эффективны для дальнейшей сортировки слиянием.

<tex> ===Описание процедуры слияния===* </tex> Оно не должно быть слишком маленьким, так как чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> n / minrun </tex> — ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размераНачало.

<tex>*</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>из которого был взят элемент.

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

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

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

===Описание процедуры слияния===<tex>*</tex> Создается временный массив в размере меньшего из сливаемых подмассивов[[Файл:Example.png|800px]]

<tex>*</tex> Меньший из == Модификация процедуры слияния подмассивов копируется во временный массив(Galloping Mode) ==Рассмотрим процедуру слияния двух массивов:

<tex>*A = {1, 2, 3, \dots, 9999, 10000}</tex> Ставятся указатели текущей позиции на первые элементы большего и временного массива.

<tex>*</tex> На каждом шаге рассматривается значение текущих элементов в большем и временном массивахB = {20000, 20001, берется меньший из них20002, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве\dots, из которого был взят элемент. <tex>*</tex> Предыдущий пункт повторяется29999, пока один из массивов не закончится. <tex>*30000}</tex> Все элементы оставшегося массива добавляются в конец нового массива. ===Модификация процедуры слияния подмассивов (Galloping Mode)===Рассмотрим процедуру слияния двух массивов:

Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге <tex>10000</tex> сравнений и <tex>A = {1, 2, 3, ..., 9999, 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, 2000122, 38, 7+2^{i - 1}, 20002\dots, 10000 </tex> массива <tex>A</tex> <tex>( \thicksim\log{n}</tex> сравнений<tex>)</tex>...После того как конец массива <tex>\mathtt{A}</tex> достигнут и известно, 29999что он весь меньше <tex>B</tex>, 30000}нужные данные из массива <tex>A</tex>копируются в результирующий.

Вышеуказанная процедура для них сработает== Доказательство времени работы алгоритма ==Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копированийчем их длины больше, тем дольше эти слияния будут происходить. Алгоритм На малом количестве длинных массивов хорошо помогает вышеописанный метод '''TimsortGalloping Mode''' предлагает в этом месте модификацию. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.Пусть <tex>k</tex> {{---}} число кусков, которая получила называет '''«галоп»'''на которые разбился наш исходный массив, очевидно <tex>k</tex> = <tex> \left\lceil \mathtt{\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>n</tex>, откуда получаем оценку в <tex>O(n\log{n})</tex>.

Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>*\mathrm{run_i}</tex> Если уже некоторое количество элементов : в нашем случае, алгоритм работает за <tex>O(в данной реализации алгоритма это \mathtt{minrun + inv})</tex>, где <tex>\mathtt{inv}</tex> {{---}} число равно 7) было взято из одного и того же обменов элементов входного массива — предполагается, равное числу инверсий. 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>.

<tex>==См. также==*</tex> В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.[[Сортировка кучей]]* [[Быстрая сортировка]]

Для вышеописанных массивов <tex> A, B </tex> алгоритм выглядит следующим образом:== Источники информации==Первые 7 итераций сравниваются числа <tex>1* Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", 2, 3, 4, 5, 6Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7</tex> из массива <tex>A</tex> с числом <tex>20000</tex>, так как <tex>20000</tex> большеChapter 53, то элементы массива <tex>A</tex> копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим '''«галопа»''': сравнивает с числом <tex>20000</tex> последовательно элементы <tex>8, 10, 14, 22, 38, 7+2^{i pp 467- 1}, ..., 10000 </tex> массива <tex>A</tex>. (<tex> \thicksim\log_{2}(n)</tex> сравнений). После того как конец массива <tex>A</tex> достигнут и известно, что он весь меньше <tex>B</tex>474, нужные данные из массива <tex>A</tex> копируются в результирующийJanuary 1993.

== Источники ==<tex>*</tex> Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7, Chapter 53, pp 467-474Python Language. — Apress, January 19932010. — 336 с.

<tex>*<[http:/tex> Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language/ru. — Apress, 2010. — 336 сwikipedia.org/wiki/Timsort Wikipedia {{---}} Timsort]

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

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