Какая временная сложность у алгоритма сортировки timsort

Алгоритм сортировки Timsort

Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.

Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.

Timsort

Timsort — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом. В настоящее время Timsort является стандартным алгоритмом сортировки в Python, OpenJDK 7 [1] и реализован в Android JDK 1.5 [2] . Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки [3] .

Содержание

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

По специальному алгоритму входной массив разделяется на подмассивы.
Каждый подмассив сортируется сортировкой вставками.
Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием.

Принципиальные особенности алгоритма в деталях, а именно в алгоритме разделения и модификации сортировки слиянием.

Алгоритм

Используемые понятия

N — размер входного массива
run — упорядоченный подмассив во входном массиве. Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е:
- либо « $a_0 \leqslant a_1 \leqslant a_2 \leqslant .$ »,
- либо «»
Шаг 0. Вычисление minrun.

Число minrun (минимальный размер упорядоченной последовательности) определяется на основе N исходя из следующих принципов: оно не должно быть слишком большим, поскольку к подмассиву размера minrun будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах.

Оно не должно быть слишком маленьким, поскольку чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для N / minrun это степень числа 2 (или близким к нему). Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.

В этом месте автор алгоритма ссылается на собственные эксперименты, показавшие, что при minrun > 256 нарушается пункт 1, при minrun < 8 — пункт 2 и наиболее эффективно использовать значения из диапазона (32;65). Исключение — если N < 64, тогда minrun = N и timsort превращается в простую сортировку вставкой. В данный момент алгоритм расчёта minrun предельно прост: берутся старшие 6 бит из N и добавляется единица, если в оставшихся младших битах есть хотя бы один ненулевой. Псевдокод:

Шаг 1. Разбиение на подмассивы и их сортировка.
- Указатель текущего элемента ставится в начало входного массива.
- Начиная с текущего элемента, идет поиск во входном массиве run (упорядоченный подмассив). По определению, в этот run однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию — элементы переставляются так, чтобы они шли по возрастанию.
- Если размер текущего run’а меньше чем minrun — выбираются следующие за найденным run-ом элементы в количестве minrun — size(run). Таким образом, на выходе будет получен подмассив размером minrun или больше, часть которого (а в идеале — он весь) упорядочена.
- Применяется к данному подмассиву сортировка вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает быстро и эффективно.
- Указатель текущего элемента ставится на следующий за подмассивом элемент.
- Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.
Шаг 2. Слияние.

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

Нужно объединить эти подмассивы для получения результирующего, полностью упорядоченного массива. Для достижения эффективности Объединение должно удовлетворять двум требованиям:
- Объединять подмассивы примерно равного размера
- Сохранить стабильность алгоритма — то есть не делать бессмысленных перестановок.
- Создается пустой стек пар <индекс начала подмассива>-<размер подмассива>. Берется первый упорядоченный подмассив.
- Добавляется в стек пара данных <индекс начала>-<размер> для текущего подмассива.
- Определяется, нужно ли выполнять процедуру слияния текущего подмассива с предыдущими. Для этого проверяется выполнение двух правил (пусть X, Y и Z — размеры трёх верхних в стеке подмассивов):
- Если одно из правил нарушается — массив Y сливается с меньшим из массивов X и Z. Повторяется до выполнения обоих правил или полного упорядочивания данных.
- Если еще остались не рассмотренные подмассивы — берется следующий и переходим к пункту 2. Иначе — конец.
Цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке справа, а значит, размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием. В идеальном случае: есть подмассивы размера 128, 64, 32, 16, 8, 4, 2, 2. В этом случае никаких слияний не будет выполнятся пока не встретятся 2 последних подмассива, а вот после этого будут выполнены 7 идеально сбалансированных слияний.

Процедура слияния подмассивов
- Создается временный массив в размере меньшего из соединяемых подмассивов.
- Копируется меньший из подмассивов во временный массив
- Ставятся указатели текущей позиции на первые элементы большего и временного массива.
- На каждом следующем шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них и копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
- Пункт 4 повторяется, пока один из массивов не закончится.
- Все элементы оставшегося массива добавляются в конец нового массива.
Модификация процедуры слияния подмассивов (Galloping Mode)

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

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

Первые 7 итераций сравниваются числа 1, 2, 3, 4, 5, 6 и 7 из массива A с числом 20000, так как 20000 больше — элементы массива A копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим «галопа»: сравнивает с числом 20000 последовательно элементы 8, 10, 14, 22, 38, n+2^i, …, 10000 массива A. (

log2 N сравнений). После того как конец массива A достигнут и известно, что он весь меньше B, нужные данные из массива A копируются в результирующий.

Timsort

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

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

Содержание

Основная идея алгоритма [ править ]

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

Алгоритм [ править ]

