Timsort — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание процедуры слияния)
м (rollbackEdits.php mass rollback)
 
(не показана 51 промежуточная версия 11 участников)
Строка 1: Строка 1:
== Timsort ==
 
 
   
 
   
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.
+
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий различные подходы.
  
Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван) и основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таким данных алгоритм Тима Петерса существенно быстрее многих других алгоритмов сортировки. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''', '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''.
+
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченные подмассивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
  
 
== Основная идея алгоритма ==
 
== Основная идея алгоритма ==
Алгоритм '''Timsort''' состоит из нескольких шагов:
+
Алгоритм '''Timsort''' состоит из нескольких частей:
 
+
* Начало.
* '''Шаг №1''': по специальному алгоритму входной массив разделяется на подмассивы.
+
* '''Шаг 1'''. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
 
+
* '''Шаг 2'''. Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка пузырьком | сортировкой пузырьком]] или любой другой устойчивой сортировкой.
* '''Шаг №2''': каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]] или [[Сортировка выбором | сортировкой выбором]].
+
* '''Шаг 3'''. Отсортированные подмассивы объединяются в один массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].
 +
* Конец.
  
* '''Шаг №3''': отсортированные подмассивы собираются в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].
+
Рассмотрим теперь каждый шаг в отдельности.
  
 
== Алгоритм ==
 
== Алгоритм ==
  
===Используемые понятия и комментарии===
+
=== Обозначения ===
  
 
* <tex>n</tex> {{---}} размер входного массива.
 
* <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> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.
  
* <tex>run</tex> {{---}} некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
+
===Шаг 1. Вычисление minrun===
** строго по убыванию <tex> a_{i} > a_{i + 1} > ..</tex>.  
+
* Начало.
** нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ..</tex>.  
+
* '''Шаг 0'''. Число <tex>\mathtt{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>minrun</tex> {{---}} минимальный размер подмассива, описанного в предыдущем пункте.   
+
Нетрудно понять, что после таких вычислений, <tex>\mathtt{\dfrac{{n}}{minrun}} </tex> будет равно степени двойки или немного меньше степени двойки.
 +
* Конец.  
 +
   '''int''' minRunLength(n):
 +
    flag = 0        <font color=green>// будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой</font>
 +
    '''while''' (n <tex> \geqslant</tex> 64)
 +
      flag |= n & 1
 +
      n >>= 1
 +
    '''return''' n + flag
  
===Шаг №1. Вычисление minrun===
+
===Шаг 2. Алгоритм разбиения на подмассивы и их сортировка===
Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов:
+
На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>\mathtt{minrun}</tex>. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>\mathtt{minrun}</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>\mathtt{minrun}</tex>. [[Файл:MinrunExample.png‎ |400px|right]]
 
 
* Не должно быть слишком большим, поскольку к подмассиву размера <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>minrun</tex>. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>. [[Файл:MinrunExample.png‎ |300px|thumb|right]]
 
 
* Начало.
 
* Начало.
* Указатель текущего элемента ставится в начало входного массива.
+
* '''Шаг 0'''. Указатель текущего элемента ставится в начало входного массива.
* Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>run</tex>. По определению, в <tex>run</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию {{---}} элементы переставляются так, чтобы они шли по возрастанию.
+
* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>\mathtt{run}</tex>. По определению, в <tex>\mathtt{run}</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления <tex>\mathtt{run}</tex> для текущего массива элементы переставляются так, чтобы они шли по возрастанию.
* Если размер текущего <tex>run</tex> меньше <tex>minrun</tex>, тогда выбираются следующие за найденным подмассивом <tex>run</tex> элементы в количестве <tex> minrun - size(run) </tex>. Таким образом, на выходе будет получен подмассив размером большим или равный <tex>minrun</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'''. Указатель текущего элемента ставится на следующий за подмассивом элемент.  
* Если конец входного массива не достигнут {{---}} переход к пункту 2
+
* '''Шаг 5'''. Если конец входного массива не достигнут {{---}} переход к шагу 1.
 
* Конец.
 
* Конец.
  
===Шаг №3. Слияние===
+
=== Шаг 3. Слияние ===
Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно ''объединять подмассивы примерно равного размера'' и ''cохранять стабильность алгоритма (не делать бессмысленных перестановок)''.  
+
Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно ''объединять подмассивы примерно равного размера'' и ''cохранять стабильность алгоритма''.  
 
[[Файл:Merge2mas.png|400px|right]]
 
