|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.04.2010, 12:10 | #1 |
Пользователь
Регистрация: 24.02.2010
Сообщений: 14
|
Внешняя сортировка
3.1. Прямое слияние
Начнем с того, как можно использовать в качестве метода внешней сортировки алгоритм простого слияния, обсуждавшийся в конце предыдущей части. Предположим, что имеется последовательный файл A, состоящий из записей a1, a2, ..., an (снова для простоты предположим, что n представляет собой степень числа 2). Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки. Для сортировки используются два вспомогательных файла B и C (размер каждого из них будет n/2). Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. (Заметим, что процедура слияния для файлов полностью иллюстрируется рисунком 2.14.) На первом шаге для распределения последовательно читается файл A, и записи a1, a3, ..., a(n-1) пишутся в файл B, а записи a2, a4, ..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4), ..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении первая из них попадет в файл B, а вторая - в файл C. После слияния файл A будет содержать полностью упорядоченную последовательность записей. Помогите написать, только вместо файла массив |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Внешняя многофазовая сортировка слиянием... | maLoy*508 | Общие вопросы Delphi | 26 | 10.05.2011 14:49 |
Внешняя сортировка. | Evgeshk@ | Общие вопросы C/C++ | 0 | 20.12.2009 23:58 |
Внешняя компонента 1c 8.1 | Dunpeal | Общие вопросы Delphi | 3 | 05.12.2009 18:12 |
Внешняя сортировка | alex55 | Общие вопросы C/C++ | 0 | 21.03.2009 22:15 |
Внешняя сортировка | Ashraf | Помощь студентам | 1 | 29.05.2008 08:56 |