Какая временная сложность у алгоритма сортировки timsort

Русские Блоги

Timsort-адаптивный, стабильный и эффективный алгоритм сортировки

При использовании алгоритма сортировки, поставляемого с Python, или алгоритма сортировки на Java, мне интересно, какой высокопроизводительный алгоритм сортировки они используют. После изучения, изучения и ознакомления с информацией они пришли к следующему пониманию.

Введение в Timsort

Timsort — это гибридный, стабильный и эффективный алгоритм сортировки, полученный на основе сортировки слиянием и сортировки вставкой, разработанный для хорошей обработки множества реальных данных. Он был реализован Тимом Петерсом в 2002 году и использовался в языке программирования Python.Алгоритм находит подпоследовательности отсортированных данных и использует эти знания для более эффективной сортировки остальных. Это делается путем слияния идентифицированных подпоследовательностей (называемых запусками) с существующими запусками до тех пор, пока не будут выполнены определенные условия.Начиная с версии 2.3, Timsort является стандартным алгоритмом сортировки Python. Сегодня Timsort является алгоритмом сортировки по умолчанию для платформ Python, Java, Android и GNU Octave.

думал

Согласно анализу данных, который необходимо сортировать на самом деле, большая часть данных обычно является частью отсортированных блоков данных. Timsort использует эту функцию.Timsort называет эти отсортированные блоки данных «запуском», и мы можем рассматривать их как «разделы» один за другим. При сортировке Timsort выполняет итерацию элементов данных и помещает их в разные прогоны. В то же время для этих прогонов они объединяются по правилам только в один прогон, и единственный оставшийся прогон является результатом сортировки.
Другими словами, он предназначен для анализа сортируемых данных в соответствии с их собственными характеристиками,Разделите отсортированные (в порядке или в обратном порядке) подпоследовательности на разделы выполнения. Конечно, этот запуск раздела также имеет определенные ограничения, то есть minrun будет сгенерирован в соответствии с последовательностью. Если исходный запуск меньше, чем длина minrun, используйте Сортировка вставкой расширяет прогон до тех пор, пока не будет выполнено условие, а затем использует сортировку слиянием для объединения нескольких прогонов.

Шаги алгоритма

