|
Страница 16 из 60
Сортировка последовательных файлов
В отличие от файлов с прямым доступом последовательные файлы
обычно не используют записи фиксированной длины и могут разме-
щаться на устройствах памяти, на которых трудно организовать пря-
мой доступ. Поэтому последовательные файлы на дисках используются
в тех случаях, когда для решения конкретной задачи удобнее ис-
пользовать записи переменной длины или когда устройство памяти
ориентировано на последовательный доступ. Например, большинство
текстовых файлов имеют последовательную организацию.
Несмотря на то, что такой подход к сортировке, когда диско-
вый файл рассматривается как массив, имеет ряд преимуществ, его
нельзя применить к последовательным файлам - быстрый доступ к
произвольному элементу в этом случае невозможен. Например, нельзя
быстро прочитать произвольную запись из последовательного файла,
расположенного на магнитной ленте. По этой причине возникают
трудности по применению любого ранее описанного метода сортировки
массивов к сортировке последовательных файлов.
Имеется два подхода к сортировке последовательных файлов.
Первый подход предусматривает считывание информации в оперативную
память и сортировку при помощи одного из стандартных методов сор-
тировки массивов. Несмотря на то, что при таком подходе сортиров-
ка будет выполняться быстро, размеры оперативной памяти наклады-
вают сильное ограничение на размер сортируемого файла.
При использовании второго подхода, получившего название сор-
тировки слиянием, весь файл делиться на две равные части. В про-
цессе сортировки из каждого файла считывается по одному элементу,
эта пара элементов упорядочивается и делается запись элементов в
третий файл, расположенный на диске. Новый файл затем снова де-
лится на два файла и упорядоченные пары элементов объединяются в
упорядоченные группы элементов по четыре элемента в каждой. Затем
полученный файл снова разделяется на два файла и вся процедура
повторяется до тех пор, пока файл не будет отсортирован. Эту сор-
тировку-слияние называют трехленточным слиянием, поскольку в этом
случае одновременно требуется иметь три файла /т.е. три накопите-
ля на магнитной ленте, если файл располагается на ленте/.
Для того, чтобы лучше понять работу сортировки-слияние,
рассмотрим следующую последовательность числе:
1 4 3 8 6 7 2 5.
В результате разбиения получаться следующие последователь-
ности:
1 4 3 8
6 7 2 5.
Затем производится слияние пар элементов:
1 6 - 4 7 - 2 3 - 5 8.
Новое разбиение дает следующие последовательности:
1 6 - 4 7
2 3 - 5 8.
Результат следующего слияния:
1 2 3 6 - 4 5 7 8.
Последнее разбиение будет следующим:
1 2 3 6
4 5 7 8.
И в результате получаем:
1 2 3 4 5 6 7 8.
При сортировке методом слияния, как возможно вы уже замети-
ли, требуется выполнить log n операций доступа к каждому файлу,
где "n" является числом сортируемых элементов.
Ниже дается простая версия алгоритма сортировки методом сли-
яния. Предполагается, что размер входного файла в два раза превы-
шает объем содержащейся в нем информации. Поэтому в действтитель-
ности требуется иметь лишь один файл. Однако, по-существу, метод
сортировки слиянием не изменяется. В этом примере данное
"filtype" определяется как файл типа "DataItem". Функция "Find"
используется для считывания конкретной записи из файла.
{ функция "Find" используется в сортировке методом
слияния для считывания из файла конкретной записи.}
function Find(var fp:filtype; i:integer):DataItem;
var
t:DataItem;
begin
Seek(fp, i-1);
Read(fp, t);
Find := t;
end;
procedure Mergesort(var fp: filetype; count:integer);
var
i, j, k, l, t, h, m, p, q, r: integer;
ch1, ch2:DataItem
up: Boolean;
begin
up := TRUE;
p := 1;
repeat
h := 1; m := count;
if up then
begin
i := 1; j := count; k := count+1; l := 2*count;
end else
begin
k := 1; l := count; i := count+1; j := 2*count;
end;
repeat
if m>=p then q := p else q := m;
m := m-q;
if m>=p then r := p else r := m;
m := m-r;
while (q<>0) and (r<>0) do
begin
if Find(fp,i) < Find(fp,j) then
begin
Seek(fp, i-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; i := i+1; q := q-1;
end else
begin
Seek(fp, j-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; j := j-1; r := r-1;
end;
end;
while r<>0 do
begin
Seek(fp, j-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; j := j-1; r := r-1;
end;
while q<>0 do
begin
Seek(fp, i-1); Read(fp,ch2);
Seek(fp, k-1); Write(fp,ch2);
k := k+h; i := i+1; q := q-1;
end;
h := -1; t := k;
k := l;
l := t;
until m = 0:
up := not up;
p := p*2;
until p >= count;
if not up then
for i := 1 to count do
begin
Seek(fp, i-1+count); Read(fp,ch2);
Seek(fp, i-1); Write(fp,ch2);
end;
end; { кoнец сортировки методом слияния }
|