Обозначения [ править ]
- [math]n[/math] — размер входного массива.
- [math]\mathtt
  [/math] — подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
  - строго по убыванию [math]\mathtt \gt a_ \gt \dots> [/math] .
  Шаг 1. Вычисление minrun [ править ]
  
  Начало.
  
  Шаг 0. Число [math]\mathtt[/math] определяется на основе [math]n[/math] , исходя из следующих принципов:
  
  Не должно быть слишком большим, поскольку к подмассиву размера [math]\mathtt[/math] будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).
  
  Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для [math] \mathtt<\dfrac> [/math] — степень двойки. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
  
  Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону [math] [32; 65) [/math] (подробнее о том, почему так, будет сказано ниже).
  
  Исключение: если [math] n \lt 64 [/math] , тогда [math] n = \mathtt [/math] и Timsort превращается в сортировку вставками.
  
  Нетрудно понять, что после таких вычислений, [math]\mathtt<\dfrac<>> [/math] будет равно степени двойки или немного меньше степени двойки.
  
  Конец.
  
  Шаг 2. Алгоритм разбиения на подмассивы и их сортировка [ править ]
  
  Начало.
  
  Шаг 0. Указатель текущего элемента ставится в начало входного массива.
  
  Шаг 1. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива [math]\mathtt[/math] . По определению, в [math]\mathtt[/math] однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления [math]\mathtt[/math] для текущего массива элементы переставляются так, чтобы они шли по возрастанию.
  
  Шаг 2. Если размер текущего [math]\mathtt[/math] меньше [math]\mathtt[/math] , тогда выбираются следующие за найденным подмассивом [math]\mathtt[/math] элементы в количестве [math] \mathtt [/math] . Таким образом, на выходе будет получен подмассив размером большим или равным [math]\mathtt[/math] , часть которого (в лучшем случае — он весь) упорядочена.
  
  Шаг 3. К данному подмассиву применяем сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает эффективно.
  
  Шаг 4. Указатель текущего элемента ставится на следующий за подмассивом элемент.
  
  Шаг 5. Если конец входного массива не достигнут — переход к шагу 1.
  
  Конец.
  
  Шаг 3. Слияние [ править ]
  
  Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно объединять подмассивы примерно равного размера и cохранять стабильность алгоритма.
  
  Начало.
  
  Шаг 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] .
  
  Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.
  
  Описание процедуры слияния [ править ]
  
  Начало.
  
  Шаг 0. Создается временный массив в размере меньшего из сливаемых подмассивов.
  
  Шаг 1. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив — правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
  
  Шаг 2. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
  
  Шаг 3. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
  
  Шаг 4. Предыдущий пункт повторяется, пока один из массивов не закончится.
  
  Шаг 5.Все элементы оставшегося массива добавляются в конец нового массива.
  
  Конец.
  
  Пример [ править ]
  
  Возьмем [math]n = 356[/math] . При таком [math]n[/math] [math]\mathtt[/math] оказался равным [math]45[/math] . Ниже представлена работа алгоритма. Числа с закрывающей скобкой показывают номера шагов, на которых произошло сливание нижестоящих подмассивов.
  
  Модификация процедуры слияния подмассивов (Galloping Mode) [ править ]
  
  Рассмотрим процедуру слияния двух массивов:
  
  Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге [math]10000[/math] сравнений и [math]10000[/math] копирований. Timsort предлагает в этом месте модификацию, которая получила называет галоп. Алгоритм следующий:
  
  Начало.
  
  Шаг 0. Начинается процедура слияния.
  
  Шаг 1. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
  
  Шаг 2. Если уже некоторое количество элементов (например, в JDK 7 это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим галопа, то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
  
  Шаг 3. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.
  
  Конец.
  
  Для вышеописанных массивов [math]\mathtt[/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^, \dots, 10000 [/math] массива [math]A[/math] [math]( \thicksim\log[/math] сравнений [math])[/math] . После того как конец массива [math]\mathtt[/math] достигнут и известно, что он весь меньше [math]B[/math] , нужные данные из массива [math]A[/math] копируются в результирующий.
  
  Доказательство времени работы алгоритма [ править ]
  
  Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод Galloping Mode. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу. Пусть [math]k[/math] — число кусков, на которые разбился наш исходный массив, очевидно [math]k[/math] = [math] \left\lceil \mathtt<\dfrac> \right\rceil [/math] .
  
  Главный факт, который нам понадобится для доказательства нужной оценки времени работы в [math]O(n \log)[/math] — это то, что сливаемые массивы всегда имеют примерно одинаковую длину. Можно сказать больше: пока [math]k \gt 3[/math] сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной [math]\mathtt[/math] последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы [math]\mathtt[/math] .
  
  Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в [math]\approx 2[/math] раза. Таким образом получаем, что каждый подмассив [math]\mathtt[/math] может участвовать в не более [math]O(\log)[/math] операций слияния, а значит и каждый элемент будет задействован в сравниниях не более [math]O(\log)[/math] раз. Элементов [math]n[/math] , откуда получаем оценку в [math]O(n\log)[/math] .
  
  Также нужно сказать про сортировку вставками, которая используется для сортировки подмассивов [math]\mathrm[/math] : в нашем случае, алгоритм работает за [math]O(\mathtt)[/math] , где [math]\mathtt[/math] — число обменов элементов входного массива, равное числу инверсий. C учетом значения [math]k[/math] получим, что сортировка всех блоков может занять [math]O(\mathtt) \cdot k = O(\mathtt) \cdot [/math] [math]\left\lceil \mathtt<\dfrac> \right\rceil [/math] . Что в худшем случае [math](\mathtt<2>> )[/math] может занимать [math]O(\mathtt) [/math] времени. Откуда видно, что константа [math]\mathtt[/math] играет немалое значение: при большом [math]\mathtt[/math] слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после экспериментов на различных значениях и был выбран оптимальный диапазон — от [math]32[/math] до [math]64[/math] .
  
  Похожие публикации:
  
  Как сделать текст в ворде с двух сторон листа
  
  Как уменьшить размер нет графа
  
  Как умножить список на число python
  
  Как установить access если установлен office