Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Классификация алгоритмов сортировки).pdf

Недостатки данного алгоритма следующие:

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

4.5 Метод сортировки TimSort

Метод TimSort не является «самостоятельным» методом сортировки. Вместо этого он пытается соединить положительные стороны двух методов – сортировки вставками и сортировки слиянием, которые были рассмотрены ранее.

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

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

Перечислим шаги, которые необходимо выполнить для реализации метода.

Вначале определяется минимальный размер «подмассивов», на которые мы будем делить исходный массив. С одной стороны, он не должен быть очень маленьким, иначе придется слишком долго сливать их на последнем шаге. С другой стороны, он не должен быть очень большим, так как мы будем сортировать его методом вставок, а он работает медленно на больших массивах. Были проведены эксперименты, и определено, что лучше всего выбирать значения в диапазоне от 32 до 65. Это число – параметр алгоритма, его можно либо задать в коде, либо каким-то образом определить на основе исходных данных. Обозначим это число как NUM.

Далее необходимо разбить исходный массив на подмассивы. Для этого, начиная с первого элемента еще неразбитой части массива, мы выбираем два элемента. Если они идут по убыванию, меняем их местами (чтобы они шли по возрастанию). Далее, смотрим на третий элемент и далее. Если в какой-то момент, пока мы еще не взяли NUM элементов, мы обнаруживаем, что массив неупорядочен, берем ровно NUM элементов. Если же после просмотра NUM элементов, окажется, что все они упорядочены – то мы идем далее, пока не найдем первый неупорядоченный элемент, и помечаем, что данный «подмассив» сортировать не надо – он уже упорядочен, и следующий шаг для данного подмассива можно пропустить.

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

Далее необходимо объединить все отсортированные подмассивы в один. Эта процедура также поддается оптимизации – в оптимальном алгоритме подмассивы поочередно заносятся в структуру под названием «стек», и при выполнении определенных условий сливаются друг с другом. В «наивном» варианте можно просто сливать подмассивы друг с другом в порядке очереди – первый со вторым, получившийся с третьим, и так далее.

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

Из-за того, что алгоритм работает довольно быстро, он начал использоваться во многих серьезных программных продуктах, таких как Python, Java [6] и Android [7].

Однако данный алгоритм обладает тем недостатком, что он довольно сложен, и в его реализации очень легко допустить ошибку, а так как он используется во многих программных продуктах, то речь будет идти о миллиардах пользователей по всему миру. Сам алгоритм был разработан Тимом Петерсом (в честь него он и был назван TimSort) в 2002 году, но в его реализации была допущена досадная ошибка, приводящая к его некорректной работе на специально подобранных входных данных.

Из-за сложности алгоритма, сама ошибка оставалась незамеченной в течение целых 13 лет – с 2002 по 2015 год, причем даже в 2015 году она была найдена не людьми. Было решено использовать специальную программу KeY, чтобы доказать корректность некоторых алгоритмов (в том числе сортировки) формально (то есть, математически строго). Была доказана корректность двух более медленных алгоритмов, но программа так и не смогла доказать корректность алгоритма TimSort. Этим заинтересовались авторы данной программы, и выяснили, что действительно, в реализации данного алгоритма была допущена ошибка [5].

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

5. Непрактичные алгоритмы сортировки

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

Алгоритм Bogosort задумывался как способ отсортировать массив самым медленным способом. Он имеет асимптотическое время выполнения , что очень много, так как факториал растет чрезвычайно быстро в зависимости от роста . Сам алгоритм заключается в том, что мы просто произвольно перемешиваем массив (что можно сделать способами), а затем просто проверяем, получилось ли отсортировать массив или нет (проходя по нему один раз). То есть, при сортировке массива мы полагаемся на случайность. Естественно, из-за ее медленности, такой сортировкой никто не пользуется в реальной жизни.

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

