Подфайл

Cтраница 2

На рис. 12.1 показаны подфайлы, исследуемые в ходе бинарного поиска в небольшой таблице; на рис. 12.2 приведен больший пример. В ходе каждой итерации отбрасывается несколько больше половины таблицы, поэтому количество требуемых итераций мало. [16]

Как уже отмечалось, подфайл состоит из двух частей: собственно подсписка и ячеек в области переполнения, которые связаны с данным подфайлом. В случае неупорядоченного подфайла безразлично, куда включается новая запись. Если имеется свободное место в подсписке, запись размещается в подсписке. Если же последний заполнен, то в области переполнения выделяется новая ячейка и запись помещается в нее. Чтобы запись оставалась связанной с подфайлом, ее необходимо поместить в его цепочку переполнения, причем место расположения этой записи опять не имеет значения. Таким образом, необходимо выполнить простей шую операцию - - найти цепочку переполнения, принадлежащую данному подфайлу. Содержащая новую запись ячейка может помещаться в начало, конец или любое другое место цепочки, что определяется удобством реализации. [17]

Заметьте, что все подфайлы имеют один и тот же тип. [18]

Предположим, что в первом подфайле содержатся / нулей и j нулей во втором подфайле. Доказательство этой леммы требует рассмотрения четырех случаев в зависимости от того, являются ли / и j четными или нечетными числами. Если обе переменные имеют четные значения, то две подзадачи слияния выполняется над двумя файлами, при этом один файл содержит / / 2 нулей, а другой файл - j / 2 нулей, так что в обоих случаях получившийся при слиянии файл содержит ( i j) / 2 нулей. Файл типа 0 - 1 подвергается тасованию и в тех случаях, когда / - четное, a j - нечетное число, а также когда / - нечетное, a j - четное число. Но если оба / и j - нечетные числа, то мы завершаем эту процедуру тем, что тасуем файл, содержащий ( / у) / 2 1 нулей с файлом, содержащим ( / у) / 2 - 1 нулей, следовательно, полученный после тасования файл содержит / у - 1 нулей, единицу, ноль и N - i - j - 1 единиц ( см. рис. 11.3), и один из компараторов на завершающей стадии заканчивает сортировку. [19]

В этом бинарном дереве каждый подфайл представлен своим разделяющим элементом ( или самим собой, если он имеет размер 1), и поддеревья каждого узла суть деревья, представляющие подфайлы после разделения. Дабы не загромождать рисунок, нулевые подфайлы на нем не показаны, хотя наши рекурсивные версии алгоритма выполняют рекурсивные вызовы при выполнении условия г1, когда разделяющим элементом становится наименьший или наибольший элемент файла. Само по себе дерево не зависит от очередности, в которой подфайлы подвергаются разделению. Наша рекурсивная реализация сортировки соответствует посещению узлов при их обходе в прямом порядке, а нерекурсивная реализация соответствует правилу посещения сначала наименьшего дерева. [20]

Слияние файлов, состоящих из упорядоченных подфайлов. [21]

Они называются пороговыми и отделяют упорядоченные подфайлы в файле. Если ключ очередной записи меньше предыдущего, значит, эта очередная запись является пороговой. [22]

Добавление, новой записи в подфайл подсписка nL затрагивает область переполнения, если в этом подсписке все ячейки исчерпаны. [23]

ДИНАМИЧЕСКИЕ ХАРАКТЕРИСТИКИ ДВОИЧНОЙ БЫСТРОЙ СОРТИРОВКИ НА КРУПНОМ ФАЙЛЕ Разбиения на части при двоичной быстрой сортировке менее чувствительны к порядку расположения ключи, чем в условиях стандартной быстрой сортировки. В рассматриваемом случае выполнение этой процедуры на двух различных 8-разрядный файлах с произвольной организацией приводят к практически идентичным профилям разделений. [24]

Почему сортировка меньшего из двух подфайлов первым менее важна в случае двоичной быстрой сортировки, чем в случае обычной быстрой сортировки. [25]

Другими словами, в процессе разделения небольшие подфайлы просто игнорируются. [26]

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

Лемма 7.3. Если меньший из двух подфайлов сортируется первым, то стек никогда не содержит более IgN вхождений в случаях, когда для сортировки N файлов применяется быстрая сортировка. [28]

Процесс выборки предусматривает разбиение на разделы подфайла, который содержит искомый элемент, перемещение левого указателя вправо или правого указателя влево в зависимости от того, где окажется точка раздела. [29]

Аналогично сортировка продолжается и на втором подфайле, и так далее, пока файл не от-сортируется по всему ключу. [30]

Страницы: 1 2 3 4 5