Файл: Сортировка слиянием.pdf

Гарантированное время выполнения, пропорциональное NlogN, может быть и недостатком. Например, существуют методы, которые могут быть адаптированы таким образом, что в некоторых особых ситуациях время их выполнения может быть линейным - например, при достаточно высокой упорядоченности файла либо при наличии лишь нескольких различных ключей. В противоположность этому время выполнения сортировки слиянием зависит главным образом от числа ключей входного файла и практически не чувствительно к их упорядоченности [10, С. 332].

Сортировка слиянием является устойчивой, и это склоняет чашу весов в ее пользу в тех приложениях, в которых устойчивость важна. Конкурирующие с ней методы, такие как быстрая сортировка или пирамидальная сортировка, не относятся к числу устойчивых. Различные приемы, обеспечивающие устойчивость этих методов, обычно требуют дополнительной памяти; поэтому если на первый план выдвигается устойчивость, то требование дополнительной памяти для сортировки слиянием становится менее важным [10, С. 332].

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

В таблице 1 показана относительная эффективность различных рассмотренных нами усовершенствований. Как это часто бывает, оказывается, что если направить усилия на оптимизацию внутреннего цикла алгоритма сортировки, то время выполнения сортировки можно сократить наполовину и даже больше [10, С. 335].

Также можно добиться дальнейшего повышения производительности, поместив наименьшие элементы обоих массивов в простые переменные или машинные регистры процессора и избежав, таким образом, лишних обращений к массивам. Тогда внутренний цикл сортировки слиянием можно свести к сравнению (с условным переходом), увеличению на единицу значений двух счетчиков (k и либо i, либо j) и проверке условия завершения цикла с условным переходом. Общее количество команд в таком внутреннем цикле несколько больше, чем для быстрой сортировки, но эти команды выполняются всего лишь Nlg N раз, в то время как команды внутреннего цикла быстрой сортировки выполняются на 39% чаще (или на 29% для варианта с вычислением медианы из трех). Для более точного сравнения этих двух алгоритмов в различных средах нужна их тщательная реализация и подробный анализ. Однако точно известно, что внутренний цикл сортировки слиянием несколько длиннее внутреннего цикла быстрой сортировки [10, С. 335].

В данном случае сортировка слиянием обладает несомненным преимуществом перед быстрой сортировкой в том, что она устойчива и гарантирует высокую скорость (вне зависимости от характера входных данных), но проигрывает в том, что использует дополнительный объем памяти, пропорциональный размеру массива [10, С. 335].

Представленные здесь относительные временные показатели различных видов сортировки для случайно упорядоченных файлов чисел с плавающей точкой различного размера N показывают, что: стандартная быстрая сортировка примерно в два раза быстрее стандартной сортировки слиянием; добавление отсечения небольших файлов снижает время выполнения и нисходящей, и восходящей сортировок слиянием примерно на 15%; для указанных в таблице размеров файлов быстродействие нисходящей сортировки слиянием приблизительно на 10% выше, чем восходящей; даже если устранить затраты на копирование файла, то и в этом случае сортировка слиянием случайно упорядоченных файлов на 50-60% медленнее обычной быстрой сортировки (см. таблица 1).

Таблица 1. Эмпирическое сравнение алгоритмов сортировки слиянием

Обозначения:

Q - Стандартная быстрая сортировка

T - Стандартная нисходящая сортировка слиянием

T* - Нисходящая сортировка слиянием с отсечением небольших файлов

O - Нисходящая сортировка слиянием с отсечением и без копирования массива

B - Стандартная восходящая сортировка слиянием

B* - Восходящая сортировка слиянием с отсечением небольших файлов

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

Возможно, быструю сортировку было бы точнее назвать алгоритмом «властвуй и разделяй»: в рекурсивных реализациях при каждом обращении большая часть работы выполняется перед рекурсивными вызовами. А вот рекурсивная сортировка слиянием более соответствует принципу «разделяй и властвуй» : вначале файл делится на две части, и затем каждая часть обрабатывается отдельно. Сортировка слиянием сначала выполняется для небольших задач, а в заключение обрабатывается самый большой подфайл. Быстрая сортировка начинается с обработки наибольшего подфайла и завершается обработкой подфайлов небольших размеров. Любопытно сравнение этих алгоритмов по аналогии с управлением коллективом сотрудников: быстрая сортировка соответствует тому, что каждый руководитель затрачивает свои усилия на правильное разбиение задачи на подзадачи, так что после выполнения всех подзадач работа будет успешно выполнена; сортировка слиянием соответствует тому, что каждый руководитель быстро и произвольно делит задачу пополам, а затем, после решения подзадач, затрачивает свои усилия на объединение результатов [10, С. 336].

Это различие ясно видно в нерекурсивных реализациях. Быстрой сортировке нужен стек - для хранения больших подзадач, разбиение на которые зависит от входных данных. Сортировка слиянием допускает простые нерекурсивные реализации, поскольку способ разбиения файла на части не зависит от данных, и становится возможным изменение очередности решения подзадач, что позволяет упростить программу.

