Слияние рассортированных подфайлов

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

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

Из сортируемого файла в основную память считывается максимально возможное количество элементов. После внутренней сортировки подфайл отсылается на периферийное устройство А. Затем другой не рассортированный подфайл считывается, сортируется и записывается на периферийное устройство В. Цикл чтения, сортировки и записи продолжается до тех пор, пока весь сортируемый файл не будет размещен на внешних устройствах. На каждом из устройств подфайлы последовательно перенумерованы символами At, Л2, Аз— и Въ В2, В3, причем внутренняя сортировка и распределение по устройствам выполнялись в порядке: Аъ В1у Л2, В2, Аз, В3 .

После того как такое распределение закончено, первые элементы подфайлов А г и Bi сравниваются и меньший из них записывается на устройство С. Это будет первый элемент первой строки устройства С. Выбранный элемент замещается следующим элементом из той же строки (в примере 2 из А х), снова повторяется сравнение, и меньший из элементов будет вторым элементом Сг. Процедура замещения, сравнения и записи продолжается до тех пор, пока не будет достигнут конец одной из строк. После этого элементы другой строки просто добавляются к строке С Далее выбирается вторая пара сортируемых строк (Л2иВ2), которые сливаются таким же способом на устройстве D (образуя строку Dx), следующие две строки сливаются на устройстве С и т. д. Эта процедура переменной записи на С и D продолжается до тех пор, пока в Л и б не останется больше элементов.

Аналогичным образом элементы сортируемых строк с устройств С и D попарно сравниваются и сливаются на устройствах Л и В. Описанный процесс с чередованием устройств ввода и вывода в целом продолжается до тех пор, пока не останется только один рассортированный файл.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Слияние рассортированных подфайлов Если подлежащий сортировке набор данных большой, то в основной памяти можно единовременно разместить только некоторую часть этого набора данных. В таком случае находящийся в основной памяти подфайл сортируется с помощью одного из описанных ранее методов и рассортированная элементарная строка записывается на ленту, диск или барабан. Известно несколько различных методов сортировки, зависящих от характера распределения строк на периферийных устройствах и того, как эти строки должны сливаться. В этом разделе мы познакомимся е тремя наиболее часто используемыми процедурами. В примерах используются четыре внешних устройства. Естественно, если при сортировке и слиянии доступно большее количество внешних устройств, то можно применить те же самые принципы и уменьшить общее время сортировки. Из сортируемого файла в основную память считывается максимально возможное количество элементов. После внутренней сортировки подфайл отсылается на периферийное устройство А. Затем другой не рассортированный подфайл считывается, сортируется и записывается на периферийное устройство В. Цикл чтения, сортировки и записи продолжается до тех пор, пока весь сортируемый файл не будет размещен на внешних устройствах. На каждом из устройств подфайлы последовательно перенумерованы символами At, Л2, Аз— и Въ В2, В3, причем внутренняя сортировка и распределение по устройствам выполнялись в порядке: Аъ В1у Л2, В2, Аз, В3 . После того как такое распределение закончено, первые элементы подфайлов А г и Bi сравниваются и меньший из них записывается на устройство С. Это будет первый элемент первой строки устройства С. Выбранный элемент замещается следующим элементом из той же строки (в примере 2 из А х), снова повторяется сравнение, и меньший из элементов будет вторым элементом Сг. Процедура замещения, сравнения и записи продолжается до тех пор, пока не будет достигнут конец одной из строк. После этого элементы другой строки просто добавляются к строке С Далее выбирается вторая пара сортируемых строк (Л2иВ2), которые сливаются таким же способом на устройстве D (образуя строку Dx), следующие две строки сливаются на устройстве С и т. д. Эта процедура переменной записи на С и D продолжается до тех пор, пока в Л и б не останется больше элементов. Аналогичным образом элементы сортируемых строк с устройств С и D попарно сравниваются и сливаются на устройствах Л и В. Описанный процесс с чередованием устройств ввода и вывода в целом продолжается до тех пор, пока не останется только один рассортированный файл.