Алгоритм Stooge Sort (блуждающая сортировка), скорее всего, разрабатывался как самый странный метод сортировки, который, тем не менее, дает вменяемое (хотя и более плохое, чем обычные методы) асимптотическое время сортировки. Оно равно . То есть, можно сказать, что хотя этот алгоритм медленнее даже самых простых алгоритмов , однако, тем не менее, он не создавался с целью быть «самым медленным», как Bogosort, и не слишком отличается от стандартных более медленных алгоритмов.

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

• Если в конце списка значение элемента меньше, чем в начале, то поменять первый и последний элементы местами;
• Если в сортируемом списке есть хотя бы три элемента, то выполнить следующие три шага, если нет – то сортировка окончена:
  • Рекурсивно вызвать процесс сортировки для первых списка;
  • Рекурсивно вызвать процесс сортировки для последних списка;
  • Снова рекурсивно вызвать процесс сортировки для первых списка.

Несмотря на то, что процесс сортировки выглядит довольно странно (например, не совсем понятно, зачем нужно два раза вызывать процесс для первых двух третей списка, и почем именно двух третей), данный процесс работает.

6. Алгоритмы сортировки, не основанные на сравнениях

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

Первым представителем такого вида сортировок можно назвать блочную сортировку. Данная сортировка, прежде чем непосредственно сортировать элементы массива, делит их на несколько корзин (bucket’ов), например, на десять. Если у нас в массиве находятся числа от 0 до 1000, то в первой корзине будут находиться числа от 0 до 100, во второй – от 100 до 200, и так далее. Данное деление можно сделать за время порядка - просто пробежав по массиву от начала до конца. Затем, когда элементы разложены по корзинам, происходит сортировка каждой корзины. При этом используется любой вид сортировки – либо какой-то стандартный, либо блочная сортировка вызывается рекурсивно. После того, как каждая корзина отсортирована, происходит объединение всех элементов в один большой массив. Так как значения каждой корзины располагаются строго друг за другом, то получить итоговый массив можно последовательно объединив корзины.

В чем смысл деления исходного массива на корзины? Дело в том, что алгоритма сортировки любого массива с асимптотическим временем до сих пор не найдено. Следовательно, в любом случае, скорость сортировки массива падает быстрее, чем растет число его элементов. Например, мы сортируем некоторый массив за 10 секунд. Затем мы увеличиваем число элементов массива в 10 раз, но время исполнения увеличится больше чем в десять раз (зависит от алгоритма, но для примера допустим, что в 20 раз, то есть, нам потребуется 200 секунд). Однако если же мы, как и раньше, увеличим размер массива в десять раз, а затем раскидаем данные по десяти корзинам, то каждую из них, как и раньше, можно будет отсортировать за 10 секунд. Итого нам понадобится секунд, что в два раза меньше. Однако тут следует учесть, что на раскладывание данных по корзинам и обратную сборку также требуется время, поэтому итоговое время будет зависеть от числа корзин и распределения исходных данных.

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

Еще одним представителем сортировок, не основанных на сравнениях, является алгоритм сортировки подсчетами. Этот алгоритм можно применять лишь к таким массивам, в которых существует довольно небольшое (не более нескольких миллионов) различных значений. Например, этот алгоритм идеально подойдет для сортировки оценок учеников (всего пять вариантов), однако совсем не подойдет для сортировки фамилий, имен и отчеств полутора миллиардов жителей Китая.

В случае если в нашем массиве есть лишь N различных элементов, необходимо каким-то способом их пронумеровать от 1 до N (в случае с оценками это делается элементарно – оценки сами представляют собой последовательность от 1 до 5). Далее необходимо создать массив размера N, который заполнить нулями. После этого необходимо пробежать от начала массива до конца (это займет времени), и для каждого найденного значения увеличить значение нужной ячейки только что созданного массива. Например, если выясняется, что ученик получил четвертку, то необходимо увеличить четвертый элемент массива (итоговое количество полученных четверок).