Существует точка зрения, что быструю сортировку естественнее рассматривать как нисходящий алгоритм, поскольку он начинает работу на вершине дерева рекурсии, а затем для завершения сортировки опускается вниз. Можно обдумать и нерекурсивный вариант быстрой сортировки, которая обходит дерево рекурсии сверху вниз, но по уровням. Таким образом, сортировка многократно проходит по массиву, разбивая файлы на меньшие подфайлы. Для массивов этот метод не годится из-за большого объема затрат на хранение информации о подфайлах, а для связных списков он аналогичен восходящей сортировке слиянием [4, С. 67].

Сортировка слиянием и быстрая сортировка отличаются по признаку устойчивости. Если подфайлы при сортировке слиянием упорядочены с соблюдением устойчивости, то вполне достаточно обеспечить устойчивость слияния, что сделать совсем нетрудно. Рекурсивная структура алгоритма автоматически приводит к индуктивному доказательству устойчивости. Но для реализации быстрой сортировки с использованием массивов нет очевидного простого способа разбиения файлов, обеспечивающего устойчивость, так что устойчивость исключается еще до вступления в дело рекурсии. Хотя примитивная реализация быстрой сортировки для связных списков является устойчивой [4, С. 67].

2.6. Пирамидальная сортировка

Пирамидальная сортировка была предложение Дж. Уильямсом в 1964 году. Это алгоритм сортировки массива произвольных элементов; требуемый им дополнительный объём памяти не зависит от количества исходных данных. Время работы алгоритма в среднем, а также в лучшем и худшем случаях.

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

Сортировка начинается с построения пирамиды. При этом максимальный элемент списка оказывается в вершине дерева: ведь потомки вершины обязательно должны быть меньше. Затем корень записывается последним элементом списка, а пирамида с удаленным максимальным элементом переформировывается. В результате в корне оказывается второй по величине элемент, он копируется в список, и процедура повторяется пока все элементы не окажутся возвращенными в список. [10, С. 362].

2.7. Поразрядная сортировка

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

Часто нет необходимости в полной обработке ключей на каждом этапе: при поиске в телефонном справочнике, чтобы найти страницу с номером какого-либо абонента, достаточно проверить лишь несколько первых букв его фамилии. Чтобы добиться такой же эффективности алгоритмов сортировки, перейдем от абстрактной операции сравнения ключей к абстракции, в которой ключи разбиваются на последовательность частей фиксированного размера — байтов. Двоичные числа представляют собой последовательности битов, строки — последовательности символов, десятичные числа — последовательности цифр, аналогично могут рассматриваться и многие другие (хотя и не все) типы ключей. Методы сортировки, основанные на обработке ключей по частям, называются поразрядными методами сортировки (radix sort). Эти методы не просто сравнивают ключи, а обрабатывают и сравнивают части ключей [10, С. 401].

Алгоритмы поразрядной сортировки интерпретируют ключи как числа, представленные в системе счисления с основанием R, при различных значениях R (основание системы счисления — radix), и работают с отдельными цифрами этих чисел. Например, когда почтово-сортировочная машина обрабатывает пачку конвертов, каждый из которых помечен 5-значным десятичным числом, она распределяет эту пачку на десять отдельных пачек: в одной находятся пакеты, номера которых начинаются с 0, в другой находятся пакеты с номерами, начинающимися с 1, в третьей — с 2 и т.д. Каждая пачка может быть обработана отдельно с помощью того же метода, по следующей цифре, или более простым способом, если в пачке всего лишь несколько пакетов. Если теперь собрать пакеты из пачек в порядке от 0 до 9 и в таком же порядке внутри каждой пачки, то они окажутся упорядоченными. Эта процедура представляет собой поразрядную сортировку с R = 10, и такой метод удобен в приложениях, использующих сортировку, где ключами являются десятичные числа, содержащие от 5 до 10 цифр — наподобие почтовых кодов, телефонных номеров или идентификационных номеров [10, С. 404].

Алгоритмы поразрядной сортировки основаны на абстрактной операции «извлечь i-ю цифру ключа». К счастью, в С++ есть низкоуровневые операции, позволяющие реализовать такие действия просто и эффективно. Это очень важно, поскольку некоторые языки программирования (например, Pascal), поощряя машинно-независимое программирование, намеренно затрудняют написание программ, зависящих от способа представления чисел в конкретной машине. В таких языках трудно реализовать многие виды битовых операций, удобные для выполнения на большинстве компьютеров. В частности, жертвой этой " прогрессивной " философии стала и поразрядная сортировка. Однако создатели С и С++ поняли, что прямые операции с битами часто бывают весьма полезны, и при реализации поразрядной сортировки можно воспользоваться низкоуровневыми языковыми средствами [10, С. 405].