Изменения

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

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

* По '''Шаг №1''': по специальному алгоритму входной массив разделяется на подмассивы. * Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]] или [[Сортировка выбором | сортировкой выбором]]. * Отсортированные подмассивы собираются в единый массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].

Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных * '''TimsortШаг №3''' существенно быстрее многих дргугих алгоритмов : отсортированные подмассивы собираются в единый массив с помощью модифицированной [[Сортировка слиянием | сортировкислиянием]].

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

* <tex>run</tex> — {{---}} некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:** строго по убыванию <tex> a_{i} > a_{i + 1} > ... </tex>. ** нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ... </tex>.

# строго по убыванию * <tex> a_{i} > a_{i + 1} > ... minrun</tex>. # нестрого по возрастанию <tex> a_{i{---} \le a_{i + 1} \le ... </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''' превращается в сортировку вставками.

===Шаг №2. Разбиения Алгоритм разбиения на подмассивы и их сортировка===На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>. [[Файл:MinrunExample.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, иначе — конец данного шага* Конец.

Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>. * Итак, нужно Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:# Объединять ''объединять подмассивы примерно равного размера# Сохранить '' и ''cохранять стабильность алгоритма (не делать бессмысленных перестановок)''. [[Файл:Merge2mas.png|400px|right]] Алгоритм шага №3:* Начало.* Создается пустой стек пар <tex> < </tex>индекс начала подмассива<tex> > </tex>{{---}} <tex> < </tex> <размер подмассива<tex> > </tex>.

* Добавляется в стек пара данных <tex> < </tex>индекс начала текущего подмассива<tex> > </tex>{{---}} <tex> < </tex> <его размер<tex> > </tex>.* Затем правило следующее. Пусть <tex>X,Y,Z - </tex> {{---}} длины верхних трех интервалов, которые лежат в стеке. Причем <tex>X</tex> – {{---}} это последний элемент стека. # * Повторяем пока выражение (<tex>Z > X + Y</tex> && <tex>Y > X</tex>) не станет истинным # ** Если количество элементов в стеке размер стека не меньше 3 и <tex>Z \leqslant X + Y</tex> – {{---}} сливаем <tex>Y</tex> c <tex>min(X,Z)</tex>. ** Иначе Если <tex>Y \leqslant X </tex> – {{---}} сливаем <tex>X</tex> c <tex>Y</tex>. # ** Возвращаемся в п.16.* Конец

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

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

Главный факт, который нам понадобится для доказательства нужной оценки времени работы в <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''' сделает следующие слияния: