Сортировка дисковых файлов
Имеется два типа дисковых файлов: файлы с последовательным доступом и файлы с произвольным доступом. Если файл достаточно небольшой, то он может быть считан в оперативную память и тогда могут использоваться для наиболее эффективной сортировки те прог- раммы, которые рассматривались ранее для сортировки массивов. Од- нако многие дисковые файлы имеют слишком большой размер и не мо- гут просто считываться в оперативную память для сортировки. Для этого требуется применить специальные методы.
Сортировка дисковых файлов произвольного доступа
Дисковые файлы с произвольным доступом, которые используются в большинстве баз данных на микро-ЭВМ, обладают двумя основными преимуществами над последовательными дисковыми файлами. Во-пер- вых, их легко поддерживать. Обновление информации может произво- диться без копирования всего списка. Во-вторых, их можно рассмат- ривать как большие массивы, расположенные на диске, что в значительной мере упрощает сортировку.
Последнее преимущество позволяет использовать алгоритм быст- рой сортировки в некоторыми его модификациями для поиска различ- ных записей на диске аналогично индексированию массива. В отличие от сортировки последовательного файла при сортировке дискового файла с произвольным доступом не требуется иметь на диске прост- ранство одновременно как для отсортированного, так и для неотсор- тированного массива.
В каждом конкретном случае алгоритм сортировки должен моди- фицироваться в соответствии со структурой сортируемых данных и выбранным ключом сортировки. Однако основные принципы сортировки дисковых файлов произвольного доступа можно понять, изучая прог- рамму сортировки записей с адресами почтовых корреспонденций /за- пись "address" определялась раньше/. В приводимом ниже примере, предполагается, что число элементов фиксированно и равно восьми- десяти. На практике счетчик записей должен поддерживаться динами- чески
{ пример программы сортировки списка почтовых адресов }programm MlistSort;
type
address = record
name: string[30];
street: string[40];
sity: string[20];
state: string[2];
zip: string[9];
end;
str80 = string[80];
DataItem = addres;
DataArray = array [1..80] of DataItem
recfil = file of DataItem
var
test: DataItem;
t, t2:integer;
testfile: recfil;
{ найти запись в файле }
function Find(var fp:recfil; i:integer): str80
var
t:address;
begin
i := i-1;
Seek(fp, i)
Read(fp, t)
Find := t.name;
end;
procedure QsRand(var var fp:recfil; count:integer)
procedure Qs(l, r:integer)
var i, j, s:integer ;
x, y, z:DataItem;
begin
i := l; j := r;
s := (l+r) div 2;
Seek(fp,s-1); { получить запись }
Reed(fp,x); repeat
while Find(fp, i) < x.name do i := i+1;
while x.name < Find(fp, j) do j := j-1;
if i<=j then
begin
Seek(fp,i-1); Reed(fp,y);
Seek(fp,j-1); Reed(fp,z);
Seek(fp,j-1); Write(fp,y);
Seek(fp,i-1); Write(fp,z);
i := i+1; j := j-1;
end;
until i>y;
if l
begin
qs(1,count);
end; { конец быстрой сортировки файла произвольного
доступа }
begin
Assign(testfile, 'rectest.dat');
Reset(testfile);
t := 1;
while not EOF(testfile) do begin
Read(testfile,test); { подсчет числа записей в
файле}
t := t+1;
end;
t := t-1;
QsRand(testfile,t)
end.
Функция Find используется для того, чтобы оставить в основ- ном неизменным программу быстрой сортировки. Результатом этой функции является символьная строка "name" из записи, расположен- ной на диске. Необходимо постоянно вычитать единицу из аргументов функций Seek и Find, так как записи дискового файла нумеруются начиная с нуля, а массивы нумеруются с единицы.
Сортировка последовательных файлов
В отличие от файлов с прямым доступом последовательные файлы обычно не используют записи фиксированной длины и могут разме- щаться на устройствах памяти, на которых трудно организовать пря- мой доступ. Поэтому последовательные файлы на дисках используются в тех случаях, когда для решения конкретной задачи удобнее ис- пользовать записи переменной длины или когда устройство памяти ориентировано на последовательный доступ. Например, большинство текстовых файлов имеют последовательную организацию.
Несмотря на то, что такой подход к сортировке, когда диско- вый файл рассматривается как массив, имеет ряд преимуществ, его нельзя применить к последовательным файлам - быстрый доступ к произвольному элементу в этом случае невозможен. Например, нельзя быстро прочитать произвольную запись из последовательного файла, расположенного на магнитной ленте. По этой причине возникают трудности по применению любого ранее описанного метода сортировки массивов к сортировке последовательных файлов.
Имеется два подхода к сортировке последовательных файлов. Первый подход предусматривает считывание информации в оперативную память и сортировку при помощи одного из стандартных методов сор- тировки массивов. Несмотря на то, что при таком подходе сортиров- ка будет выполняться быстро, размеры оперативной памяти наклады- вают сильное ограничение на размер сортируемого файла.
При использовании второго подхода, получившего название сор- тировки слиянием, весь файл делиться на две равные части. В про- цессе сортировки из каждого файла считывается по одному элементу, эта пара элементов упорядочивается и делается запись элементов в третий файл, расположенный на диске. Новый файл затем снова де- лится на два файла и упорядоченные пары элементов объединяются в упорядоченные группы элементов по четыре элемента в каждой. Затем полученный файл снова разделяется на два файла и вся процедура повторяется до тех пор, пока файл не будет отсортирован. Эту сор- тировку-слияние называют трехленточным слиянием, поскольку в этом случае одновременно требуется иметь три файла /т.е. три накопите- ля на магнитной ленте, если файл располагается на ленте/
.Для того, чтобы лучше понять работу сортировки-слияние, рассмотрим следующую последовательность числе:
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 Энциклопедия по Турбо-Паскалю ч.1 = 28 = 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нец сортировки методом слияния }