• Генерация minrun в соответствии с размером последовательности ( Зачем мне минран? Я расскажу об этом при слиянии)
  • Minrun — это значение условия для разделения прогона. Если размер прогона меньше этого minrun, он должен быть расширен, и следующие элементы заполняются в прогоне до тех пор, пока он не будет соответствовать требованиям и не станет равен minrun. Итак, объясните метод выбора minrun: если длина сортируемой последовательности равна n, мы сгенерируем всего ⌈nminrun⌉ \ lceil \ frac \ rceil⌈minrunn⌉Первоначальный запуск.
    • ⌈nminrun⌉\lceil\frac\rceil⌈minrunn— это в точности целая степень двойки, процесс слияния будет очень "идеальным", что может быть выражено в виде полного двоичного дерева.
    • ⌈nminrun⌉\lceil\frac\rceil⌈minrunn⌉ Немного больше, чем некоторая степень целого числа 2, на заключительном этапе алгоритма будет комбинация сверхдлительного и ультракороткого прогонов, что является очень плохой ситуацией.
      Следовательно, мы выберем minrun, чтобы ⌈nminrun⌉ \ lceil \ frac \ rceilceminrunn⌉ — это просто целая степень 2 или число, немного меньшее определенной целой степени 2.
    • 189: 10111101, возьмите первые шесть старших битов флага как 101111 (47), а последние два бита как 01, так что minrun будет 47 + 1 = 48, ⌈nminrun⌉ \ lceil \ frac \ rceil⌈minrunn⌉ = 4 Соответствуют условиям.
    • 976: 11 1101 0000, первые шесть старших битов флага — 111101 (61), а последние несколько бит — 0000, поэтому minrun — 61, ⌈nminrun⌉ \ lceil \ frac \ rceil⌈minrunn⌉ = 16 удовлетворяют условиям.
    • X>Y+ZX > Y + ZX>Y+Z
    • Y>ZY > ZY>Z
      При достижении конца данных Timsort многократно объединяет два прогона в верхнюю часть стека до тех пор, пока не останется только один полных данных, и два вышеуказанных правила не будут соблюдены одновременно.
      
      На практике Timsort объединяет два соседних прогона для временного хранения свободного пространства. Размер временного хранилища равен размеру меньшего из двух прогонов. Алгоритм Timsort сначала копирует меньший прогон в это временное хранилище, а затем использует пространство, изначально сохраненное для двух прогонов, для хранения объединенного прогона.
      
      Алгоритм слияния заключается в использовании простой сортировки вставкой, последовательного сравнения слева направо или справа налево, а затем слияния двух прогонов. Для повышения эффективности Timsort использует двоичную сортировку слиянием (двоичную сортировку слиянием). То есть сначала используйте двоичный поиск, чтобы найти вставленную позицию, а затем вставьте ее. ( Сравнение в python очень дорогое, сравнение дороже, чем на мобильных устройствах, поэтому, если вы можете уменьшить сравнение, вы можете уменьшить сравнение ）

    Galloping mode

    В режиме Galloping алгоритм ищет первый элемент другого прогона за один прогон. Комбинируя начальный элемент со вторыми 2k − 12k-12 другого прогонаk−1 элементы (то есть 1, 3, 5 . ) сравниваются с завершенными, чтобы получить диапазон элементов, в котором расположен начальный элемент. Это сокращает диапазон двоичного поиска, тем самым повышая эффективность. Если обнаруживается, что эффективность галопирования ниже, чем бинарного поиска, выйдите из режима галопирования.
    Например, мы хотим объединить два прогона X и Y, а X — меньший прогон, а X и Y уже отсортированы отдельно, скопируйте X в кэш-память Как показано на рисунке ниже.
    
    Двоичный поиск найдет первый элемент x в X, который больше Y [0]. Когда x найден, элементы до x могут быть проигнорированы при слиянии. Точно так же вы также можете найти первый элемент y, больший, чем X [-1] (самый большой элемент X) в Y. Когда y найден, элементы после y могут быть проигнорированы при слиянии. Этот поиск может быть случайным Эффективность в цифрах не очень высока, но очень эффективна в других ситуациях.
    
    Когда алгоритм достигает минимального порога min_gallop, алгоритм переключается в режим Galloping, пытаясь использовать те элементы в данных, которые можно напрямую отсортировать. Галоп полезен только тогда, когда начальный элемент одного забега не является одним из первых семи элементов другого забега. Это означает, что начальный порог равен 7.
    Чтобы избежать недостатков режима Galloping, функция слияния регулирует порог. Если выбранный элемент принадлежит к тому же массиву ранее возвращенных элементов, min_gallop уменьшается на 1. В противном случае значение увеличивается на 1, что предотвращает возврат в режим галопирования. В случае случайных данных значение min_gallop станет настолько большим, что режим Gallop никогда больше не повторится.

    Временная сложность алгоритма

    
    По сути, Timsort — это сортировка слиянием, которая претерпела большую оптимизацию, и сортировка слиянием достигла худшего случая, сравнивая нижнюю границу временной сложности алгоритма сортировки, поэтому в худшем случае Временная сложность Timsort — O (nlogn) O (nlogn)O(nlogn). В лучшем случае, то есть вход сортируется, он выполняется O (n) O (n) за линейное времяO(n). Видно, что Timsort в настоящее время является лучшим методом сортировки.

    Код

    Реализованный ниже код не является конкретным и полным timsort, а является упрощенным, в соответствии с приблизительной реализацией идей Timsort. Для получения конкретного и полного кода обратитесь к разделу сортировки в исходном коде Python или в исходном коде в JDK1.8, или обратитесь кОфициальный исходный код Timsort на C：

    Timsort — Timsort

    Timsort — это гибридный стабильный алгоритм сортировки, полученный из сортировка слиянием и сортировка вставкой, предназначенная для хорошей работы со многими типами реальных данных. Он был реализован Тимом Петерсом в 2002 году для использования в языке программирования Python. Алгоритм находит подпоследовательности данных, которые уже упорядочены (запускаются), и использует их для более эффективной сортировки остатка. Это делается путем объединения прогонов до тех пор, пока не будут выполнены определенные критерии. Timsort является стандартным алгоритмом сортировки Python начиная с версии 2.3. Он также используется для сортировки массивов непримитивного типа в Java SE 7, на платформе Android, в GNU Octave, на V8,Swift и Rust.

    Он использует методы из статьи 1993 года «Оптимистическая сортировка и теоретическая сложность информации».

    Содержание

    • 1 Операция
      • 1.1 Критерии слияния
      • 1.2 Накладные расходы на пространство слияния
      • 1.3 Направление слияния
      • 1.4 Галопирующий режим во время слияния
      • 1.5 Нисходящие прогоны
      • 1.6 Минимальный размер цикла

      Операция

      Timsort был разработан, чтобы использовать преимущества прогонов последовательных упорядоченных элементов, которые уже существуют в большинстве реальных данных, естественных прогонов. Он выполняет итерацию по элементам сбора данных в прогоны и одновременно помещает эти прогоны в стек. Всякий раз, когда прогоны на вершине стека соответствуют критерию слияния , они объединяются вместе. Это продолжается до тех пор, пока не будут пройдены все данные; затем все прогоны объединяются по два за раз, и остается только один отсортированный прогон. Преимущество объединения упорядоченных прогонов вместо слияния подсписок фиксированного размера (как это делается при традиционной сортировке слиянием) состоит в том, что оно уменьшает общее количество сравнений, необходимых для сортировки всего списка.

      Каждый прогон имеет минимальный размер, который зависит от размера входных данных и определяется в начале алгоритма. Если серия меньше этого минимального размера серии, используется сортировка вставкой для добавления дополнительных элементов в серию, пока не будет достигнут минимальный размер серии.

      Критерии слияния

      прогоны вставляются в стек . Если | Z | ≤ | Y | + | X |, затем X и Y объединяются и заменяются в стеке. Таким образом, слияние продолжается до тех пор, пока все прогоны не удовлетворяют i. | Z |>| Y | + | X | и ii. | Y |>| X |.

      Timsort — это стабильный алгоритм сортировки (сохраняется порядок элементов с одинаковым ключом), который стремится выполнить сбалансированное слияние (слияние, таким образом, объединяет прогоны одинакового размера).

      Для достижения стабильности сортировки объединяются только последовательные прогоны. Между двумя непоследовательными запусками может быть элемент с одним и тем же ключом элементов внутри прогонов, и объединение этих двух прогонов изменит порядок равных ключей. Пример этой ситуации (упорядоченные прогоны): [1 2 2] 1 4 2 [0 1 2]

      В поисках сбалансированных слияний Timsort рассматривает три прогона на вершине стека, X, Y, Z, и поддерживает инварианты:

      1. | Z |>| Y | + | X |
      2. | Y |>| X |

      Если любой из этих инвариантов нарушается, Y объединяется с меньшим из X или Z и инварианты проверяются снова. Как только инварианты сохранятся, можно начинать поиск нового прогона в данных. Эти инварианты поддерживают слияния примерно сбалансированными, сохраняя при этом компромисс между отложением слияния для баланса, использованием новых запусков в кэш-памяти и относительно простыми решениями о слиянии.

      Накладные расходы на пространство слияния

      Для слияния Timsort копирует элементы меньшего массива (X на этом рисунке) во временную память, затем сортирует и заполняет элементы в окончательном порядке в объединенное пространство X и Y.

      Исходная реализация сортировки слиянием не на месте, и у нее накладные расходы на пространство N (размер данных). Существуют реализации сортировки слиянием на месте, но они требуют больших затрат времени. Чтобы получить средний термин, Timsort выполняет сортировку слиянием с небольшими затратами времени и меньшими затратами пространства, чем N.

      Сначала Timsort выполняет двоичный поиск, чтобы найти место, где находится первый элемент второго прогона будет вставлен в первый упорядоченный прогон, сохраняя его в порядке. Затем он выполняет тот же алгоритм, чтобы найти место, где последний элемент первого прогона будет вставлен во второй упорядоченный прогон, сохраняя его упорядоченным. Элементы до и после этих местоположений уже находятся на своих местах, и их не нужно объединять. Затем меньший из оставшихся элементов двух прогонов копируется во временную память, а элементы объединяются с большей серией в теперь свободное пространство. Если первый прогон меньше, слияние начинается с самого начала; если второй меньше, слияние начинается в конце. Эта оптимизация снижает количество необходимых перемещений элементов, время работы и временные накладные расходы на пространство в общем случае.

      Пример: необходимо объединить два прогона [1, 2, 3, 6, 10] и [4, 5, 7, 9, 12, 14, 17]. Обратите внимание, что оба прогона уже отсортированы по отдельности. Наименьший элемент второго прогона — 4, и его нужно будет добавить в 4-ю позицию первого прогона, чтобы сохранить его порядок (при условии, что первая позиция прогона равна 1). Самый большой элемент первого прогона — 10, и его нужно добавить в 5-ю позицию второго прогона, чтобы сохранить его порядок. Следовательно, [1, 2, 3] и [12, 14, 17] уже находятся в своих конечных положениях, и прогоны, в которых требуются перемещения элементов, — это [6, 10] и [4, 5, 7, 9]. Обладая этими знаниями, нам нужно выделить временный буфер размером 2 вместо 5.

      Направление слияния

      Слияние может выполняться в обоих направлениях: слева направо, как в традиционная сортировка слиянием или справа налево.

      Галопирующий режим во время слияния

      Элементы (обозначенные синей стрелкой) сравниваются, и меньший элемент перемещается в свою конечную позицию (обозначенную красной стрелкой).

      Отдельное слияние прогонов R1 а R2 ведет подсчет последовательных элементов, выбранных из серии. Когда это число достигает минимального порога скачка (min_gallop), Timsort считает, что вероятно, что многие последовательные элементы все еще могут быть выбраны из этого прогона, и переключается в режим галопирования. Предположим, что R1 отвечает за его запуск. В этом режиме алгоритм выполняет экспоненциальный поиск, также известный как поиск в галопе, для следующего элемента x цикла R2 в цикле R1. Это делается в два этапа: первый этап находит диапазон (2-1, 2-1), где x. На втором этапе выполняется двоичный поиск элемента x в диапазоне, найденном на первом этапе. Галопирующий режим — это попытка адаптировать алгоритм слияния к шаблону интервалов между элементами в прогонах.

      Все красные элементы меньше синих (здесь 21). Таким образом, они могут быть перемещены куском в окончательный массив.

      Галопирование не всегда эффективно. В некоторых случаях режим «галоп» требует большего количества сравнений, чем простой линейный поиск. Согласно тестам, проведенным разработчиком, галопирование выгодно только тогда, когда начальный элемент одного запуска не является одним из первых семи элементов другого запуска. Это подразумевает начальный порог 7. Чтобы избежать недостатков режима галопирования, предпринимаются два действия: (1) Когда обнаруживается, что галопирование менее эффективно, чем бинарный поиск, из режима галопирования выходят. (2) Успех или неудача скачки используются для настройки min_gallop. Если выбранный элемент принадлежит к тому же массиву, который ранее возвращал элемент, min_gallop уменьшается на единицу, что способствует возврату в режим галопирования. В противном случае значение увеличивается на единицу, препятствуя возвращению в режим галопирования. В случае случайных данных значение min_gallop становится настолько большим, что режим галопирования никогда не повторяется.

      Запуск по убыванию

      Чтобы также воспользоваться преимуществами данных, отсортированных в порядке убывания, Timsort строго инвертирует нисходящие прогоны, когда он их находит, и добавляет их в стек прогонов. Поскольку нисходящие прогоны позже слепо меняются местами, исключение прогонов с равными элементами поддерживает стабильность алгоритма; т.е. равные элементы не будут перевернуты.

      Минимальный размер прогона

      Алгоритм Timsort ищет упорядоченные последовательности минимального размера, minruns, для выполнения сортировки.

      Поскольку слияние наиболее эффективно, когда количество прогонов равно или немного меньше, степень двойки и заметно менее эффективна, когда количество прогонов немного больше степени двух, Timsort выбирает minrun, чтобы попытаться обеспечить первое условие.

      Minrun выбирается из диапазона от 32 до 64 включительно, так что размер данных, деленный на minrun, равен или немного меньше степени двойки. Последний алгоритм берет шесть наиболее значимых битов размера массива, добавляет один, если установлен какой-либо из оставшихся битов, и использует этот результат в качестве minrun. Этот алгоритм работает для всех массивов, включая массивы меньше 64; для массивов размером 63 или меньше это устанавливает minrun равным размеру массива, а Timsort сокращается до сортировки вставкой.

      Анализ

      В худшем случае Timsort принимает O (n log ⁡ n) <\ displaystyle O (n \ log n)>сравнений для сортировки массива из n элементов. В лучшем случае, когда вход уже отсортирован, он выполняется за линейное время, что означает, что это алгоритм адаптивной сортировки.

      Он имеет преимущество перед Quicksort для сортировки ссылок на объекты или указатели, поскольку они требуют дорогостоящего косвенного обращения к памяти для доступа к данным и выполнения сравнений, а преимущества согласованности кэша Quicksort значительно уменьшаются.

      Формальная проверка

      В 2015 году голландские и немецкие исследователи в проекте EU FP7 ENVISAGE обнаружили ошибку в стандартной реализации Timsort.

      В частности, инварианты при групповом запуске размеры обеспечивают жесткую верхнюю границу максимального размера требуемой стопки. Реализация предварительно выделяла стек, достаточный для сортировки 2 байтов ввода, и избегала дальнейших проверок переполнения.

      Однако гарантия требует, чтобы инварианты применялись к каждой группе из трех последовательных запусков, но реализация проверила это только для трех лучших. Используя инструмент KeY для формальной проверки программного обеспечения Java, исследователи обнаружили, что этой проверки недостаточно, и они смогли найти длины прогонов (и входные данные, которые генерировали эти длины прогонов) что приведет к тому, что инварианты будут нарушены глубже в стеке после слияния вершины стека.

      Как следствие, для определенных входных данных выделенного размера недостаточно для хранения всех несвязанных прогонов. В Java это создает для этих входных данных исключение выхода за пределы массива. Наименьший вход, который вызывает это исключение в Java и Android v7, имеет размер 67108864 (2). (Более старые версии Android уже вызывали это исключение для определенных входных данных размером 65536 (2))

      Реализация Java была исправлена ​​путем увеличения размера предварительно выделенного стека на основе обновленного анализа наихудшего случая. В статье также показано формальными методами, как установить предполагаемый инвариант, проверив, что четыре самых верхних прогона в стеке удовлетворяют двум правилам, указанным выше. Этот подход был принят в Python и Android.

      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<\dfrac> [/math] — степень двойки. Это требование обусловлено тем, что алгоритм слияния подмассивов наиболее эффективно работает на подмассивах примерно равного размера.
          • Автором алгоритма было выбрано оптимальное значение, которое принадлежит диапазону [math] [32; 65) [/math] (подробнее о том, почему так, будет сказано ниже).
          • Исключение: если [math] n \lt 64 [/math] , тогда [math] n = \mathtt [/math] и Timsort превращается в сортировку вставками.

          Нетрудно понять, что после таких вычислений, [math]\mathtt<\dfrac<>> [/math] будет равно степени двойки или немного меньше степени двойки.

          • Конец.

          Шаг 2. Алгоритм разбиения на подмассивы и их сортировка

          

          • Начало.
          • Шаг 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<\dfrac> \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<\dfrac> \right\rceil [/math] . Что в худшем случае [math](\mathtt<2>> )[/math] может занимать [math]O(\mathtt) [/math] времени. Откуда видно, что константа [math]\mathtt[/math] играет немалое значение: при большом [math]\mathtt[/math] слияний будет меньше, а сортировки вставками будут выполняться долго. Причём эти функции растут с разной скоростью, поэтому и ещё после экспериментов на различных значениях и был выбран оптимальный диапазон — от [math]32[/math] до [math]64[/math] .

            What is Timsort?

            Understanding probably one of the most commonly used sorting algorithms.

            We all have used the array.sort() and sorted() functions in python, haven’t we? C’mon, we all have used it to save time! But have we ever tried to understand what algorithm is being executed in the background? In my quest to find out and understand the underlying algorithm, I came across an article on Wikipedia about Timsort.

            Timsort, named after its inventor Tim Peters, has been the default sorting algorithm Python since version 2.3! Despite all this, Timsort is still a very obscure sort. Still, many students and engineers are unaware of this sort and how it works! So let’s try and understand how this algorithm works.

            Timsort and its History

            Tim came up with this sorting algorithm in the year 2002 after realising that real-world data almost always contain blocks that are already sorted, either in the ascending order or the descending order. This was something that other sorting algorithms didn’t take into consideration. So his approach of sorting was to identify such blocks in the given dataset called runs and sort them further using Mergesort and Binary Insertion Sort.

            But why Timsort?

            After looking at the above table one might argue that Quicksort and Merge Sort both have the same average time complexity as Timsort, then what’s the need for Timsort? To begin with, if we take a look at the best time complexity, Timsort outperforms both, Quicksort and Mergesort. Not only that, at its worst, although it runs at a speed similar to that of Mergesort, it outperforms Quicksort!

            Note: Quicksort is efficient for very large datasets but not for small datasets.

            Okay, enough about time complexity. If we talk in terms of space complexity, Timsort has a complexity of O(n), which when compared to other algorithms like Quicksort that have a complexity O(1), suggests that maybe it lies on the more inadequate side of the spectrum.

            Another criterion on which sorting algorithms are generally assessed is stability. What is stability? A sorting algorithm is said to be stable in nature when elements of the same value maintain their original order even after sorting. It is often required while sorting real-world data like sorting entries of names in a school-record etc.

            When compared on paper, Heapsort also seems to be better than Timsort. It is an in-place sorting algorithm, has similar average and worst-case time complexities compared to Timsort, then why is Timsort still preferred as the default sorting algorithm? It is because Heapsort has a poor locality of reference. The operating system cannot predict the pointer’s next position as the pointer can either multiply or divide by 2.

            Understanding Timsort

            Timsort is a hybrid and adaptive algorithm. It uses both Binary Insertion Sort and Merge Sort to sort a list in an average time of O(n logn) but in the best case, it can sort the given dataset in O(n) time. It identifies already sorted chunks of the list first and uses these chunks to sort the remainder more efficiently.

            Implementing Timsort

            Implementing Timsort is a little difficult, and understanding it also is a little complex. To make it easier for me and you, let’s break down Timsort into 3 steps

            1. Checking List Size

            While checking the size of the list if we find that the size of the list is less than 64 elements, Timsort will directly apply Binary Insertion Sort. But what’s the use of learning about a new sort if we're going to just apply an Insertion sort you might ask! Yes yes, we are discussing Timsort but, it has been found that Binary Insertion Sort or Insertion Sort, in general, is highly efficient and fast on a list whose size is in the range of 23–64 elements but quite slow on lights or larger size.

            Binary Insertion Sort

            Let’s take a look at a variation of Insertion Sort, called Binary Insertion Sort.

            In Binary Insertion Sort, we use the normal binary search to find the correct index in the sorted section of the list to insert the selected unsorted element at each iteration, unlike the standard Insertion Sort that uses linear search to do the same. Further, the normal Insertion Sorting takes O(n) comparisons in the worst case, but this is reduced to O(n logn) when Binary Insertion Sort is used.

            But what do we do if the size of the list is more than 64 elements? Simple, we move onto Step 2.

            2. Finding Runs in the List

            What are runs? In simple terms, they are blocks of the given list. A natural run is a block of the list in which all the elements are either strictly increasing or decreasing. We look for such runs in the list because we don’t have to sort them. The increasing runs can be simply merged with the next run but the decreasing runs are first blindly reversed, then merged with the next run.

            I hate to break it to you, but everything isn’t so straightforward. During the first pass of the list, the algorithm while looking for runs also calculates the minimum run size and this is given the term minrun. The algorithm chooses the value of minrun from the range of 32–64 inclusive because Binary Insertion Sort is faster in lists of smaller size.

            Furthermore, the value of minrun is generally equal to or nearly less than a power of 2, because merging lists of such size is more efficient. We’ll look more into it while learning about the implementation of Timsort.

            3.a Merging the Sorted Runs

            After finding runs in the list that are of size greater than or equal to minrun, Timsort moves on to perform Merge Sort on these sorted runs. However, Timsort has to maintain stability while merging the runs.

            To ensure that the algorithm is stable, Timsort as when it finds a run in the list, it adds that run into a stack.

            During merging, the Timsort has to balance two competing needs. First, we would have to delay the merging process as much as possible so that we can exploit patterns that might come up later in the list. But at the same time, merging the runs as soon as possible to exploit the run just found, which is still high in the memory hierarchy.

            To balance these two things out, unlike a normal stack where only the top entries are considered, Timsort considers the top three entries (runs) in the stack. And in doing so, creates two rules that must hold of those items:

            1. A > B + C
            2. B > C

            Now the Merge Sort that is followed to merge two runs in Timsort is again, yes, you guessed it right, a variation of the general Merge Sort called In-place Merge Sort. It is also because merging two adjacent runs of different lengths and maintaining their stability is hard. In In-place Merge Sort, instead of making a new list of size n+m (assuming that n and m are the sizes of the two runs), a temporary copy of the smaller list (say n < m) is made and the larger run is shifted by n places.

            3.b Galloping

            Timsort has another optimisation in the form of Galloping. If the algorithm finds that if one of the two runs is “winning” continuously for some time then instead of pushing elements one by one, it pushes elements as a chunk.

            Consider the above two lists. We notice that elements from A[0:4] are all smaller than B[1], so checking for each element will be very inefficient. So when Timsort enters into galloping mode, if binary searches for the position where B[1] can fit in list A. This way the algorithm can move the entire chunk of A[0:4] into place. Then the algorithm binary searches for the correct position of A[0] in B.

            But it has been noticed that galloping is not worth it if the correct position for B[0] is very close to the beginning of A (or vice versa), so if that is the case then the algorithm exits gallop mode quickly. Also, the algorithm only enters galloping mode after a certain number of consecutive A-only or B-only wins.

            Conclusion

            Timsort is a very fast and stable sort, but more importantly, it is optimised or rather should I say it is designed with keeping the real-world data sets in mind. Are there faster and better sorting algorithms? Probably yes. Can Timsort be used in every situation? Maybe not. But in the end, it is an optimised approach to solving a few dataset problems.

            Even after all this research I still believe there is so much more to this sorting algorithm that I haven’t figured out yet!

            Похожие публикации:

            1. Значок передача данных на андроиде на экране наверху что
            2. Как зайти в расширенный биос на ноутбуке hp
            3. Как установить метро фор стим
            4. Ошибка 80004005 windows 7 как исправить