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

Так как не тратится лишняя память, например, при потоковом вводе с консоли или из файла.

1.6 Сортировка слиянием

Сортировка слиянием (merge sort) привлекает своей простотой и наличием некоторых особенностей (например, она принадлежит к алгоритмам класса O(n×log(n)) и не имеет худших случаев), но если приступить к его реализации, можно натолкнуться на большую проблему. Тем не менее, сортировка слиянием очень широко используется при необходимости сортировки содержимого файлов, размер которых слишком велик, чтобы поместиться в памяти. Данный метод также рассмотрен в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».^[4]

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

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

Смотрим на первые элементы обоих массивов. Элемент с меньшим значением переносим в результирующий массив. Снова смотрим на первые элементы в обоих массивах и снова переносим в результирующий массив элемент с меньшим значением, удаляя его из исходного массива. описанный процесс продолжается до тех пор, пока не исчёрпываются элементы одного из исходных массивов. После этого в результирующий массив можно перенести все оставшиеся элементы в исходном массиве. Такой алгоритм формально известен под названием алгоритма двухпутевого слияния (two-way merge algorithm).

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

Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных массивах. Если в первом из них находится - nэлементов, а во втором - m, нетрудно придти к выводу, что в худшем случае будет произведено (n+m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n).

Так каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Ведь для его работы необходимо иметь два отсортированных массива меньшей длины, из которых создаётся один большой массив.

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

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

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

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

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

Несмотря на то, что сортировка слиянием требует дополнительной памяти (объём которой пропорционален количеству элементов в исходном массиве), она обладает некоторыми интересными свойствами:

• сортировка слиянием принадлежит к классу O(n×log(n)).
• она устойчива.
• для сортировки слиянием не имеет значения ни порядок элементов в исходном массиве (будь то массив, отсортированный в прямом порядке или обратном), ни повторения значений в массиве, то есть сортировка слиянием не имеет худшего случая.

Очевидно, требуется n операций на создание первоначального дерева, а затем n шагов, каждый по logn сравнений для выбора нового наименьшего.

Глава 2 Алгоритмы неустойчивой сортировки

Сортировка методом Шелла.

Сортировка методом прочёсывания.

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

Быстрая сортировка.

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

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

Более подробное описание сортировки методом Шелла, сортировки методом прочёсывания и быстрой сортировки также изложено в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».^[5]

2.1 Сортировка методом Шелла

Этот метод разработал Дональд Л.Шелл в 1959 году. Он основан на сортировке методом вставок. Сортировка методом Шелла (Shell sort) пытается повысить скорость работы за счёт более быстрого перемещения элементов массива, находящихся далеко от нужных позиций. Данная сортировка предполагает перемещение таких элементов «прыжками» через несколько элементов одновременно, уменьшая размер «прыжков» и, в конце концов, окончательная установка элементов в нужные позиции выполняется с помощью классической сортировки методом вставок.

Рассмотрим выполнение сортировки методом Шелла на примере карточной колоды. Расположите карты колоды в длинную линию. Извлеките из этой линии карт первую и каждую четвёртую карту после первой (т.е. пятую, девятую и тринадцатую). Выполните сортировку выбранных карт методом вставок и снова поместите их в линию. Извлеките из колоды вторую и четвёртую карту после второй (т.е. шестую и девятую). Выполните сортировку выбранных карт методом вставок и снова поместите их в линию. Выполните те же операции над третей и каждой четвёртой картой после третей, а затем над четвёртой и каждой четвёртой картой после четвёртой.

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

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

Рис. 5 Сортировка методом Шелла

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

Сортировка методом Шелла работает путём вставки отсортированных подмножеств основного списка. Каждое подмножество формируется за счёт выборки каждого n-ного элемента массива, начиная с любой позиции в списке. В результате будет получено n подмножеств, которые отсортированы методом вставок. Полученная последовательность элементов массива называется отсортированной по n. Затем значение n уменьшается и снова выполняется сортировка. Уменьшение значений n происходит до тех пор, пока n не будет равно 1, после чего последний проход будет представлять собой стандартную сортировку методом вставок.

Идея метода сортировки Шелла заключается в том, что сортировка по n быстро переносит элементы массива в область, где они должны находиться в отсортированной последовательности, а уменьшение значений n позволяет уменьшать размер «прыжков» и в конце концов поместить элемент в требуемую позицию. Медленному перемещению элементов предшествуют большие «прыжки», сводящиеся к простой сортировке методом вставок.

Какие значения n лучше использовать?

Дональд Л.Шелл предложил значения 1, 2, 4, 8, 16, 32 и т.д. (естественно в обратном порядке), но с этими значениями связана одна проблема: до последнего прохода элементы массива с чётными индексами никогда не сравниваются с элементами нечётного индексами. И, следовательно, при выполнении последнего прохода всё ещё возможны перемещения элементов на большие расстояния.

В 1969 году Дональд Кнут (Donald Knuth) предложил последовательность 1, 4, 13, 40, 121 и т.д. (каждое последующее значение на единицу больше, чем утроенное предыдущее значение). Для массивов средних размеров эта последовательность позволяет получить достаточно высокие характеристики быстродействия.

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

2.2 Сортировка методом прочёсывания