1632
правки
Изменения
Timsort
,rollbackEdits.php mass rollback
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слияниемразличные подходы.
Данный алгоритм является относительно новым и был изобретен в 2002 году придуман Тимом Петерсом(в честь него и назван) и основывается на том. На массивах данных, что в реальном мире сортируемые массивы данных часто которые содержат в себе упорядоченные подмассивы. На таким данных , алгоритм Тима Петерса существенно быстрее многих показывает себя намного лучше других алгоритмов сортировкисортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''.
== Основная идея алгоритма ==
Алгоритм '''Timsort''' состоит из нескольких шаговчастей:* Начало.* '''Шаг №11''': по специальному алгоритму входной . Входной массив разделяется на подмассивыфиксированной длины, вычисляемой определённым образом. * '''Шаг №22''': каждый . Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка пузырьком | сортировкой пузырьком]] или любой другой устойчивой сортировкой.* '''Шаг 3'''. Отсортированные подмассивы объединяются в один массив с помощью модифицированной [[Сортировка выбором слиянием | сортировкой выборомсортировки слиянием]].* Конец.
== Алгоритм ==
===Используемые понятия и комментарииОбозначения ===
* <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> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
===Шаг №22. Алгоритм разбиения на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <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охранять стабильность алгоритма (не делать бессмысленных перестановок)''.
[[Файл:Merge2mas.png|400px|right]]
* Начало.
* '''Шаг 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|900px800px]]
== Модификация процедуры слияния подмассивов (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 dpi=150> \ulcorner \frac{n}{minrun} \urcorner </tex>. Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <tex>О(nlog(n))</tex> {{---}} это то, что сливаемые массивы '''всегда''' имеют примерно одинаковую длинну. Можно сказать больше {{---}} пока <tex>k > 3</tex> сливаемые подмассивы будут именно одинаковой длинны (данный факт хорошо виден на примере). Безусловно, после разбения массива на блоки длинной <tex>minrun</tex> последний блок может быть отличен от данного значения практически в 2 раза, но эти 20-30 элементов разницы при <tex>n</tex> порядка <tex>10^6</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.
* Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
* [http://ru.wikipedia.org/wiki/Timsort Wikipedia {{- --}} Timsort] * [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr {{---}} Алгоритм сортировки Timsort]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]