39
правок
Изменения
Нет описания правки
== Timsort ==
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition='''Timsort''' — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.
}}
Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван). В настоящее время '''Timsort''' является стандартным алгоритмом сортировки в '''Python''', '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''. Чтобы понять почему — достаточно взглянуть на таблицу из Википедии:
[[Файл:Таблица26007.png]]
== Основная идея алгоритма ==
<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 сортировки слиянием].
Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных '''Timsort''' существенно быстрее многих дргугих алгоритмов сортировки.
== Алгоритм ==
===Используемые понятия и комментарии===
<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''' состоит из нескольких шагов:
===Шаг №1. Вычисление minrun===
Число <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> (32; 65) </tex>.
# Исключение — если <tex> n < 64 </tex>, тогда <tex> n = minrun </tex> и '''Timsort''' превращается в сортировку вставками.
Таким образом, алгоритм расчета <tex> minrun </tex> не так уж сложен: берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
int GetMinrun(int n) {
int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */
while (n >= 64) {
flag |= n & 1;
n >>= 1;
}
return n + flag;
}
===Шаг №2. Разбиения на подмассивы и их сортировка===
На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: [[Файл:Массив.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, иначе — конец данного шага.
===Шаг №3. Слияние===
Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>.
<tex>\bullet</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:
# Объединять подмассивы примерно равного размера
# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:Слияние.png|right]]
Алгоритм шага №3:
# Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>.
# Берется первый упорядоченный подмассив.
# Добавляется в стек пара данных <индекс начала текущего подмассива> <tex>-</tex> <его размер>.
# При выполнении двух последующих правил выполняется процедура слияния текущего подмассива с предыдущими.
Если <tex>X, Y, Z</tex> — размеры трёх верхних подмассивов в стеке, то:
# <tex>X > Y + Z</tex>
# <tex>Y > Z</tex>
Если одно из правил нарушается — массив <tex>Y</tex> сливается с меньшим из массивов <tex>X</tex>, <tex>Z</tex>. Процедура повторяется до выполнения обоих правил или полного упорядочивания данных.
Если остались не рассмотренные подмассивы, то берется следующий и переходим ко второму пункту. Иначе — конец.
Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.
===Описание процедуры слияния===
<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]
{{Определение
|id=идентификатор (необязательно), пример: def1.
|definition='''Timsort''' — гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием.
}}
Данный алгоритм был изобретен в 2002 году Тимом Петерсом(в честь него и назван). В настоящее время '''Timsort''' является стандартным алгоритмом сортировки в '''Python''', '''OpenJDK 7''' и реализован в '''Android JDK 1.5'''. Чтобы понять почему — достаточно взглянуть на таблицу из Википедии:
[[Файл:Таблица26007.png]]
== Основная идея алгоритма ==
<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 сортировки слиянием].
Данный алгоритм основывается на том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных '''Timsort''' существенно быстрее многих дргугих алгоритмов сортировки.
== Алгоритм ==
===Используемые понятия и комментарии===
<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''' состоит из нескольких шагов:
===Шаг №1. Вычисление minrun===
Число <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> (32; 65) </tex>.
# Исключение — если <tex> n < 64 </tex>, тогда <tex> n = minrun </tex> и '''Timsort''' превращается в сортировку вставками.
Таким образом, алгоритм расчета <tex> minrun </tex> не так уж сложен: берем старшие 6 бит числа <tex> n </tex> и добавляем единицу, если в оставшихся младших битах есть хотя бы один ненулевой.
int GetMinrun(int n) {
int flag = 0; /* станет 1 если среди сдвинутых битов есть хотя бы 1 ненулевой */
while (n >= 64) {
flag |= n & 1;
n >>= 1;
}
return n + flag;
}
===Шаг №2. Разбиения на подмассивы и их сортировка===
На данном этапе у нас есть входной массив, его размер <tex>n</tex> и вычисленное число <tex>minrun</tex>. Алгоритм работы этого шага: [[Файл:Массив.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, иначе — конец данного шага.
===Шаг №3. Слияние===
Если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к <tex>minrun</tex>. Если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий <tex>minrun</tex>.
<tex>\bullet</tex> Итак, нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, объединение должно удовлетворять требованиям:
# Объединять подмассивы примерно равного размера
# Сохранить стабильность алгоритма (не делать бессмысленных перестановок). [[Файл:Слияние.png|right]]
Алгоритм шага №3:
# Создается пустой стек пар <индекс начала подмассива> <tex>-</tex> <размер подмассива>.
# Берется первый упорядоченный подмассив.
# Добавляется в стек пара данных <индекс начала текущего подмассива> <tex>-</tex> <его размер>.
# При выполнении двух последующих правил выполняется процедура слияния текущего подмассива с предыдущими.
Если <tex>X, Y, Z</tex> — размеры трёх верхних подмассивов в стеке, то:
# <tex>X > Y + Z</tex>
# <tex>Y > Z</tex>
Если одно из правил нарушается — массив <tex>Y</tex> сливается с меньшим из массивов <tex>X</tex>, <tex>Z</tex>. Процедура повторяется до выполнения обоих правил или полного упорядочивания данных.
Если остались не рассмотренные подмассивы, то берется следующий и переходим ко второму пункту. Иначе — конец.
Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.
===Описание процедуры слияния===
<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]
