Изменения
Timsort
,→Шаг 1. Вычисление minrun
'''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> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
===Шаг 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>и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
===Шаг №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охранять стабильность алгоритма (не делать бессмысленных перестановок)''.
[[Файл: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|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> копируются в результирующий.
== Доказательство времени работы алгоритма См. также==Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <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* [[Быстрая сортировка]]
* 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]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]][[Категория: Сортировкина сравнениях]]