39
правок
Изменения
Нет описания правки
'''Timsort''' — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.
Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван). В настоящее время '''Timsort''' является стандартным алгоритмом сортировки в '''Python''', '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''. Чтобы понять почему — достаточно взглянуть на таблицу из Википедии:
== Основная идея алгоритма ==
<tex>\bullet*</tex> По специальному алгоритму входной массив разделяется на подмассивы.
<tex>\bullet*</tex> Каждый подмассив сортируется [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8 сортировкой вставками].
<tex>\bullet*</tex> Отсортированные подмассивы собираются в единый массив с помощью модифицированной [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC сортировки слиянием].
===Используемые понятия и комментарии===
<tex>\bullet*</tex> <tex>n</tex> — размер входного массива.
<tex>\bullet*</tex> <tex>run</tex> — некоторый подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
# строго по убыванию <tex> a_{i} > a_{i + 1} > ... </tex>.
# нестрого по возрастанию <tex> a_{i} \le a_{i + 1} \le ... </tex>.
<tex>\bullet*</tex> <tex>minrun</tex> — минимальный размер подмассива, описанного в предыдущем пункте.
Алгоритм '''Timsort''' состоит из нескольких шагов:
Число <tex>minrun</tex> определяется на основе <tex> n </tex>, исходя из принципов:
<tex> \bullet * </tex> Оно не должно быть слишком большим, поскольку к подмассиву размера <tex> minrun </tex> будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах.
<tex> \bullet * </tex> Оно не должно быть слишком маленьким, так как чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для <tex> n / minrun </tex> — ''степень двойки''. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
<tex>\bullet*</tex> Согласно авторским экспериментам:
# При <tex> minrun > 256 </tex> нарушается пункт <tex>1</tex>.
# При <tex> minrun < 8 </tex> нарушается пункт <tex>2</tex>.
Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>.
<tex>\bullet*</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:
# Объединять подмассивы примерно равного размера
# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:Слияние.png|right]]
===Описание процедуры слияния===
<tex>\bullet*</tex> Создается временный массив в размере меньшего из сливаемых подмассивов.
<tex>\bullet*</tex> Меньший из подмассивов копируется во временный массив
<tex>\bullet*</tex> Ставятся указатели текущей позиции на первые элементы большего и временного массива.
<tex>\bullet*</tex> На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый
отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
<tex>\bullet*</tex> Предыдущий пункт повторяется, пока один из массивов не закончится.
<tex>\bullet*</tex> Все элементы оставшегося массива добавляются в конец нового массива.
== Источники ==
<tex>\bullet*</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.
<tex>\bullet*</tex> Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
<tex>\bullet*</tex> [http://ru.wikipedia.org/wiki/Timsort Wikipedia - Timsort]
<tex>\bullet*</tex> [http://habrahabr.ru/company/infopulse/blog/133303/ Habrahabr - Алгоритм сортировки Timsort]
