Алгоритмы сортировки слиянием (MergeSort)

⇐ ПредыдущаяСтр 4 из 11Следующая ⇒

Эта группа алгоритмов построена на следующей общей идее. Пусть имеются два массива, A₁ и A₂, каждый из которых уже отсортирован. Тогда можно выполнить операцию слияния этих массивов, результатом которой будет новый массив B, содержащий все элементы из A₁ и A₂ и при этом тоже сортированный. При этом важно, что процедура слияния может быть выполнена за линейное время, а точнее сказать, число итераций будет равно числу элементов B.

Операция слияния выполняется просто как просмотр массивов A₁ и A₂ от начала к концу; каждый раз сравнивается пара текущих элементов из A₁ и A₂, меньший из них записывается в массив B, после чего индекс в соответствующем массиве увеличивается на 1. Когда достигается конец одного из массивов A₁ или A₂, оставшиеся элементы другого массива переносятся в B.

Но откуда возьмутся сортированные массивы A₁ и A₂? От ответа на этот вопрос зависит выбор конкретного алгоритма сортировки слиянием.

Наиболее простой из этих алгоритмов так и называется: сортировка простым слиянием. Он заключается в следующем. Пусть дан произвольный (не сортированный) массив A. Для простоты примем сначала, что число его элементов четно: n = 2m. Каждый элемент из A может рассматриваться как отдельный массив длиной 1, причем такой «массив», конечно, можно считать сортированным. Будем брать в качестве сливаемых массивов a₁ и a_m+1, a₂ и a_m+2, … a_m и a₂_m. Получающиеся при слиянии упорядоченные пары элементов будем помещать во вспомогательный массив B от его начала.

Теперь возьмем в качестве сливаемых массивов пары элементов из B: (b₁, b₂) и (b_m+1, b_m+2), (b₃, b₄) и (b_m+3, b_m+4), и т.д. Образующиеся упорядоченные четверки элементов будем записывать в массив A от его начала. Затем будем сливать эти четверки в группы по 8 и записывать их в B, и т.д. Через несколько таких проходов длина упорядоченной группы элементов достигнет n, т.е. массив окажется полностью отсортированным.

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

Чтобы оценить эффективность алгоритма, напомним, что число итераций при слиянии двух массивов равно их суммарной длине. Очевидно, что на каждом проходе слияния будет выполняться n итераций. Число проходов тоже нетрудно определить: поскольку длина отсортированных групп удваивается при каждом проходе, то эта длина достигнет значения n после выполнения log₂n проходов. Отсюда следует, что время сортировки T(n) = O(n·log(n)), причем эта оценка справедлива как для среднего, так и максимального времени сортировки. Таким образом, алгоритмы слияния являются другим видом алгоритмов сортировки (помимо пирамидальной сортировки), которые гарантируют время порядка n·log(n) даже в худшем случае.

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

Среди возможных модификаций алгоритма слияния можно упомянуть алгоритм естественного слияния. Его отличие заключается в определении начального набора сливаемых сортированных массивов. Если в алгоритме простого слияния в качестве такого набора использовались отдельные элементы массива, которые мы рассматривали как подмассивы длиной 1, то идея естественного слияния – в том, что исходный несортированный массив с высокой вероятностью уже содержит немало отрезков, на которых элементы расположены по возрастанию. Такие «естественно сортированные» отрезки называют сериями. Легко показать, что в полностью случайном массиве средняя длина серии равна 2. На практике же, как уже отмечалось, могут встречаться частично отсортированные массивы со значительно более длинными сериями. Использование серий в качестве исходного набора сливаемых массивов может привести к уменьшению числа проходов слияния. Однако реализация алгоритма естественного слияния несколько более сложна, чем для простого слияния.

Задача внешней сортировки

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

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

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

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

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

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

Совершенно по-другому ведет себя сортировка слиянием.

Обычно этот алгоритм для файлов реализуют как чередование двух фаз работы: фазы разделения и фазы слияния (рис. 3.3).

Рис. 3.3. Двухфазное слияние файлов

На фазе разделения исходный файл A просматривается от начала до конца и из него выделяются серии записей, упорядоченные по возрастанию. Нечетные по счету серии записываются во вспомогательный файл B1, четные – в файл B2.

На фазе слияния просматриваются файлы B1 и B2, прочитанные из них серии попарно сливаются и записываются в файл A.

Фазы разделения и слияния повторяются до тех пор, пока в A не будет записана единственная серия, содержащая все элементы в отсортированном виде.

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

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

Основной недостаток алгоритмов слияния – потребность во вспомогательном массиве – для случая сортировки файлов выступает как потребность в двух вспомогательных файлах B1 и B2, суммарный размер которых равен размеру сортируемого файла. Конечно, это не очень приятное свойство, однако дисковое пространство обычно является менее дефицитным ресурсом, чем оперативная память.

Оценка эффективности методов внешней сортировки «в смысле O-большое», приводит к результату, на первый взгляд парадоксальному. Одна и та же оценка T(n) = O(n× log(n)) получается и для «подходящего» MergeSort, и для «неподходящего» QuickSort. Но здесь надо вспомнить, что оценка с точностью до O-большого характеризует только скорость роста времени при увеличении n, конкретные же значения T(n) очень сильно различаются для разных алгоритмов. В первом приближении можно считать, что для алгоритмов слияния значение n как бы делится на число записей таблицы, помещающихся в одном секторе диска.

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