[[Файл:Merge2mas.png|400px|right]]
 
* Начало.
 
* Начало.
* Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex> {{---}} <tex> < </tex>размер подмассива<tex> > </tex>.
+
* '''Шаг 0'''. Создается пустой стек пар <tex> < </tex> индекс начала подмассива, размер подмассива <tex> > </tex>.
* Берется первый упорядоченный подмассив.
+
* '''Шаг 1'''. Берется первый упорядоченный подмассив.
* Добавляется в стек пара данных <tex> < </tex>индекс начала текущего подмассива<tex> > </tex> {{---}} <tex> < </tex>его размер<tex> > </tex>.
+
* '''Шаг 2'''. Добавляется в стек пара данных <tex> < </tex> индекс начала текущего подмассива, его размер <tex> > </tex>.
* Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека.  
+
* '''Шаг 3'''. Пусть <tex>X,Y,Z </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> {{---}} это последний элемент стека (если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами).
* Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>Y > X</tex>) не станет истинным  
+
* '''Шаг 4'''. Повторяем пока выражение (<tex>Z > X + Y \wedge Y > X</tex>) не станет истинным  
** Если размер стека не меньше 3 и <tex>Z \leqslant X + Y</tex> {{---}} сливаем <tex>Y</tex> c <tex>min(X,Z)</tex>.  
+
** Если размер стека не меньше <tex>2</tex> и <tex>Y \leqslant X </tex> {{---}} сливаем <tex>X</tex> c <tex>Y</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>.  
* Возвращаемся в п.6.
+
* '''Шаг 5'''. Переходим к шагу 2.
 
* Конец
 
* Конец
  
Строка 77: Строка 70:
  
 
===Описание процедуры слияния===
 
===Описание процедуры слияния===
* Создается временный массив в размере меньшего из сливаемых подмассивов.
+
* Начало.
  
* Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив <tex>-</tex> правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.  
+
* '''Шаг 0'''. Создается временный массив в размере меньшего из сливаемых подмассивов.
  
* Ставятся указатели текущей позиции на первые элементы большего и временного массива.
+
* '''Шаг 1'''. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив {{---}} правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.  
  
* На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
+
* '''Шаг 2'''. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
  
* Предыдущий пункт повторяется, пока один из массивов не закончится.
+
* '''Шаг 3'''. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
  
* Все элементы оставшегося массива добавляются в конец нового массива.
+
* '''Шаг 4'''. Предыдущий пункт повторяется, пока один из массивов не закончится.
  
