3622
правки
Изменения
Нет описания правки
== Timsort ==
'''Timsort''' {{---}} гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слияниемразличные подходы.
Данный алгоритм является относительно новым и был изобретен в 2002 году придуман Тимом Петерсом (в честь него и назван) и основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таким массивах данных , которые содержат упорядоченный подмасивы, алгоритм Тима Петерса существенно быстрее многих показывает себя намного лучше других алгоритмов сортировкисортировок. В настоящее время '''Timsort''' является стандартной сортировкой в '''Python''', реализован в '''OpenJDK 7''' и '''Android JDK 1.5'''.
== Основная идея алгоритма ==
Алгоритм '''Timsort''' состоит из нескольких частей:
* Начало.
* '''Шаг 1'''. По специальному алгоритму входной Входной массив разделяется на подмассивыфиксированной длины, вычисляемой определённым образом.* '''Шаг 2'''. Каждый подмассив сортируется [[Сортировка вставками | сортировкой вставками]], [[Сортировка выбором пузырьком | сортировкой выборомпузырьком]] или любой другой устойчивой сортировкой.* '''Шаг 3'''. Отсортированные подмассивы собираются объединяются в единый один массив с помощью модифицированной [[Сортировка слиянием | сортировки слиянием]].
* Конец.
* <tex>n</tex> {{---}} размер входного массива.
* <tex>run</tex> {{---}} некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
** строго по убыванию <tex> a_{i} > a_{i + 1} > ... </tex>.
** нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ... </tex>.
