Внешняя сортировка. Основные характеристики сортировок методом слияний

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

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

Отрезок, состоящий из одного элемента, упорядочен всегда. Если длина серии фиксирована, то слияние называется простым. Сортировка, при которой всегда сливаются две самые длинные из возможных серий, называется естественным слиянием. Вначале серии распределяются на два или несколько вспомогательных файлов. Распределение серий идет поочередно, т.е. первая серия записывается в первый вспомогательный файл, вторая – во второй и т.д. После того, как произошла запись в последний файл, опять начинается запись серии в первый вспомогательный файл. После распределения всех серий они объединяются в более длинные упорядоченные отрезки: из каждого вспомогательного файла берется по одной серии и они сливаются. Если в каком-то файле серия заканчивается, то следующая пока не рассматривается. Сформированный более длинный упорядоченный отрезок записывается либо в исходный файл, либо в какой-то из вспомогательных файлов, это зависит от вида сортировки. Когда все серии из всех вспомогательных файлов объединены в новые серии, опять начинается их распределение. Так продолжается до тех пор, пока все данные не будут упорядочены.

1) Количество вспомогательных файлов, на которые идет распределение серий.

ü Если данные распределяются на два вспомогательных файла, то сортировка называется двухпутевым слиянием,

ü если на N (N>2) вспомогательных файлов, то – многопутевым слиянием.

2) Количество фаз в реализации сортировки.

ü Фазой называются действия по однократной обработке всего множества.

ü Наименьший процесс, повторение которого составляет процесс сортировки проход (этапом).

ü В двухфазной сортировке отдельно реализуются две фазы:

1) распределение

2) и слияние.

ü После того, как произошло распределение данных по вспомогательным файлам, они объединяются и записываются в исходный файл.

ü В однофазной сортировке обе эти фазы объединены в одну.

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

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

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

Алгоритм прямого слияния.

На первом шаге упорядоченные отрезки имеют длину, равную единице, т.е. состоят из одного элемента.

Затем они объединяются и  в случае двухпутевого слияния вновь сформированные отрезки будут состоять из двух элементов,  а в случае многопутевого – из N элементов.

o Предположим, что имеется последовательный файл F0, состоящий из записей a₁, a₂, ..., a_n.

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

o Для сортировки используются два вспомогательных файла F1 и F2 (размер каждого из них будет n/2).

o Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла F0 в файлы F1 и F2, а затем слияние файлов F1 и F2 в файл F0.

o На первом шаге для распределения последовательно читается файл F0, и

· записи a₁, a₃, ..., a_n-1 пишутся в файл F1,

· а записи a₂, a₄, ..., a_n - в файл F2 (начальное распределение).

o Начальное слияние производится над парами (a₁, a₂), (a₃, a₄), ..., (a_n-1, a_n), и результат записывается в файл F0.

o На втором шаге снова последовательно читается файл F0,

· и в файл F1 записываются последовательные пары с нечетными номерами,

· а в файл F2 - с четными.

o При слиянии образуются и пишутся в файл F0 упорядоченные четверки записей.

o И так далее.

o Перед выполнением последнего шага файл F0 будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении

· первая из них попадет в файл F1,

· а вторая - в файл F2.

o После слияния файл F0 будет содержать полностью упорядоченную последовательность записей.

o Сортировка прямым слиянием заканчивается, если:

· после фазы слияния длина серии не меньше количества элементов в файле;

· на фазе слияния осталась ровно одна серия;

· второй по счету вспомогательный файл для однофазной сортировки после распределения серий остался пустым.

Алгоритм естественного слияния.

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

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

В каждом проходе число серий уменьшается в N раз (если количество серий во вспомогательных файлах одинаково), а общее число пересылок не более, чем n ∗ [log n].

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

Так же как и прямое слияние, сортировка естественным слиянием может быть

a. двухпутевой или многопутевой,

b. двухфазной или однофазной.

При распределении распознается

c. первая серия записей и переписывается в файл F1,

d. вторая - в файл F2 и т.д.

При слиянии

e. первая серия записей файла F1 сливается с первой серией файла F2,

f. вторая серия F1 со второй серией F2 и т.д.

Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла F0.

Процесс завершается, когда в файле F0 остается только одна серия.

· Пусть исходный файл состоит из элементов:

F0: 1  3  14  6  8  9  2  4  5  8  2  3  1  16

· Тогда двухпутевое двухфазное естественное слияние будет проходить следующим образом:

· Для упорядочивания данных в сортировке прямым слиянием при тех же самых условиях потребовалось бы 4 прохода, поскольку длина серии на 4-ом проходе составляла бы 16 элементов, а в исходном файле содержится 14 элементов.