Изменения

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

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

<tex>*</tex> По специальному алгоритму входной массив разделяется на подмассивыРассмотрим теперь каждый шаг в отдельности.

== Алгоритм == === Обозначения === * <tex>n</tex> {{---}} размер входного массива.*<tex>\mathtt {run}</tex> Каждый {{---}} подмассив сортируется [httpво входном массиве, который обязан быть упорядоченным одним из двух способов:** строго по убыванию <tex>\mathtt {a_{i} > a_{i + 1} > \dots} </tex>. ** нестрого по возрастанию <tex>\mathtt {a_{i} \leqslant a_{i + 1} \leqslant \dots} </neerctex>.ifmo.ru * <tex>\mathtt {minrun} </wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8 сортировкой вставками]tex> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.

===Шаг 1. Вычисление minrun===* Начало.* '''Шаг 0'''. Число <tex>\mathtt{minrun}</tex> определяется на основе <tex>n</tex>, исходя из следующих принципов:** Не должно быть слишком большим, поскольку к подмассиву размера <tex>\mathtt{minrun}</tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).** Отсортированные подмассивы собираются в единый массив с помощью модифицированной Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> \mathtt{\dfrac{n}{minrun}} </tex> {{---}} ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.** Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону <tex> [http32; 65) </tex> (подробнее о том, почему так, будет сказано ниже). ** Исключение:если <tex> n < 64 </tex>, тогда <tex> n = \mathtt{minrun} </neerctex> и '''Timsort''' превращается в сортировку вставками.ifmo* '''Шаг 1'''.ruБерем старшие 6 бит числа <tex>n</wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC сортировки слиянием]tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.

Данный алгоритм основывается ===Шаг 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'''. Указатель текущего элемента ставится на следующий за подмассивом элемент. * '''TimsortШаг 5''' существенно быстрее многих дргугих алгоритмов сортировки. Если конец входного массива не достигнут {{---}} переход к шагу 1.* Конец.

== Алгоритм =Шаг 3. Слияние ===Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно ''объединять подмассивы примерно равного размера'' и ''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> {{---}} это последний элемент стека (если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами).* '''Шаг 4'''. Повторяем пока выражение (<tex>Z > X + Y \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>. * '''Шаг 5'''. Переходим к шагу 2.* Конец

===Используемые понятия Основная цель этой процедуры {{---}} сохранение баланса. Изменения будут выглядеть как на картинке, а значит и комментарии===размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.

<tex>===Описание процедуры слияния===*</tex> <tex>n</tex> — размер входного массиваНачало.

<tex>*</tex> <tex>run</tex> — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним '''Шаг 0'''. Создается временный массив в размере меньшего из двух способов:сливаемых подмассивов.

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

<tex>*</tex> <tex>minrun</tex> — минимальный размер подмассива, описанного в предыдущем пункте'''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.

Алгоритм * '''TimsortШаг 3''' состоит . На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из нескольких шагов:===Шаг №1них, копируется в новый отсортированный массив. Вычисление minrun===Число <tex>minrun</tex> определяется на основе <tex> n </tex>Указатель текущего элемента перемещается в массиве, исходя из принципов:которого был взят элемент.

<tex> * </tex> Оно '''Шаг 4'''. Предыдущий пункт повторяется, пока один из массивов не должно быть слишком большим, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивахзакончится.

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

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

Таким образом, алгоритм расчета <tex> minrun </tex> не так уж сложен[[Файл: берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевойExample. int GetMinrun(int n) { int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */ while (n >= 64) { flag png|= n & 1; n >>= 1; } return n + flag; }800px]]

===Шаг №2. Разбиения на подмассивы и их сортировка=Модификация процедуры слияния подмассивов (Galloping Mode) ==На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: [[ФайлРассмотрим процедуру слияния двух массивов:Массив.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, иначе — конец данного шага.

===Шаг №3. Слияние===Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоныA = {1, 2, 3, \dots, то упорядоченные подмассивы могут иметь размер9999, превышающий <tex>minrun10000}</tex>.

<tex>*B = {20000, 20001, 20002, \dots, 29999, 30000}</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:# Объединять подмассивы примерно равного размера# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:Слияние.png|right]]

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

Основная цель этой процедуры — сохранение баланса* Начало. Изменения будут выглядеть * '''Шаг 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(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> На каждом шаге рассматривается значение текущих {{---}} число обменов элементов входного массива, равное числу инверсий. 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>== Источники информации==*</tex> Все элементы оставшегося массива добавляются в конец нового массиваPeter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7, Chapter 53, pp 467-474, 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]

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