Cтраница 2
Алгоритм сортировки информации методом слияния ключевых признаков на машине с четырьмя блоками состоит из: алгоритма предварительного упорядочения исходной информации в оперативной памяти машины; алгоритма распределения и записи предварительно упорядоченной информации на три магнитные ленты и алгоритма слияния предварительно упорядоченной информации с трех магнитных лент на одну. [16]
На этапе построения отрезков мы читаем по одному блоку данных на отрезок, что дает R операций чтения блоков. При каждом проходе алгоритма слияния мы будем читать все данные; это означает, что на каждом проходе будет читаться N / ( S / 2) - 2Д блоков. [17]
В определении однозначности говорится, что для двух перекрывающихся и неоднозначных образцов каждый образец, уничтожающий эту неоднозначность, должен быть специализацией обоих и соответствовать каждому аргументу, которому соответствуют оба этих образца. Несмотря на то что алгоритм слияния проводит проверку на специализацию, объясните, почему нет необходимости проверять перекрываемость образцов. [18]
Одно из важных свойств программы 8.1 заключается в том, что реализуемое ею слияние устойчиво: она сохраняет относительный порядок элементов с одинаковыми ключами. Это обстоятельство еще больше усложняет проблему разработки истинного алгоритма обменного слияния. [19]
Существование алгоритма слияния, не требующего резервных объемов памяти, очевидно для случая, когда размер меньшего из двух сливаемых массивов равен единице. Из сказанного выше по индукции следует, что алгоритм слияния, не использующий резервных объемов памяти, существует при произвольных размерах сливаемых массивов. Оператор слияния, не использующий резервных объемов памяти, представляет собой рекурсивную процедуру, описание которой непосредственно вытекает из доказательства существования алгоритма. [20]
Здесь желательно на какое-то время остановиться и подумать о том, как можно все это сделать. На первый взгляд кажется, что у этой проблемы есть простое решение, однако на самом деле все известные до сих пор решения достаточно сложные, особенно если их сравнить с программой 8.1. И в самом деле, довольно трудно разработать алгоритм обменного слияния, т.е. в рамках пространства памяти, занимаемого входными файлами, который обладал бы лучшими характеристиками и который мог бы стать альтернативой обменной сортировке. [21]
Корректировка на месте выполняется быстрее, чем полное слияние, и не требует создания нового файла. Корректировка на месте выполняется с использованием алгоритма слияния, подобного рассмотренному, только вместо цепочек вставки записи и удаления, а также цепочек перемещения оставшихся записей корректировки ( метка КО) программируются цепочки блокировки и сигнализации соответствующих типов ошибок. [22]
Формируется файл с постоянной или переменной длиной записи, причем результативная запись получается из нескольких перфокарт различных форматов, представленных различными первичными файлами. В соответствии с каждым исходным форматом создается согласно обычной технологии обработки данных необходимое число последовательных файлов. Затем они объединяются отдельной программой с использованием алгоритма слияния двух или более последовательностей. Параллельно контролируются совместимость и полнота данных. [23]
Если условия равного распределения серий больше не существует, то процедуру слияния следует изменить: после достижения конца одного из файлов нужно копировать не одну серию, а всю оставшуюся часть другого. Это приводит к четким и очень простым по сравнению с модификацией процедуры распределения изменениям. Читатель может сам убедиться в справедливости такого утверждения. Пере смотренная версия алгоритма слияния включена в уже полную прогр. [24]
Слияние на рис. 9.14 помещает вторую строку ( 22) в конце области вывода. Эта строка строится не вниз от некоторой точки, вычисленной по таблице описания строк, а вверх от последней позиции. Это самый простой снисиб размещения сгрики, длина которой неизвестна. Для последующих просмотров алгоритма простого слияния возрастающие строки размещаются с головы списка, а убывающие ( возрастающие снизу вверх) - с хвоста. [25]
Распределение строк на ленте при любой схеме слияния заданной степени включает выбор устройств ввода-вывода для получения строк в соответствии с назначениями данного слияния. Есть два основных типа алгоритмов - сбалансированные и несбалансированные. Несбалансированное распределение размещает строки так, чтобы достичь идеального уровня. Понятие идеальных уровней будет описано в связи с каждым типом несбалансированного слияния; в общем случае, идеальный уровень - это такое распределение строк, которое позволит несбалансированному слиянию работать без изменения алгоритма слияния от просмотра к просмотру. [26]