При ВС требуется работать с данными, расположенными на внешних устройствах последовательного доступа. Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов, где всегда доступен каждый элемент.
В основе большинства методов ВС лежит процедура слияния. Слияние означает объединение двух упорядоченных наборов данных в 1 упорядоченную последовательность с помощью повторяющегося выбора доступных в данный момент элементов.
В процессе слияния поочередно сравниваются ключи в парах, доступных в текущий момент записей из исходных наборов данных.
Запись с меньшим набором ключа помещается в результирующий набор данных и исключается из исходного файла. Действия повторяются, пока не будет исчерпан один из исходных наборов данных. Затем оставшиеся в другом наборе данные пересылаются в результирующий файл без изменения порядка следования.
Покажем реализацию процедуры слияния для двух упорядоченных массивов A[1..n] , B[1..m] в результирующий набор данных C[1.. n+m] i, j, k – элементы в соответствующих массивах. Схема процедуры слияния:
Опубликовал Kest
January 28 2010 14:01:59 ·
0 Комментариев ·
16467 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
