Алгоритм сортировки Timsort
Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.
Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.
Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Сразу к сути
- По специальному алгоритму разделяем входной массив на подмассивы.
- Сортируем каждый подмассив обычной сортировкой вставками.
- Собираем отсортированные подмассивы в единый массив с помощью модифицированной сортировки слиянием.
Алгоритм
Используемые понятия
- N — размер входного массива
- run — упорядоченный подмассив во входном массиве. Причём упорядоченный либо нестрого по возрастанию, либо строго по убыванию. Т.е или «a0 a1 > a2 > . »
- minrun — как было сказано выше, на первом шаге алгоритма входной массив будет поделен на подмассивы. minrun — это минимальный размер такого подмассива. Это число рассчитывается по определённой логике из числа N.
Шаг 0. Вычисление minrun.
- Оно не должно быть слишком большим, поскольку к подмассиву размера minrun будет в дальнейшем применена сортировка вставками, а она эффективна только на небольших массивах
- Оно не должно быть слишком маленьким, поскольку чем меньше подмассив — тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма.
- Хорошо бы, чтобы N \ minrun было степенью числа 2 (или близким к нему). Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
int GetMinrun(int n) < int r = 0; /* станет 1 если среди сдвинутых битов будет хотя бы 1 ненулевой */ while (n >= 64) < r |= n & 1; n >>= 1; > return n + r; >
Шаг 1. Разбиение на подмассивы и их сортировка.
- Ставим указатель текущего элемента в начало входного массива.
- Начиная с текущего элемента, ищем во входном массиве run (упорядоченный подмассив). По определению, в этот run однозначно войдет текущий элемент и следующий за ним, а вот дальше — уже как повезет. Если получившийся подмассив упорядочен по убыванию — переставляем элементы так, чтобы они шли по возрастанию (это простой линейный алгоритм, просто идём с обоих концов к середине, меняя элементы местами).
- Если размер текущего run’а меньше чем minrun — берём следующие за найденным run-ом элементы в количестве minrun — size(run). Таким образом, на выходе у нас получается подмассив размером minrun или больше, часть которого (а в идеале — он весь) упорядочена.
- Применяем к данному подмассиву сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает быстро и эффективно.
- Ставим указатель текущего элемента на следующий за подмассивом элемент.
- Если конец входного массива не достигнут — переход к пункту 2, иначе — конец данного шага.
Шаг 2. Слияние.
На данном этапе у нас имеется входной массив, разбитый на подмассивы, каждый из которых упорядочен. Если данные входного массива были близки к случайным — размер упорядоченных подмассивов близок к minrun, если в данных были упорядоченные диапазоны (а исходя из рекомендаций по применению алгоритма, у нас есть основания на это надеяться) — упорядоченные подмассивы имеют размер, превышающий minrun.
Теперь нам нужно объединить эти подмассивы для получения результирующего, полностью упорядоченного массива. Причём по ходу этого объединения нужно выполнить 2 требования:
- Объединять подмассивы примерно равного размера (так получается эффективнее).
- Сохранить стабильность алгоритма — т.е. не делать бессмысленных перестановок (например, не менять два последовательно стоящих одинаковых числа местами).
Достигается это таким образом.
- Создаем пустой стек пар -. Берём первый упорядоченный подмассив.
- Добавляем в стек пару данных — для текущего подмассива.
- Определяем, нужно ли выполнять процедуру слияния текущего подмассива с предыдущими. Для этого проверяется выполнение 2 правил (пусть X, Y и Z — размеры трёх верхних в стеке подмассивов):
X > Y + Z
Y > Z - Если одно из правил нарушается — массив Y сливается с меньшим из массивов X и Z. Повторяется до выполнения обоих правил или полного упорядочивания данных.
- Если еще остались не рассмотренные подмассивы — берём следующий и переходим к пункту 2. Иначе — конец.
Цель этой хитрой процедуры — сохранение баланса. Т.е. изменения будут выглядеть вот так:
а значит, размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием. Представьте себе идеальный случай: у нас есть подмассивы размера 128, 64, 32, 16, 8, 4, 2, 2 (забудем на секунду о наличии требования «размер подмассива >= minrun»). В этом случае никаких слияний не будет выполнятся пока не встретятся 2 последних подмассива, а вот после этого будут выполнены 7 идеально сбалансированных слияний.
Процедура слияния подмассивов
Как Вы помните, на втором шаге алгоритма мы занимаемся слиянием двух подмассивов в один упорядоченный. Мы всегда соединяем 2 последовательных подмассива. Для их слияния используется дополнительная память.
- Создаём временный массив в размере меньшего из соединяемых подмассивов.
- Копируем меньший из подмассивов во временный массив
- Ставим указатели текущей позиции на первые элементы большего и временного массива.
- На каждом следующем шаге рассматриваем значение текущих элементов в большем и временном массивах, берём меньший из них и копируем его в новый отсортированный массив. Перемещаем указатель текущего элемента в массиве, из которого был взят элемент.
- Повторяем 4, пока один из массивов не закончится.
- Добавляем все элементы оставшегося массива в конец нового массива.
Модификация процедуры слияния подмассивов
- Начинаем процедуру слияния, как было показано выше.
- На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминаем, из какого именно подмассива был элемент.
- Если уже некоторое количество элементов (в данной реализации алгоритма это число жестко равно 7) было взято из одного и того же массива — предполагаем, что и дальше нам придётся брать данные из него. Чтобы подтвердить эту идею, мы переходим в режим «галопа», т.е. бежим по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (мы помним, что массив упорядочен и мы имеем полное право на бинарный поиск) текущего элемента из второго соединяемого массива. Бинарный поиск эффективнее линейного, а потому операций поиска будет намного меньше.
- Найдя, наконец, момент, когда данные из текущего массива-поставщика нам больше не подходят (или дойдя до конца массива), мы можем, наконец, скопировать их все разом (что может быть эффективнее копирования одиночных элементов).
- Первые 7 итераций мы сравниваем числа 1, 2, 3, 4, 5, 6 и 7 из массива A с числом 20000 и, убедившись, что 20000 больше — копируем элементы массива A в результирующий.
- Начиная со следующей итерации переходим в режим «галопа»: сравниваем с числом 20000 последовательно элементы 8, 10, 14, 22, 38, n+2^i, . 10000 массива A. Как видно, таких сравнение будет намного меньше 10000.
- Мы дошли до конца массива A и знаем, что он весь меньше B (мы могли также остановиться где-то посередине). Копируем нужные данные из массива A в результирующий, идём дальше.
Материалы по теме
- Timsort на Википедии (русской версии нет)
- Представление алгоритма от его создателя
- Обсуждение алгоритма на Stackoverflow
- Красивая визуализация алгоритма
Timsort — самый быстрый алгоритм сортировки, о котором вы никогда не слышали
Timsort: Очень быстрый, O(n log n), стабильный алгоритм сортировки, созданный для реального мира, а не для академических целей.
Timsort — это алгоритм сортировки, который эффективен для реальных данных, а не создан в академической лаборатории. Tim Peters создал Timsort для Python в 2001 году.
Timsort сначала анализирует список, который он пытается отсортировать, и на его основе выбирает наилучший подход. С момента его появления он используется в качестве алгоритма сортировки по умолчанию в Python, Java, платформе Android и GNU Octave.
Нотация Big O для Timsort — это O(n log n). Чтобы узнать о нотации Big O, прочтите это.
Время сортировки Timsort такое же, как и у Mergesort, что быстрее, чем у большинства других известных сортировок. Timsort фактически использует сортировку вставкой как и Mergesort. Вы это скоро увидите.
Peters разработал Timsort для использования уже упорядоченных элементов, которые существуют в большинстве реальных наборов данных. Он называет эти упорядоченные элементы «natural runs» (естественные пробеги). Они итеративно перебирают данные, собирая элементы в пробеги и одновременно объединяя несколько этих пробегов в один.
Если массив (array), который мы пытаемся отсортировать, содержит менее 64 элементов, Timsort выполняет сортировку вставкой.
Сортировка вставкой — это простая сортировка, которая наиболее эффективна для небольших списков. Она функционирует довольно медленно при работе с большими списками, но при этом быстро работает с маленькими списками. Идея сортировки вставкой заключается в следующем:
- Просматривать элементы по одному
- Построить отсортированный список, вставляя элемент в нужное место
Вот таблица, показывающая, как сортировка вставкой сортирует список [34, 10, 64, 51, 32, 21].
В данном случае мы вставляем только что отсортированные элементы в новый подмассив (sub-array), который начинается от начала массива.
Вот gif, показывающий сортировку вставкой:
Больше о пробегах
Если список больше 64 элементов, то алгоритм сделает первый проход (pass) по списку в поисках частей, которые строго возрастают или убывают. Если какая-либо часть является убывающей, то она будет изменена.
Таким образом, если пробег уменьшается, он будет выглядеть следующим образом (пробег выделен жирным шрифтом):
Если не происходит уменьшение, то это будет выглядеть следующим образом:
Minrun — это размер, который определяется на основе размера массива. Алгоритм выбирает его таким образом, чтобы большинство пробегов в произвольном массиве были или становились длиной minrun. Слияние двух массивов более эффективно, когда число пробегов равно или чуть меньше степени числа 2. Timsort выбирает minrun, чтобы попытаться обеспечить эту эффективность, убедившись, что minrun равен или меньше степени числа 2.
Алгоритм выбирает minrun из диапазона от 32 до 64 включительно, таким образом, чтобы длина исходного массива при расчете была меньше или равна степени числа 2.
Если длина пробега меньше minrun, необходимо рассчитать длину этого пробега относительно minrun. Используя это новое число выполняется сортировка вставкой для создания нового пробега.
Итак, если minrun равен 63, а длина пробега равна 33, вы выполняете вычитание: 63-33 = 30. Затем вы берете 30 элементов из run[33], и делаете сортировку вставкой для создания нового пробега.
После завершения этой части должно появиться множество отсортированных пробегов в списке.
Слияние
Теперь Timsort использует сортировку слиянием, чтобы объединить пробеги. Однако Timsort следит за тем, чтобы сохранить стабильность и баланс слияния во время сортировки.
Для поддержания стабильности мы не должны менять местами два одинаковых числа. Это не только сохраняет их исходные позиции в списке, но и позволяет алгоритму работать быстрее. В ближайшее время мы обсудим баланс слияния.
Когда Timsort находит пробеги, он добавляет их в стек. Простой стек выглядит следующим образом:
Представьте себе стопку тарелок. Вы не можете взять тарелки снизу, поэтому вам приходится брать их сверху. То же самое можно сказать и о стеке.
Timsort пытается сбалансировать две конкурирующие задачи при сортировке слиянием. С одной стороны, мы хотели бы отложить слияние на как можно дольше, чтобы использовать паттерны, которые могут появиться позже, но еще больше нам хотелось бы произвести слияние как можно быстрее, чтобы воспользоваться тем, что только что найденный пробег все еще находится наверху в иерархии памяти. Мы также не можем откладывать слияние «слишком надолго», потому что на запоминание еще не объединенных пробегов расходуется память, а стек имеет фиксированный размер.
Чтобы добиться компромисса, Timsort отслеживает три последних элемента в стеке и создает два правила, которые должны выполняться для этих элементов:
Где A, B и C — три самых последних элемента в стеке.
По словам Tim Peters:
Хорошим компромиссом оказалось то, что сохраняет два варианта для записей в стеке, где A, B и C — длины трех самых правых еще не объединенных частей.
Обычно объединить соседние пробеги разной длины очень сложно. Еще сложнее то, что мы должны поддерживать стабильность. Чтобы обойти эту проблему, Timsort выделяет временную память. Он помещает меньший (называя оба пробега A и B) из двух побегов в эту временную память.
Galloping*
*Модификация процедуры слияния подмассивов
Пока Timsort объединяет A и B, обнаруживается, что один пробег «выигрывает» много раз подряд. Если бы оказалось, что A состоял из гораздо меньших чисел, чем B, то A оказался бы на прежнем месте. Слияние этих двух пробегов потребовало бы много работы c нулевым результатом.
Чаще всего данные имеют некоторую уже существующую внутреннюю структуру. Timsort предполагает, что если многие значения пробега A меньше, чем значения пробега B, то, скорее всего, A будет и дальше содержать меньшие значения, чем B.
Затем Timsort переходит в режим galloping. Вместо того чтобы сверять A[0] и B[0] друг с другом, Timsort выполняет бинарный поиск соответствующей позиции b[0] в a[0]. Таким образом, Timsort может полностью переместить A. Затем Timsort ищет соответствующее местоположение A[0] в B. После этого Timsort также может полностью перемещает B.
Давайте посмотрим на это в действии. Timsort проверяет B[0] (который равен 5) и, используя бинарный поиск, ищет соответствующее место в A.
Итак, B[0] находится в конце списка A. Теперь Timsort проверяет A[0] (который равен 1) в правильном месте B. Итак, мы ищем, где находится число 1. Это число находится в начале B. Теперь мы знаем, что B находится в конце A, а A — в начале B.
Оказывается, что действие не имеет смысла, если подходящее место для B[0] находится очень близко к началу A (или наоборот), поэтому режим gallop быстро завершается, если он не приносит результатов. Кроме того, Timsort принимает это к сведению и усложняет вход в режим gallop, увеличивая количество последовательных «побед» только в A или только в B. Если режим gallop приносит результаты, Timsort облегчает его повторный запуск.
Если говорить коротко, Timsort делает две вещи невероятно хорошо:
- Обеспечивает высокую производительность при работе с массивами с уже существующей внутренней структурой
- Создает возможность поддерживать стабильную сортировку
А раньше, чтобы добиться стабильной сортировки, вам нужно было сжать элементы списка в целые числа и отсортировать его как массив кортежей.
Код
Если вас не интересует код, смело пропускайте эту часть. Под этим разделом есть дополнительная информация.
Если вы хотите увидеть оригинальный исходный код Timsort во всей его красе, посмотрите его здесь. Timsort официально реализован на C, а не на Python.
Timsort фактически встроен прямо в Python, поэтому этот код служит только в качестве пояснения. Чтобы использовать Timsort, просто напишите следующее:
list.sort()sorted(list)Если вы хотите узнать, как работает Timsort, и понять его суть, я настоятельно рекомендую вам попробовать применить его самостоятельно!
Эта статья основана на оригинальном вступлении Tim Peters к Timsort, которое можно найти здесь.
Если вам интересно узнать о курсе больше, приглашаем на день открытых дверей онлайн.
- алгоритмы
- программирование
- timsort
- алгоритм сортировки
Сортировки
Сортировкой (англ. sorting) называется процесс упорядочивания множества объектов по какому-либо признаку.
Так как данные могут хранится в разных структурах, то и алгоритмы для каждой структуры могут отличаться. Например, при хранении данных в списке сортировка кучей потребует $O(n^2 \log n)$ времени против $O(n \log n)$ с использованием массива; а вот сортировка пузырьком не изменится.
Также есть алгоритмы параллельной сортировки данных (т.н. Сортирующие сети), время работы которых в лучшем случае $O(\log n)$.
Классификация сортировок
Время работы
Эту классификацию обычно считают самой важной. Оценивают худшее время алгоритма, среднее и лучшее. Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big[ 1 \ldots n \big] $. Худшее время — наибольшее время. У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.
Память
Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.
Устойчивость
Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.
Количество обменов
Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.
Детерминированность
Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих. Все сортирующие сети являются детерминированными.
Сравнение сортировок
Рассмотрим массив $\big[ 1 \ldots n \big]$. Для элементов должно выполняться отношение порядка.
| Название | Лучшее время | Среднее | Худшее | Память | Устойчивость | Обмены (в среднем) | Описание |
|---|---|---|---|---|---|---|---|
| Сортировка пузырьком (Bubble Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. |
| Сортировка вставками (Insertion Sort) |
$O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Да | $O(n^2)$ | На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива до тех пор, пока весь набор входных данных не будет отсортирован. |
| Сортировка Шелла (Shellsort) |
$O(n\log^2)$ | Зависит от выбора шага | $O(n^2)$ | $O(1)$ | Нет | $O(n^2)$ | Является модификацией сортировки вставками, сортируем между собой элементы, стоящие на кратных нашему шагу местах. |
| Сортировка выбором (Selection Sort) |
$O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Нет | $O(n)$ | На $i$-ом шаге алгоритма находим минимальный среди последних $n — i + 1$, и меняем его местами с $i$-ым элементом в массиве. |
| Быстрая сортировка (Quick Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ (маловероятно) |
$O(\log n)$ (стек вызовов) |
Нет | $O(n \log n)$ | Один из самых известных и широко используемых алгоритмов сортировки. Алгоритм состоит в выборе опорного элемента, разделении массива на 2 части относительно опорного (одна — все элементы, меньшие опорного элемента, вторая — большие), и в сортировке полученных частей рекурсивным вызовом себя от них. |
| Сортировка слиянием (Merge Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ (обычная реализация) $O(1)$ (модифицированная реализация) |
Да | $O(n \log n)$ | Алгоритм состоит в разделении массива пополам, сортировке половин и их слиянии. |
| Timsort | $O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Да | $O(n\log)$ | Гибрид сортировки слиянием. Разбиваем массив на подмассивы фиксированной длины и сортируем каждый подмассив любой устойчивой сортировкой. После чего объединяем отсортированные подмассивы модифицированной сортировкой слиянием. |
| Сортировка кучей (Heap Sort) |
$O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Нет | $O(n \log n)$ | Строим из массива кучу, по очереди извлекаем минимум кучи. |
| Плавная сортировка (Smoothsort) |
$O(n)$ | $O(n\log)$ | $O(n\log)$ | $O(1)$ | Нет | $O(n\log)$ | Модификация сортировки кучей. Вместо двоичной кучи используем K-ую кучу Леонардо. |
| Терпеливая сортировка (Patience sorting) |
$O(n\log)$ | $O(n\log)$ | $O(n\log)$ | $O(n)$ | Нет | $O(n\log)$ | Раскидываем элементы массива по стопкам, после чего строим двоичную кучу из стопок. Позволяет также вычислить длину наибольшей возрастающей подпоследовательности данного массива. |
| Сортировка с помощью бинарного дерева (Tree Sort) |
$O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Да | $O(n)$ | Добавляем по очереди вершины в сбалансированное дерево поиска, проходим по всем вершинам в порядке возрастания. |
| Карманная сортировка (Bucket Sort) |
$O(n + k)$ | $O(n \log_k n)$ | $O(n \cdot k)$ | $O(n)$ | Да | — | Распределяем элементы в $k$ карманов, сортируем элементы внутри карманов, из каждого кармана данные записываются в массив в порядке разбиения. |
| Цифровая сортировка (Radix Sort) |
$O(n \lg n)$ | $O(n \lg n)$ | $O(n \lg n)$ | $O(n)$ | Да | — | Сортировка объектов равной длины, имеющих «разряды». обычно это строки или целые числа. Алгоритм состоит в том, чтобы отсортировать объекты по разрядам, начиная от младших к старшим. |
| Сортировка подсчетом (Counting Sort) |
$O(n)$ | $O(n + k)$ | $O(k)$ | $O(k)$ | Да | $O(n + k)$ | Сортировка целых чисел, входящих в какой-то небольшой диапазон. Создаем массив длины диапазона $k$, каждый элемент которого будет показывать, сколько исходных элементов равны данному. Бежим по массиву и считаем количество вхождений каждого числа. |
| Сортировка Хэна (Han’s Sort) |
$O(n \log \log n)$ | $O(n \log \log n)$ | $O(n \log \log n)$ | $O(n)$ | Да | $O(n \log \log n)$ | Очень сложная сортировка, основанная на принадлежности ключей к целым числам. Использует экспоненциальное поисковое дерево Андерсона. |
| Многопоточная сортировка слиянием (Multithreaded merge sort) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(n)$ | Да | $O(n \log n)$ | Отличается от сортировки слиянием только тем, что при рекурсивном вызове будет создавать новый поток. |
| PSRS-сортировка (PSRS-sorting) |
$O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(\frac>\log \frac>)$ | $O(N_^2)$ | Нет | $O(n \log n)$ | Разделим массив на $N_$ подмассива и запустим в каждой быструю сортировку. После этого объединим все эти подмассивы. |
См. также
- Поисковые структуры данных
- Приоритетные очереди
- Поиск подстроки в строке
Источники информации
- Википедия — Алгоритмы сортировки
- Wikipedia —Sorting algorithm
- Хабрахабр — Бенчмарк алгоритмов сортировки
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 174. — ISBN 978-5-8459-1794-2
Timsort
Timsort — гибридный алгоритм сортировки, сочетающий различные подходы.
Данный алгоритм является относительно новым и был придуман Тимом Петерсом. На массивах данных, которые содержат упорядоченные подмассивы, алгоритм Тима Петерса показывает себя намного лучше других сортировок. В настоящее время Timsort является стандартной сортировкой в Python и GNU Octave, реализован в OpenJDK 7 и Android JDK 1.5.
Основная идея алгоритма
Алгоритм Timsort состоит из нескольких частей:
- Начало.
- Шаг 1. Входной массив разделяется на подмассивы фиксированной длины, вычисляемой определённым образом.
- Шаг 2. Каждый подмассив сортируется сортировкой вставками, сортировкой пузырьком или любой другой устойчивой сортировкой.
- Шаг 3. Отсортированные подмассивы объединяются в один массив с помощью модифицированной сортировки слиянием.
- Конец.
Рассмотрим теперь каждый шаг в отдельности.
Алгоритм
Обозначения
- [math]n[/math] — размер входного массива.
- [math]\mathtt [/math] — подмассив во входном массиве, который обязан быть упорядоченным одним из двух способов:
- строго по убыванию [math]\mathtt \gt a_ \gt \dots> [/math] .
- нестрого по возрастанию [math]\mathtt \leqslant a_ \leqslant \dots> [/math] .
Шаг 1. Вычисление minrun
- Начало.
- Шаг 0. Число [math]\mathtt[/math] определяется на основе [math]n[/math] , исходя из следующих принципов:
- Не должно быть слишком большим, поскольку к подмассиву размера [math]\mathtt[/math] будет в дальнейшем применена сортировка вставками (эффективна только на небольших массивах).
- Оно не должно быть слишком маленьким, так как чем меньше подмассив, тем больше итераций слияния подмассивов придётся выполнить на последнем шаге алгоритма. Оптимальная величина для [math] \mathtt> [/math] — степень двойки. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
- Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону [math] [32; 65) [/math] (подробнее о том, почему так, будет сказано ниже).
- Исключение: если [math] n \lt 64 [/math] , тогда [math] n = \mathtt [/math] и Timsort превращается в сортировку вставками.
Нетрудно понять, что после таких вычислений, [math]\mathtt>> [/math] будет равно степени двойки или немного меньше степени двойки.
int minRunLength(n): flag = 0 // будет равно 1, если среди сдвинутых битов есть хотя бы один ненулевой while (n 64) flag |= n & 1 n >>= 1 return n + flagШаг 2. Алгоритм разбиения на подмассивы и их сортировка
На данном этапе у нас есть входной массив, его размер [math]n[/math] и вычисленное число [math]\mathtt
[/math] . Обратим внимание, что если данные изначального массива достаточно близки к случайным, то размер упорядоченных подмассивов близок к [math]\mathtt [/math] ,. Но если в изначальных данных были упорядоченные диапазоны, то упорядоченные подмассивы могут иметь размер, превышающий [math]\mathtt [/math] . 
- Начало.
- Шаг 0. Указатель текущего элемента ставится в начало входного массива.
- Шаг 1. Начиная с текущего элемента, идет поиск во входном массиве упорядоченного подмассива [math]\mathtt[/math] . По определению, в [math]\mathtt[/math] однозначно войдет текущий элемент и следующий за ним. Если получившийся подмассив упорядочен по убыванию, то после вычисления [math]\mathtt[/math] для текущего массива элементы переставляются так, чтобы они шли по возрастанию.
- Шаг 2. Если размер текущего [math]\mathtt[/math] меньше [math]\mathtt[/math] , тогда выбираются следующие за найденным подмассивом [math]\mathtt[/math] элементы в количестве [math] \mathtt [/math] . Таким образом, на выходе будет получен подмассив размером большим или равным [math]\mathtt[/math] , часть которого (в лучшем случае — он весь) упорядочена.
- Шаг 3. К данному подмассиву применяем сортировку вставками. Так как размер подмассива невелик и часть его уже упорядочена — сортировка работает эффективно.
- Шаг 4. Указатель текущего элемента ставится на следующий за подмассивом элемент.
- Шаг 5. Если конец входного массива не достигнут — переход к шагу 1.
- Конец.
Шаг 3. Слияние
Нужно объединить полученные подмассивы для получения результирующего упорядоченного массива. Для достижения эффективности, нужно объединять подмассивы примерно равного размера и cохранять стабильность алгоритма.
- Начало.
- Шаг 0. Создается пустой стек пар [math] \lt [/math] индекс начала подмассива, размер подмассива [math] \gt [/math] .
- Шаг 1. Берется первый упорядоченный подмассив.
- Шаг 2. Добавляется в стек пара данных [math] \lt [/math] индекс начала текущего подмассива, его размер [math] \gt [/math] .
- Шаг 3. Пусть [math]X,Y,Z [/math] — длины верхних трех интервалов, которые лежат в стеке. Причем [math]X[/math] — это последний элемент стека (если интервалов меньше трёх, проверяем лишь условия с оставшимися интервалами).
- Шаг 4. Повторяем пока выражение ( [math]Z \gt X + Y \wedge Y \gt X[/math] ) не станет истинным
- Если размер стека не меньше [math]2[/math] и [math]Y \leqslant X [/math] — сливаем [math]X[/math] c [math]Y[/math] .
- Если размер стека не меньше [math]3[/math] и [math]Z \leqslant X + Y[/math] — сливаем [math]Y[/math] c [math]\min(X,Z)[/math] .
Основная цель этой процедуры — сохранение баланса. Изменения будут выглядеть как на картинке, а значит и размеры подмассивов в стеке эффективны для дальнейшей сортировки слиянием.
Описание процедуры слияния
- Начало.
- Шаг 0. Создается временный массив в размере меньшего из сливаемых подмассивов.
- Шаг 1. Меньший из подмассивов копируется во временный массив, но надо учесть, что если меньший подмассив — правый, то ответ (результат сливания) формируется справа налево. Дабы избежать данной путаницы, лучше копировать всегда левый подмассив во временный. На скорости это практически не отразится.
- Шаг 2. Ставятся указатели текущей позиции на первые элементы большего и временного массива.
- Шаг 3. На каждом шаге рассматривается значение текущих элементов в большем и временном массивах, берется меньший из них, копируется в новый отсортированный массив. Указатель текущего элемента перемещается в массиве, из которого был взят элемент.
- Шаг 4. Предыдущий пункт повторяется, пока один из массивов не закончится.
- Шаг 5.Все элементы оставшегося массива добавляются в конец нового массива.
- Конец.
Пример
Возьмем [math]n = 356[/math] . При таком [math]n[/math] [math]\mathtt[/math] оказался равным [math]45[/math] . Ниже представлена работа алгоритма. Числа с закрывающей скобкой показывают номера шагов, на которых произошло сливание нижестоящих подмассивов.
Модификация процедуры слияния подмассивов (Galloping Mode)
Рассмотрим процедуру слияния двух массивов:
Вышеуказанная процедура для них сработает, но каждый раз на её четвёртом пункте нужно будет выполнить одно сравнение и одно копирование. В итоге [math]10000[/math] сравнений и [math]10000[/math] копирований. Timsort предлагает в этом месте модификацию, которая получила называет галоп. Алгоритм следующий:
- Начало.
- Шаг 0. Начинается процедура слияния.
- Шаг 1. На каждой операции копирования элемента из временного или большего подмассива в результирующий запоминается, из какого именно подмассива был элемент.
- Шаг 2. Если уже некоторое количество элементов (например, в JDK 7 это число равно 7) было взято из одного и того же массива — предполагается, что и дальше придётся брать данные из него. Чтобы подтвердить эту идею, алгоритм переходит в режим галопа, то есть перемещается по массиву-претенденту на поставку следующей большой порции данных бинарным поиском (массив упорядочен) текущего элемента из второго соединяемого массива.
- Шаг 3. В момент, когда данные из текущего массива-поставщика больше не подходят (или был достигнут конец массива), данные копируются целиком.
- Конец.
Для вышеописанных массивов [math]\mathtt[/math] алгоритм выглядит следующим образом: Первые [math]7[/math] итераций сравниваются числа [math]1, 2, 3, 4, 5, 6, 7[/math] из массива [math]A[/math] с числом [math]20000[/math] , так как [math]20000[/math] больше, то элементы массива [math]A[/math] копируются в результирующий. Начиная со следующей итерации алгоритм переходит в режим галопа: сравнивает с числом [math]20000[/math] последовательно элементы [math]8, 10, 14, 22, 38, 7+2^, \dots, 10000 [/math] массива [math]A[/math] [math]( \thicksim\log[/math] сравнений [math])[/math] . После того как конец массива [math]\mathtt[/math] достигнут и известно, что он весь меньше [math]B[/math] , нужные данные из массива [math]A[/math] копируются в результирующий.
Доказательство времени работы алгоритма
Не сложно заметить, что чем меньше массивов, тем меньше произойдёт операций слияния, но чем их длины больше, тем дольше эти слияния будут происходить. На малом количестве длинных массивов хорошо помогает вышеописанный метод Galloping Mode. Хоть он и не даёт асимптотического выигрыша, но уменьшает константу. Пусть [math]k[/math] — число кусков, на которые разбился наш исходный массив, очевидно [math]k[/math] = [math] \left\lceil \mathtt> \right\rceil [/math] .
Главный факт, который нам понадобится для доказательства нужной оценки времени работы в [math]O(n \log)[/math] — это то, что сливаемые массивы всегда имеют примерно одинаковую длину. Можно сказать больше: пока [math]k \gt 3[/math] сливаемые подмассивы будут именно одинаковой длины (данный факт хорошо виден на примере). Безусловно, после разбиения массива на блоки длиной [math]\mathtt[/math] последний блок может быть отличен от данного значения, но число элементов в нём не превосходит константы [math]\mathtt[/math] .
Мы выяснили, что при слиянии, длинна образовавшегося слитого массива увеличивается в [math]\approx 2[/math] раза. Таким образом получаем, что каждый подмассив [math]\mathtt[/math] может участвовать в не более [math]O(\log)[/math] операций слияния, а значит и каждый элемент будет задействован в сравниниях не более [math]O(\log)[/math] раз. Элементов [math]n[/math] , откуда получаем оценку в [math]O(n\log)[/math] .
Также нужно сказать про сортировку вставками, которая используется для сортировки подмассивов [math]\mathrm[/math] : в нашем случае, алгоритм работает за [math]O(\mathtt)[/math] , где [math]\mathtt[/math] — число обменов элементов входного массива, равное числу инверсий. C учетом значения [math]k[/math] получим, что сортировка всех блоков может занять [math]O(\mathtt) \cdot k = O(\mathtt) \cdot [/math] [math]\left\lceil \mathtt> \right\rceil [/math] . Что в худшем случае [math](\mathtt> )[/math] может занимать [math]O(\mathtt) [/math] времени. Откуда видно, что константа [math]\mathtt[/math] играет немалое значение: при большом [math]\mathtt[/math] слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после экспериментов на различных значениях и был выбран оптимальный диапазон — от [math]32[/math] до [math]64[/math] .
См. также
- Сортировка кучей
- Быстрая сортировка
Источники информации
- 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.
- Magnus Lie Hetland Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с.
- Wikipedia — Timsort
- Habrahabr — Алгоритм сортировки Timsort
- Дискретная математика и алгоритмы
- Сортировка
- Сортировки на сравнениях