В случае прямого слияния частичная упорядоченность сортируемых данных не дает никакого преимущества. Это объясняется тем, что на каждом проходе сливаются серии фиксированной длины. При естественном слиянии (ЕС) длина серий не ограничивается, а определяется количеством элементов в уже упорядоченных подпоследовательностях выделяемых на каждом проходе.
ЕС начинается с образования 2-х файлов t1, t2. Для этого поочередно считываются записи ai исходной последовательности (неупорядоченной) т.о., что если значения ключей соседних записей удовлетворяют условию f(ai)<=f(ai+1) (1), то они записываются в один файл. Как только встречаются f(ai)>f(ai+1) (2), то записи ai+1 копируются в другой файл. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.
На некотором проходе алгоритма выполняется слияние пар серий из 2-х файлов аналогично прямому слиянию с записью результатов в другую пару файлов. Но в отличие от прямого слияния длины сливаемых серий здесь не фиксированы, а определяются с помощью условия, рассматриваемого выше. Пока выполняется условие (1) считается, что записи входят в одну серию, если (2), то начинается новая серия. Такие проходы выполняются до тех пор , пока один файл из какой-либо пары не станет пустым. Замечание: при использовании для сортировки ЕС алгоритмов подобного прямому слиянию возможна потеря данных. Это объясняется тем, что для ПС количество серий в паре файлов м. отличаться не оболе чем на 1. Процесс слияния завершается после выбора всех пар, а последовательная серия, которая осталась без пары – копируется. Для ЕС количество серий в копируемых файлах моет отличаться более чем на 1. если при этом завершить проход копированием только одной непарной серии, то данные, оставшиеся в других непарных сериях м. б. потеряны.
Чтобы избежать возможной потери данных каждый проход должен завершаться копированием всех непарных серий в поочередно формируемые файлы:
Вычислительная сложность в сортировке ЕС в худшем случае оценивается аналогично прямому слиянию, но дает заметно лучший результат.
Опубликовал Kest
January 29 2010 21:15:22 ·
0 Комментариев ·
15226 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
