1632
правки
Изменения
м
== Timsort ==
Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван). В настоящее время == Основная идея алгоритма ==Алгоритм '''Timsort''' является стандартным алгоритмом сортировки в состоит из нескольких частей:* Начало.* '''PythonШаг 1'''. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.* '''OpenJDK 7Шаг 2''' и реализован в . Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка пузырьком | сортировкой пузырьком]] или любой другой устойчивой сортировкой.* '''Android JDK 1.5Шаг 3'''. Чтобы понять почему — достаточно взглянуть на таблицу из Википедии:Отсортированные подмассивы объединяются в один массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].* Конец. Рассмотрим теперь каждый шаг в отдельности. == Алгоритм ==
[[Файл:Таблица26007.png]]=== Обозначения ===
== Основная идея алгоритма ==* <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> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
Данный алгоритм основывается Основная цель этой процедуры {{---}} сохранение баланса. Изменения будут выглядеть как на томкартинке, что а значит и размеры подмассивов в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных '''Timsort''' существенно быстрее многих дргугих алгоритмов стеке эффективны для дальнейшей сортировкислиянием.
===Используемые понятия и комментарии===* '''Шаг 0'''. Создается временный массив в размере меньшего из сливаемых подмассивов.
<tex>\bullet</tex> <tex>n</tex> — размер входного массива* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив {{---}} правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
<tex>\bullet</tex> <tex>run</tex> — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:* '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
# строго по убыванию <tex> a_{i} > a_{i + 1} > * '''Шаг 3'''.На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив.Указатель текущего элемента перемещается в массиве, из которого был взят элемент. </tex>. # нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ... </tex>.
<tex>\bullet</tex> <tex>minrun</tex> — минимальный размер подмассива* '''Шаг 4'''. Предыдущий пункт повторяется, описанного в предыдущем пунктепока один из массивов не закончится.
Алгоритм * '''TimsortШаг 5''' состоит из нескольких шагов:===Шаг №1. Вычисление minrun===Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов:Все элементы оставшегося массива добавляются в конец нового массива.
<tex> \bullet </tex> Оно не должно быть слишком маленьким, так как чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> n / minrun </tex> — ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера[[Файл:Example.png|800px]]
<tex>\bullet</tex> Согласно авторским экспериментам: # При <tex> minrun > 256 </tex> нарушается пункт <tex>1</tex>.# При <tex> minrun < 8 </tex> нарушается пункт <tex>2</tex>.# Наиболее эффективные значения <tex> minrun </tex> из диапозона <tex> == Модификация процедуры слияния подмассивов (32; 65Galloping Mode) </tex>.==# Исключение — если <tex> n < 64 </tex>, тогда <tex> n = minrun </tex> и '''Timsort''' превращается в сортировку вставками.Рассмотрим процедуру слияния двух массивов:
Таким образом, алгоритм расчета <tex> minrun A = {1, 2, 3, \dots, 9999, 10000}</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>minrun</tex>. Алгоритм работы этого шага: [[Файл:Массив.png|300px|thumb|right]]# Указатель текущего элемента ставится в начало входного массива.# Начиная с текущего элементаB = {20000, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению20001, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так20002, чтобы они шли по возрастанию.# Если размер текущего <tex>run</tex> меньше <tex>minrun</tex>\dots, тогда выбираются следующие за найденным подмассивом <tex>run</tex> элементы в количестве <tex> minrun - size(run) </tex>. Таким образом29999, на выходе будет получен подмассив размером большим или равный <tex>minrun30000}</tex>, часть которого (в лучшем случае — он весь) упорядочена.# К данному подмассиву применяем сортировка вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает эффективно. # Указатель текущего элемента ставится на следующий за подмассивом элемент. # Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.
===Шаг №3Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. Слияние===Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к В итоге <tex>minrun10000</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий сравнений и <tex>minrun10000</tex>копирований. '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''галоп'''.Алгоритм следующий:
Алгоритм шага №3:== Доказательство времени работы алгоритма ==# Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить.# Берется первый упорядоченный подмассивНа малом количестве длинных массивов хорошо помогает вышеописанный метод '''Galloping Mode'''.# Добавляется в стек пара данных <индекс начала текущего подмассива> <tex>-</tex> <его размер>Хоть он и не даёт асимптотического выигрыша, но уменьшает константу.# При выполнении двух последующих правил выполняется процедура слияния текущего подмассива с предыдущими.Если Пусть <tex>X, Y, Zk</tex> — размеры трёх верхних подмассивов в стеке{{---}} число кусков, то:# <tex>X > Y + Z</tex># <tex>Y > Z</tex> Если одно из правил нарушается — на которые разбился наш исходный массив , очевидно <tex>Y</tex> сливается с меньшим из массивов <tex>Xk</tex>, = <tex>Z\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(\bulletlog{n})</tex> Создается временный массив раз. Элементов <tex>n</tex>, откуда получаем оценку в размере меньшего из сливаемых подмассивов<tex>O(n\log{n})</tex>.
<tex>\bullet</tex> Ставятся указатели текущей позиции на первые элементы большего и временного массива==См.также==* [[Сортировка кучей]]* [[Быстрая сортировка]]
<tex>\bullet</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>\bullet</tex> Предыдущий пункт повторяется* Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, пока один из массивов не закончится2010. — 336 с.
<tex>\bullet<* [http:/tex> Все элементы оставшегося массива добавляются в конец нового массива/ru.wikipedia.org/wiki/Timsort Wikipedia {{---}} Timsort]
== Источники ==<tex>\bullet<* [http:/tex> Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual ACM/habrahabr.ru/company/infopulse/blog/133303/ Habrahabr {{-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7, Chapter 53, pp 467-474, January 1993. }} Алгоритм сортировки Timsort]
<tex>\bullet</tex> Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
<tex>\bullet</tex> [http://ru.wikipedia.org/wiki/Timsort Wikipedia - Timsort]
<tex>\bullet</tex> [http[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировка]][[Категория://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки TimsortСортировки на сравнениях]]
rollbackEdits.php mass rollback
'''Timsort''' — {{---}} гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слияниемразличные подходы.
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченные подмассивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
===Шаг 1. Вычисление minrun===* Начало.* '''Шаг 0'''. Число <tex>\bulletmathtt{minrun}</tex> определяется на основе <tex>n</tex>, исходя из следующих принципов:** Не должно быть слишком большим, поскольку к подмассиву размера <tex>\mathtt{minrun}</tex> будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).** По специальному алгоритму входной массив разделяется Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> \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>\bulletmathtt{\dfrac{{n}}{minrun}} </tex> Каждый подмассив сортируется [httpбудет равно степени двойки или немного меньше степени двойки.* Конец. '''int''' minRunLength(n): flag = 0 <font color=green>//neerc.ifmo.ruбудет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой</wikifont> '''while''' (n <tex> \geqslant</index.php?titletex> 64) flag |= n & 1 n >>=%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 сортировкой вставками].1 '''return''' n + flag
===Шаг 2. Алгоритм разбиения на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>\bulletmathtt{minrun}</tex> Отсортированные . Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>\mathtt{minrun}</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы собираются могут иметь размер, превышающий <tex>\mathtt{minrun}</tex>. [[Файл:MinrunExample.png |400px|right]]* Начало.* '''Шаг 0'''. Указатель текущего элемента ставится в единый массив начало входного массива.* '''Шаг 1'''. Начиная с помощью модифицированной [http:текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>\mathtt{run}</tex>. По определению, в <tex>\mathtt{run}</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления <tex>\mathtt{run}</neerctex> для текущего массива элементы переставляются так, чтобы они шли по возрастанию.ifmo* '''Шаг 2'''.ruЕсли размер текущего <tex>\mathtt{run}</tex> меньше <tex>\mathtt{minrun}</tex>, тогда выбираются следующие за найденным подмассивом <tex>\mathtt{run}</wikitex> элементы в количестве <tex> \mathtt{minrun - size(run)} </indextex>.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>\mathtt{minrun}</tex>, часть которого (в лучшем случае {{---}} он весь) упорядочена.* '''Шаг 3'''. К данному подмассиву применяем сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена {{---}} сортировка работает эффективно. * '''Шаг 4'''. Указатель текущего элемента ставится на следующий за подмассивом элемент. * '''Шаг 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>n = 356</tex>. При таком <tex>n</tex> <tex> \bullet mathtt{minrun}</tex> Оно не должно быть слишком большим, поскольку к подмассиву размера оказался равным <tex> minrun 45</tex> будет в дальнейшем применена сортировка вставками. Ниже представлена работа алгоритма.Числа с закрывающей скобкой показывают номера шагов, а она эффективна только на небольших массивахкоторых произошло сливание нижестоящих подмассивов.
* Начало.* '''Шаг 0'''. Начинается процедура слияния.* '''Шаг 1'''. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.* '''Шаг 2'''. Если уже некоторое количество элементов (например, в '''JDK 7''' это число равно 7) было взято из одного и того же массива {{---}} предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''галопа''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.* '''Шаг 3'''. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.* Конец.Для вышеописанных массивов <tex>\bulletmathtt{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> копируются в результирующий.png|right]]
Также нужно сказать про [[Сортировка вставками | сортировку вставками]], которая используется для сортировки подмассивов <tex>\bulletmathrm{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>.