===Модификация процедуры слияния подмассивов (Galloping Mode)===
+
* '''Шаг 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, ..., 9999, 10000}</tex>
+
<tex>A = {1, 2, 3, \dots, 9999, 10000}</tex>
  
<tex>B = {20000, 20001, 20002, ..., 29999, 30000}</tex>
+
<tex>B = {20000, 20001, 20002, \dots, 29999, 30000}</tex>
  
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге 10000 сравнений и 10000 копирований. Алгоритм '''Timsort''' предлагает в этом месте модификацию, которая получила называет '''«галоп»'''. Алгоритм следующий:
+
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге <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> \left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil </tex>.  
  
* Если уже некоторое количество элементов (в данной реализации алгоритма это число равно 7) было взято из одного и того же массива {{---}} предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим '''«галопа»''', то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
+
Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <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> A, B </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>.
Первые 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>О(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
 
  
При сливании двух подмассивов <tex>run_1</tex>,<tex>run_2</tex> будет произведенно <tex>O(run_1.size + run_2.size)</tex> операций сравнения. Результирующий подмассив <tex>run_{12}</tex> будет удовлетворять выражению <tex>run_{12}.size \approx 2run_1.size \approx 2run_2.size </tex>. Таким образом, каждый подмассив <tex>run_i</tex> может поучаствовать в не более <tex>O(log(n))</tex> операций слияния, а значит и каждый элемент будет задействован в сравниниях не более <tex>O(log(n))</tex> раз. Элементов <tex>n</tex>, откуда и получаем соответствующую оценку в <tex>O(nlog(n))</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.  
 
* 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 с.
 
* Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
  
* [http://ru.wikipedia.org/wiki/Timsort Wikipedia - Timsort]
+
* [http://ru.wikipedia.org/wiki/Timsort Wikipedia {{---}} Timsort]
 +
 
 +
* [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr {{---}} Алгоритм сортировки Timsort]
  
* [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
 
  
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировки]]
+
[[Категория: Сортировка]]
 +
[[Категория: Сортировки на сравнениях]]

Текущая версия на 19:26, 4 сентября 2022

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

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

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

Алгоритм Timsort состоит из нескольких частей:

  • Начало.
  • Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
  • Шаг 2. Каждый подмассив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
  • Шаг 3. Отсортированные подмассивы объединяются в один массив с помощью модифицированной сортировки слиянием.
  • Конец.

Рассмотрим теперь каждый шаг в отдельности.

Алгоритм

Обозначения

  • [math]n[/math] — размер входного массива.
  • [math]\mathtt {run}[/math] — подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
    • строго по убыванию [math]\mathtt {a_{i} \gt a_{i + 1} \gt \dots} [/math].
    • нестрого по возрастанию [math]\mathtt {a_{i} \leqslant a_{i + 1} \leqslant \dots} [/math].
  • [math]\mathtt {minrun} [/math] — минимальный размер подмассива, описанного в предыдущем пункте.

Шаг 1. Вычисление minrun

  • Начало.
  • Шаг 0. Число [math]\mathtt{minrun}[/math] определяется на основе [math]n[/math], исходя из следующих принципов:
    • Не должно быть слишком большим, поскольку к подмассиву размера [math]\mathtt{minrun}[/math] будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).
    • Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для [math] \mathtt{\dfrac{n}{minrun}} [/math]степень двойки. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
    • Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону [math] [32; 65) [/math] (подробнее о том, почему так, будет сказано ниже).
    • Исключение: если [math] n \lt 64 [/math], тогда [math] n = \mathtt{minrun} [/math] и Timsort превращается в сортировку вставками.
  • Шаг 1. Берем старшие 6 бит числа [math]n[/math] и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.

Нетрудно понять, что после таких вычислений, [math]\mathtt{\dfrac{{n}}{minrun}} [/math] будет равно степени двойки или немного меньше степени двойки.

  • Конец.
 int minRunLength(n):
   flag = 0         // будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой
   while (n [math] \geqslant[/math] 64)
     flag |= n & 1
     n >>= 1
   return n + flag

Шаг 2. Алгоритм разбиения на подмассивы и их сортировка

На данном этапе у нас есть входной массив, его размер [math]n[/math] и вычисленное число [math]\mathtt{minrun}[/math]. Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к [math]\mathtt{minrun}[/math],. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий [math]\mathtt{minrun}[/math].
MinrunExample.png
  • Начало.
  • Шаг 0. Указатель текущего элемента ставится в начало входного массива.
  • Шаг 1. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива [math]\mathtt{run}[/math]. По определению, в [math]\mathtt{run}[/math] однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления [math]\mathtt{run}[/math] для текущего массива элементы переставляются так, чтобы они шли по возрастанию.
  • Шаг 2. Если размер текущего [math]\mathtt{run}[/math] меньше [math]\mathtt{minrun}[/math], тогда выбираются следующие за найденным подмассивом [math]\mathtt{run}[/math] элементы в количестве [math] \mathtt{minrun - size(run)} [/math]. Таким образом, на выходе будет получен подмассив размером большим или равным [math]\mathtt{minrun}[/math], часть которого (в лучшем случае — он весь) упорядочена.
  • Шаг 3. К данному подмассиву применяем сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает эффективно.
  • Шаг 4. Указатель текущего элемента ставится на следующий за подмассивом элемент.
  • Шаг 5. Если конец входного массива не достигнут — переход к шагу 1.
  • Конец.

Шаг 3. Слияние

Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно объединять подмассивы примерно равного размера и cохранять стабильность алгоритма.

Merge2mas.png
  • Начало.
  • Шаг 0. Создается пустой стек пар [math] \lt [/math] индекс начала подмассива, размер подмассива [math] \gt [/math].
  • Шаг 1. Берется первый упорядоченный подмассив.
  • Шаг 2. Добавляется в стек пара данных [math] \lt [/math] индекс начала текущего подмассива, его размер [math] \gt [/math].
  • Шаг 3. Пусть [math]X,Y,Z [/math] — длины верхних трех интервалов, которые лежат в стеке. Причем [math]X[/math] — это последний элемент стека (если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами).
  • Шаг 4. Повторяем пока выражение ([math]Z \gt X + Y \wedge Y \gt X[/math]) не станет истинным
    • Если размер стека не меньше [math]2[/math] и [math]Y \leqslant X [/math] — сливаем [math]X[/math] c [math]Y[/math].
    • Если размер стека не меньше [math]3[/math] и [math]Z \leqslant X + Y[/math] — сливаем [math]Y[/math] c [math]\min(X,Z)[/math].
  • Шаг 5. Переходим к шагу 2.
  • Конец

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

Описание процедуры слияния

  • Начало.
  • Шаг 0. Создается временный массив в размере меньшего из сливаемых подмассивов.
  • Шаг 1. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив — правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
  • Шаг 2. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
  • Шаг 3. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
  • Шаг 4. Предыдущий пункт повторяется, пока один из массивов не закончится.
  • Шаг 5.Все элементы оставшегося массива добавляются в конец нового массива.
  • Конец.

Пример

Возьмем [math]n = 356[/math]. При таком [math]n[/math] [math]\mathtt{minrun}[/math] оказался равным [math]45[/math]. Ниже представлена работа алгоритма. Числа с закрывающей скобкой показывают номера шагов, на которых произошло сливание нижестоящих подмассивов.

Example.png

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

Рассмотрим процедуру слияния двух массивов:

[math]A = {1, 2, 3, \dots, 9999, 10000}[/math]

[math]B = {20000, 20001, 20002, \dots, 29999, 30000}[/math]

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

  • Начало.
  • Шаг 0. Начинается процедура слияния.
  • Шаг 1. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
  • Шаг 2. Если уже некоторое количество элементов (например, в JDK 7 это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим галопа, то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
  • Шаг 3. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.
  • Конец.

Для вышеописанных массивов [math]\mathtt{A, B}[/math] алгоритм выглядит следующим образом: Первые [math]7[/math] итераций сравниваются числа [math]1, 2, 3, 4, 5, 6, 7[/math] из массива [math]A[/math] с числом [math]20000[/math], так как [math]20000[/math] больше, то элементы массива [math]A[/math] копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим галопа: сравнивает с числом [math]20000[/math] последовательно элементы [math]8, 10, 14, 22, 38, 7+2^{i - 1}, \dots, 10000 [/math] массива [math]A[/math] [math]( \thicksim\log{n}[/math] сравнений[math])[/math]. После того как конец массива [math]\mathtt{A}[/math] достигнут и известно, что он весь меньше [math]B[/math], нужные данные из массива [math]A[/math] копируются в результирующий.

Доказательство времени работы алгоритма

Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод Galloping Mode. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу. Пусть [math]k[/math] — число кусков, на которые разбился наш исходный массив, очевидно [math]k[/math] = [math] \left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil [/math].

Главный факт, который нам понадобится для доказательства нужной оценки времени работы в [math]O(n \log{n})[/math] — это то, что сливаемые массивы всегда имеют примерно одинаковую длину. Можно сказать больше: пока [math]k \gt 3[/math] сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной [math]\mathtt{minrun}[/math] последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы [math]\mathtt{minrun}[/math].

Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в [math]\approx 2[/math] раза. Таким образом получаем, что каждый подмассив [math]\mathtt{run_i}[/math] может участвовать в не более [math]O(\log{n})[/math] операций слияния, а значит и каждый элемент будет задействован в сравниниях не более [math]O(\log{n})[/math] раз. Элементов [math]n[/math], откуда получаем оценку в [math]O(n\log{n})[/math].

Также нужно сказать про сортировку вставками, которая используется для сортировки подмассивов [math]\mathrm{run_i}[/math]: в нашем случае, алгоритм работает за [math]O(\mathtt{minrun + inv})[/math], где [math]\mathtt{inv}[/math] — число обменов элементов входного массива, равное числу инверсий. C учетом значения [math]k[/math] получим, что сортировка всех блоков может занять [math]O(\mathtt{minrun + inv}) \cdot k = O(\mathtt{minrun + inv}) \cdot [/math][math]\left\lceil \mathtt{\dfrac{n}{minrun}} \right\rceil [/math]. Что в худшем случае [math](\mathtt{inv = \dfrac{minrun(minrun - 1)}{2}} )[/math] может занимать [math]O(\mathtt{n \cdot minrun}) [/math] времени. Откуда видно, что константа [math]\mathtt{minrun}[/math] играет немалое значение: при большом [math]\mathtt{minrun}[/math] слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после экспериментов на различных значениях и был выбран оптимальный диапазон — от [math]32[/math] до [math]64[/math].

См. также

Источники информации

  • 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 с.