Файл: Методы сортировки данных.pdf

1.5 Сортировка двоичным (бинарным) деревом

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

Описание метода сортировки двоичным деревом детально рассмотрено в книге Н. Вирта: «Алгоритмы и структуры данных».^[3]

Вместо «предок» и «преемник» также непосредственно употребляют термины «родитель» и «потомок». Все элементы дерева также называют «узлами». При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом, вставляя на место. Если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить.

Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:

44 44 44 44 44

\ / \ / \ / \

55 12 55 12 55 12 55

\ \ \

42 42 94

(**) 44 44 (*) 44

/ \ / \ / \

12 55 12 55 12 55

\ \ / \ \ / \ \

42 94 06 42 94 06 42 94

/ / / /

18 18 18 67

Дерево может быть и более-менее ровным, как на (*), может и иметь всего две основные ветви (**), а если входная последовательность уже непосредственно отсортирована, то дерево выродится в линейный список.

Рекурсивно обходя полученное дерево по правилу "левый сын - родитель - правый сын", то, записывая все встречающиеся элементы в массив, мы будем получать упорядоченное в порядке возрастания множество. Hа этом и основана идея сортировки деревом.

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

Общее быстродействие метода O(n×logn). Поведение неестественно, устойчивости, вообще говоря, нет.

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

Поэтому данная сортировка обычно применяют там, где:

- построенное дерево можно с успехом применить для других задач;

- данные уже построены в 'дерево';

- данные можно считывать непосредственно в дерево.

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

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 Сортировка методом прочесывания

Сортировку методом прочёсывания (comb sort) нельзя отнести к обычным и общепринятым алгоритмам. На сегодняшний день он малоизвестен, тем не менее, он отличается достаточно быстрым уровнем быстродействия и удобной реализацией. Метод был разработан Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) в 1991 году. Фактически он использует пузырьковую сортировку таким же образом, как и сортировка методом Шелла сортировку методом вставок.

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

Перетасуйте карты и разложите на столе. Выделите 1 и 9 карту (расстояние между картами 8), если они находятся в неправильном порядке - поменяйте их местами. Выделите 2 и 10 карты (расстояние между картами 6) и, при необходимости, поменяйте их местами. То же самое проделайте для 3 и 11 карты (расстояние между картами 4), 4 и 12 карты (расстояние между картами 3), а затем 5 и 13 (расстояние между картами 2). Далее сравнивайте и переставляйте пары карт (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12) и (7, 13), т.е. карты непосредственно отстоящие друг от друга на шесть позиций. А теперь выполните проход по разложенным картам, отстоящим друг от друга на четыре позиции, затем на три и две позиции, как показано на рисунке 6. После этого выполните стандартную пузырьковую сортировку.^[6]

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

Каким образом были получены значения расстояний 8, 6, 4 ,3, 2, 1? Разработчики этого метода сортировки провели большое количество экспериментов и эмпирическим путём пришли к выводу, что значение каждого последующего расстояния «прыжка» должно быть получено в результате деления предыдущего значения расстояния на 1,3.

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

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

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

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