Генераторы программ сортировки слияния

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

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

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

На рис. 9.23 изображена блок-схема обычного генератора программ сортировки/слияния. Так, например, программа сортировки слияния SM1 фирмы IBM использует минимум три магнитные ленты или один диск и может объединить до 16 файлов [25], Может быть задано не более 64 ключей, и бинарные ключи не обязательно должны начинаться с границы байта. Связь своих подпрограмм со сгенерированной программой сортировки пользователь может осуществить через 17 входных и выходных точек. Программа сама выбирает метод сортировки, лучше всего соответствующий объему доступной основной-памяти, количеству и типу периферийных устройств и объему сортируемых данных.

Максимальная длина записи зависит от типа используемых периферийных устройств и объема основной памяти, выделенного программе сортировки, и изменяется от 11000 до 32000 байт. Программа осуществляет сбалансированную сортировку, если она может использовать более трех магнитных лент и объем входных данных не задан или подсчитан приблизительно. Доступный объем основной памяти при сбалансированной сортировке не может быть меньше 12К, а для промежуточного хранения данных допускается использование не более 32 магнитных лент.

Если для промежуточного хранения выделено только три ленты, то программа автоматически выбирает более эффективный в данном случае метод многофазной сортировки. Минимальный объем основной памяти при этом методе также равен 12К.

Наконец, при осциллирующей сортировке требуется минимум 21К основной памяти и максимум 17 лент для промежуточного хранения данных.

Один из режимов сортировки с использованием диска требует минимум 13К основной памяти и работает максимум с шестью областями на диске, в то время как другие режимы требуют 24К основной памяти и обрабатывают До 17 областей на диске.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Генераторы программ сортировки слияния Почти все операционные системы имеют несколько типов генераторов программ сортировки слияния. Такой генератор, используя специальные управляющие команды, порождает программу сортировки, основанную на рассмотренных выше принципах. Обычно параметры, перфорируемые на управляющих картах, содержат такую информацию: длина записей; требуемый порядок (убывающий или возрастающий) представления рассортированного файла; расположение ключа или ключей в записи, их длина, тип и порядок старшинства; расположение и длины полей, которые необходимо передать в рассортированных записях; длина и структура рассортированных записей; точки входа и выхода, через которые пользователь, связывает свою подпрограмму с программой сортировки; коэффициенты блокирования записей; типы и количество внешних запоминающих устройств и томов, используемых при сортировке (если система не выбирает их сама); информация о метках; входные и выходные периферийные устройства (на которых данные располагаются до и после сортировки). После считывания и проверки управляющих карт, сгенерированная программа сортировки автоматически выполняет две фазы сортировки. Программист в этом не принимает никакого участия, а оператор должен только подготовить. К использованию требуемые периферийные устройства и тома. На рис. 9.23 изображена блок-схема обычного генератора программ сортировки/слияния. Так, например, программа сортировки слияния SM1 фирмы IBM использует минимум три магнитные ленты или один диск и может объединить до 16 файлов [25], Может быть задано не более 64 ключей, и бинарные ключи не обязательно должны начинаться с границы байта. Связь своих подпрограмм со сгенерированной программой сортировки пользователь может осуществить через 17 входных и выходных точек. Программа сама выбирает метод сортировки, лучше всего соответствующий объему доступной основной-памяти, количеству и типу периферийных устройств и объему сортируемых данных. Максимальная длина записи зависит от типа используемых периферийных устройств и объема основной памяти, выделенного программе сортировки, и изменяется от 11000 до 32000 байт. Программа осуществляет сбалансированную сортировку, если она может использовать более трех магнитных лент и объем входных данных не задан или подсчитан приблизительно. Доступный объем основной памяти при сбалансированной сортировке не может быть меньше 12К, а для промежуточного хранения данных допускается использование не более 32 магнитных лент. Если для промежуточного хранения выделено только три ленты, то программа автоматически выбирает более эффективный в данном случае метод многофазной сортировки. Минимальный объем основной памяти при этом методе также равен 12К. Наконец, при осциллирующей сортировке требуется минимум 21К основной памяти и максимум 17 лент для промежуточного хранения данных. Один из режимов сортировки с использованием диска требует минимум 13К основной памяти и работает максимум с шестью областями на диске, в то время как другие режимы требуют 24К основной памяти и обрабатывают До 17 областей на диске.