Я пишу информационный бюллетень для учащихся под названием Mighty Knowledge. Каждый новый выпуск содержит ссылки и основные уроки из самого лучшего контента, включая цитаты, книги, статьи, подкасты и видео. Каждый выбран специально для того, чтобы научиться жить более мудрой, счастливой и полной жизнью. Зарегистрируйтесь здесь.

Timsort - самый быстрый алгоритм сортировки на свете. Сделано разработчиком для разработчиков. Он создан для реального мира, а не для академических кругов.

Представляем Timsort

Timsort - это гибридный стабильный алгоритм сортировки, созданный на основе сортировки слиянием и сортировки вставкой, предназначенный для эффективной работы практически с любыми типами реальных данных. Тим Питер создал Timsort (и его потрясающее название) для языка программирования Python в 2001 году.

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

Итак, насколько это эффективно? Что ж, с момента его изобретения в 2001 году он использовался в качестве алгоритма сортировки по умолчанию в Python, Java, Android OS и Octave! Это надежный и надежный метод сортировки.

Что касается фактических количественных показателей, ознакомьтесь с приведенной ниже таблицей, в которой показаны сложности различных алгоритмов сортировки, включая Timsort. Timsort - это действительно умное слияние сортировки вставкой и сортировки слиянием!

Вставная часть

Сортировка вставкой - это простой алгоритм сортировки, который наиболее эффективен для небольших списков (т. Е. С меньшим объемом данных). Это довольно медленно для больших списков, но очень быстро для маленьких. Идея сортировки вставкой заключается в следующем:

  • Посмотрите на элементы один за другим
  • Создайте отсортированный список, вставив элемент в правильное место

Таким образом, с Timsort у нас есть жесткое и быстрое правило: если в нашем списке меньше 64 элементов, запустите сортировку вставкой. Это довольно интуитивно понятно, поскольку, как мы видим из диаграммы сложности алгоритмов сортировки, сортировка вставкой привязана к верхней «лучшей» сложности (когда у нас есть меньший список) и «худшей» пространственной сложности!

Посмотрите гифку ниже, чтобы проиллюстрировать, как работает сортировка вставкой!

«Прогоны» Тимсорта

Если список превышает 64 элемента, Timsort сначала просматривает список, ища части, которые строго увеличиваются или уменьшаются. Если часть уменьшается, она перевернет эту часть. Это значительно снизит вычислительную нагрузку на оставшуюся часть сортировки. Timsort называет эти уже отсортированные части «пробегами».

Например, если пробег уменьшается, это будет выглядеть следующим образом (где пробег выделен жирным шрифтом):

Если пробег увеличивается, это будет выглядеть так:

Также существует настраиваемый параметр, называемый minrun. Minrun - это размер, который определяется на основе размера массива. Алгоритм выбирает его так, чтобы большинство прогонов в случайном массиве имели длину или становились минимальными.

Часть слияния

Теперь, когда Timsort имеет много наборов чисел или «прогонов», он будет выполнять своего рода модифицированную сортировку слиянием в списке. Во-первых, для обеспечения стабильности Timsort не обменивается двумя числами равного значения. Это не только сохраняет их исходные позиции в списке, но и позволяет алгоритму работать быстрее.

Затем, поскольку у нас уже есть несколько прогонов, которые представляют собой просто отсортированные подсписки, нам не нужно делать для них какое-либо разделение на захват, что мы обычно делаем при сортировке слиянием. В какой-то момент нам просто нужно будет объединить эти прогоны с другими прогонами / группами сортировки слияния.

… Но тогда возникает вопрос: когда мы должны объединиться с запуском, а не работать с остальными несортированными данными?

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

Чтобы обеспечить этот компромисс, Timsort отслеживает три самых последних элемента в стеке с именами A, B и C, где A - самый последний, а C - самый низкий, и создает два жестких правила, которые должны выполняться в отношении этих предметов:

1. A > B + C

2. B > C

Это вынуждает Timsort сосредоточить свои вычисления на наиболее важных и рентабельных задачах, которые ему необходимо выполнять.

Простые, умные и интуитивно понятные правила оказываются сильной стороной алгоритма Timsort.

Код Timsort на Python

Вот понятный и простой Python-код алгоритма Timsort, написанный с нуля!

Но помните, Timsort уже встроен в Python! Итак, вы уже используете его, когда вызываете встроенную функцию сортировки следующим образом:

my_sorted_list = sorted(my_list)