Просмотр исходного текста страницы Timsort

== Timsort ==
 
'''Timsort''' — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.

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

== Основная идея алгоритма ==

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

<tex>*</tex>  Каждый подмассив сортируется [http://neerc.ifmo.ru/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>*</tex>  Отсортированные подмассивы собираются в единый массив с помощью модифицированной [http://neerc.ifmo.ru/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 сортировки слиянием].


Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных '''Timsort''' существенно быстрее многих дргугих алгоритмов сортировки.

== Алгоритм ==

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

<tex>*</tex>  <tex>n</tex>   — размер входного массива.

<tex>*</tex>  <tex>run</tex> — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:

# строго по убыванию <tex> a_{i} > a_{i + 1} > ...  </tex>.   
# нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ...  </tex>.   

<tex>*</tex>  <tex>minrun</tex> — минимальный размер подмассива, описанного в предыдущем пункте.   

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

<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''' превращается в сортировку вставками.

Таким образом, алгоритм расчета <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>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>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>.

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

Алгоритм шага №3:
# Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>.
# Берется первый упорядоченный подмассив.
# Добавляется в стек пара данных <индекс начала текущего подмассива> <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>*</tex> Создается временный массив в размере меньшего из сливаемых подмассивов.

<tex>*</tex> Меньший из подмассивов копируется во временный массив

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

<tex>*</tex> На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый 
отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.

<tex>*</tex> Предыдущий пункт повторяется, пока один из массивов не закончится.

<tex>*</tex> Все элементы оставшегося массива добавляются в конец нового массива.

===Модификация процедуры слияния подмассивов (Galloping Mode)===
Рассмотрим процедуру слияния двух массивов:

<tex>A = {1, 2, 3, ..., 9999, 10000}</tex>

<tex>B = {20000, 20001, 20002, ..., 29999, 30000}</tex>

Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»'''. Алгоритм следующий:

<tex>*</tex> Начинается процедура слияния.

<tex>*</tex> На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.

<tex>*</tex> Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.

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

Для вышеописанных массивов <tex> A, B </tex> алгоритм выглядит следующим образом:
Первые 7 итераций сравниваются числа <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}, ..., 10000 </tex> массива <tex>A</tex>. (<tex> \thicksim\log_{2}(n)</tex> сравнений). После того как конец массива <tex>A</tex> достигнут и известно, что он весь меньше <tex>B</tex>, нужные данные из массива <tex>A</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>  Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.

<tex>*</tex> [http://ru.wikipedia.org/wiki/Timsort Wikipedia - Timsort]

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


[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]