1632
правки
Изменения
м
** Иначе Если <tex>Y \leqslant X </tex> {{---}} сливаем <tex>X</tex> c <tex>Y</tex>. * '''Шаг 5'''. Если всего осталось <tex> 3 </tex> подмассива, которые сейчас в стеке, то сливаем их в правильном порядке, иначе же переходим Переходим к шагу 2.
rollbackEdits.php mass rollback
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий различные подходы.
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченный подмасивыупорядоченные подмассивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''' и '''GNU Octave''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
== Основная идея алгоритма ==
* '''Шаг 1'''. Берем старшие 6 бит числа <tex>n</tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
Нетрудно понять, что после таких вычислений, <tex>\mathtt{\dfrac{{n}}{minrun}} </tex> будет степенью равно степени двойки или немного меньше степени двойки.
* Конец.
'''int''' minRunLength(n):
* '''Шаг 0'''. Указатель текущего элемента ставится в начало входного массива.
* '''Шаг 1'''. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива <tex>\mathtt{run}</tex>. По определению, в <tex>\mathtt{run}</tex> однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления <tex>\mathtt{run}</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'''. Указатель текущего элемента ставится на следующий за подмассивом элемент.
* '''Шаг 5'''. Если конец входного массива не достигнут {{---}} переход к шагу 1.
* '''Шаг 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>.
* Конец
