Сортировка записей в файле
Для работы большинства рассмотренных выше алгоритмов сортировки массивов требуется
произвольный доступ к элементам. Записи в файле обычно могут быть прочитаны лишь
в порядке их следования и перестановка двух записей невозможна. Пожалуй,
единственное исключение - файл записей фиксированной длины, размещенный на диске
(т.е. не на ленте), но и в этом случае надо учитывать, что смена дорожки на диске
происходит далеко не мгновенно, так что скорость произвольного доступа заметно
меньше скорости последовательного. В силу этих причин для сортировки файлов
используются алгоритмы, основанные на идее распределения/слияния. Они используют
только последовательный доступ к записям, но требуют наличия свободного пространства
на внешних носителях (что может быть обеспечено). Такой алгоритм (dSort) был
рассмотрен и он легко адаптируется для сортировки файлов. Он может быть улучшен
путем использования большего числа временных файлов (лент) и объединения циклов
распределения/слияния.
Все приведенные ниже примеры выполняют сортировку строк в текстовом файле (длина
строк в пределах от нуля до заданного максимального значения). Отсортированный
файл записывается на место исходного. Файлы сложнее массивов и для работы с ними
будет использован специальный класс CFile, в котором реализованы операции обмена
с диском и необходимые операции сравнения. Важно отметить, что в алгоритмах
распределения/слияния сравниваются только текущие записи из разных файлов и
текущая запись файла с предыдущей записью этого же файла. Эти сравнения помещены
в методы Comp и Skip:
<![CDATA[
struct CFile
...
void Init (char @name); // Инициализация
void Open (); // Откpытие для чтения
void Create(); // Откpытие для записи (создание)
int EOF (); // Пpовеpка достижения конца файла (0-нет)
int Comp (CFile @F); // Сpавнение с дpугим файлом
void Write (CFile @F); // Запись стpоки
int Skip (); // Чтение следующей стpоки (0-не конец сеpии)
void Close (); // Закpытие
end
]]>
После проверки EOF доступна одна строка файла. Она может сравниваться со строкой
другого файла (с помощью Comp) и записываться в выходной файл (с помощью Write).
Skip читает следующую строку и сравнивает ее с предыдущей. Если вновь прочитанная
строка должна помещаться в выходной файл после ранее прочитанной (она "больше"
предыдущей) - возвращается ноль, если нет (или если достигнут конец файла) - не ноль.
При рассмотрения алгоритммов сортировки детали реализации класса CFile не играют
никакой роли, будут использованы лишь перечисленные восемь методов. Полная реализация
класса приведена ниже. Поскольку используются классы, необходим
компилятор версии 1.2. В принципе возможна реализация того же самого без использования
классов. В этом случае CFile - обычная структура, все его методы - обычные функции,
но с дополнительным параметром - ссылкой на файл:
<![CDATA[
struct CFile
...
end
void Init(CFile @File; char @name)
...
end
...
]]>
Соответственно, вместо Data.Init(@name) нужно писать Init(@Data,@name).
В данном конкретном случае оба способа примерно эквивалентны, но выбран
вариант с использованием классов.
Во всех приведенных ниже примерах широко используются ссылки на экземпляры
классов. Возможно, это не очень хорошо, но пока так...
"Очевидная" реализация функции распределения/слияния сходна с dSort:
<![CDATA[
void fSort(char @name, @left, @right)
CFile Data;
CFile Left;
CFile Right;
Data .Init(@name);
Left .Init(@left);
Right.Init(@right);
repeat
Data .Open ();
Left .Create();
Right.Create();
word Dest=0;
while Data.EOF()=0 do
if Dest=0 then
Left .Write(@Data);
else
Right.Write(@Data);
end
if Data.Skip()!=0 then
Dest=(Dest+1)%2;
end
end
Right.Close();
Left .Close();
Data .Close();
Left .Open ();
Right.Open ();
Data .Create();
word Flag=0;
while Left.EOF()=0 & Right.EOF()=0 do
CFile @F0, @F1;
if Left.Comp(@Right)<=0 then
@F0=@Left;
@F1=@Right;
else
@F0=@Right;
@F1=@Left;
end
Data.Write(@F0);
if F0.Skip()!=0 then
repeat
Data.Write(@F1);
until F1.Skip()!=0;
if F0.EOF()=0 | F1.EOF()=0 then
Flag=1;
end
end
end
while Left.EOF()=0 do
Data .Write(@Left);
Left .Skip ();
end
while Right.EOF()=0 do
Data .Write(@Right);
Right.Skip ();
end
Data .Close();
Right.Close();
Left .Close();
//putc('.');
until Flag=0;
end
]]>
После первого прохода в файле образуются упорядоченные цепочки длиной не менее двух,
после второго - длиной не менее четырех и так далее, пока файл не будет состоять
из одной упорядоченной цепочки. Таким образом, число проходов не превысит [Log2(N)+1],
время одного прохода примерно пропорционально N, общее время ~N*Log(N).
За счет увеличения числа временных файлов можно сократить число проходов:
<![CDATA[
void nSort(char @name, @temp; CFile @Temp; word nFile)
char @Char="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ@#$%";
CFile @Data=@Temp[nFile];
Data.Init(@name);
int W=0;
while temp[W]!='?' do
inc W;
end
int I=0;
while I<nFile do
temp[W]=Char[I];
Temp[I].Init(@temp);
inc I;
end
repeat
Data.Open();
I=0;
while I<nFile do
Temp[I].Create();
inc I;
end
word Dest=0;
while Data.EOF()=0 do
Temp[Dest].Write(@Data);
if Data.Skip()!=0 then
Dest=(Dest+1)%nFile;
end
end
I=nFile;
while I>0 do
dec I;
Temp[I].Close();
end
Data.Close();
I=0;
while I<nFile do
Temp[I].Open();
inc I;
end
Data.Create();
word Flag=0;
while TRUE do
CFile @P[64];
word N;
I=0;
N=0;
while I<nFile do
if Temp[I].EOF()=0 then
int J=0;
while J<N do
if Temp[I].Comp(@P[J])<0 then
exit
end
inc J;
end
int K=N;
while K>J do
@P [K]=@P [K-1];
dec K;
end
@P [K]=@Temp[I];
inc N;
end
inc I;
end
if N=0 then
exit
end
while N>0 do
Data.Write(@P[0]);
if P[0].Skip()=0 then
I=1;
while I<N do
if P[0].Comp(@P[I])<=0 then
exit
end
inc I;
end
CFile @T=@P[0];
int J=0;
while J<I-1 do
@P [J]=@P [J+1];
inc J;
end
@P[J]=@T;
loop
end
if P[0].EOF()=0 then
Flag=1;
end
I=0;
while I+1<N do
@P [I]=@P [I+1];
inc I;
end
dec N;
end
end
Data.Close();
I=nFile;
while I>0 do
dec I;
Temp[I].Close();
end
//putc('.');
until Flag=0;
end
]]>
Время одного прохода при этом увеличивается, т.к. требуется больше сравнений, но
число проходов уменьшается. После первого прохода образуются упорядоченные цепочки
длиной не менее nFile, после второго - nFile*nFile и так далее. Таким образом
nFile - новое основание логарифма в формуле расчета числа проходов.
Наконец, можно объединить циклы распределения/слияния:
<![CDATA[
void xSort(char @name, @temp; CFile @Temp; word nFile)
char @Char="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ@#$%";
int W=0;
while temp[W]!='?' do
inc W;
end
int I=0;
while I+1<2*nFile do
temp[W]=Char[I];
Temp[I].Init(@temp);
inc I;
end
CFile @Src=@Temp[I];
CFile @Dst=@Temp;
Src.Init(@name);
Src.Open();
I=0;
while I<nFile do
Dst[I].Create();
inc I;
end
word Dest=0;
while Src.EOF()=0 do
Dst[Dest].Write(@Src);
if Src.Skip()!=0 then
Dest=(Dest+1)%nFile;
end
end
I=nFile;
while I>0 do
dec I;
Dst[I].Close();
end
Src.Close();
word Swap=0;
repeat
word Flag=Swap;
if Swap=0 then
@Src=@Temp[0];
@Dst=@Temp[nFile];
Dest=nFile-1;
else
@Src=@Temp[nFile];
@Dst=@Temp[0];
Dest=0;
end
word Comp=Dest;
I=0;
while I<nFile do
Src[I].Open ();
inc I;
end
I=0;
while I<nFile do
Dst[I].Create();
inc I;
end
while TRUE do
CFile @P[64];
int N;
I=0;
N=0;
while I<nFile do
if Src[I].EOF()=0 then
int J=0;
while J<N do
if Src[I].Comp(@P[J])<0 then
exit
end
inc J;
end
int K=N;
while K>J do
@P [K]=@P [K-1];
dec K;
end
@P [K]=@Src[I];
inc N;
end
inc I;
end
if N=0 then
exit
end
while N>0 do
Dst[Dest].Write(@P[0]);
if P[0].Skip()=0 then
I=1;
while I<N do
if P[0].Comp(@P[I])<=0 then
exit
end
inc I;
end
CFile @T=@P[0];
int J=0;
while J<I-1 do
@P [J]=@P [J+1];
inc J;
end
@P[J]=@T;
loop
end
I=0;
while I+1<N do
@P [I]=@P [I+1];
inc I;
end
dec N;
end
if Dest!=Comp then
Flag=1;
end
Dest=(Dest+1)%nFile;
end
I=nFile;
while I>0 do
dec I;
Dst[I].Close();
end
I=nFile;
while I>0 do
dec I;
Src[I].Close();
end
//putc('.');
Swap=(Swap+1)%2;
until Flag=0;
end
]]>
Существуют и еще лучшие алгоритмы, например алгоритм многофазной сортировки
(R.L. Gilstad, 1960), основанный на несимметричном распределении записей
исходного файла по лентам. Этот алгоритм не столь очевиден, как предыдущие,
вот его упрощенная версия (используются два временных файла):
<![CDATA[
void pSort(char @name, @left, @right)
CFile Data;
CFile Left;
CFile Right;
Data .Init(@name);
Left .Init(@left);
Right.Init(@right);
Data .Temp=0;
Left .Temp=1;
Right.Temp=1;
//--------------------------------
Data .Open ();
Left .Create();
Right.Create();
Left .Lock=0;
Right.Lock=0;
Left .Swap=0;
Right.Swap=0;
Left .N =1;
Right.N =1;
word Pred =1;
word Fib =1;
while Data.EOF()=0 do
if Left.N=0 & Right.N=0 then
Left .N=Pred;
Right.N=Fib-Pred;
Pred =Fib;
Fib =Fib+Left.N;
end
CFile @P=@Left;
if Left.N<Right.N then
@P=@Right;
end
if P.Lock!=0 then
if P.Comp(@Data)>0 then
dec P.N;
end
else
dec P.N;
end
repeat
P.Write(@Data);
until Data.Skip()!=0;
P.Line()=Data.Pred();
P.Lock =1;
end
Right.Close ();
Left .Close ();
Data .Close ();
CFile @L=@Left;
CFile @R=@Right;
CFile @D=@Data;
//--------------------------------
L.Open ();
R.Open ();
D.Create();
while TRUE do
if R.N<L.N then
CFile @T=@L;
@L=@R;
@R=@T;
end
while R.N>L.N do
if L.EOF()=0 then
repeat
D.Write(@L);
until L.Skip()!=0;
end
dec R.N;
end
while L.EOF()=0 & R.EOF()=0 do
CFile @P0=@L;
CFile @P1=@R;
if L.Comp(@R)>0 then
@P0=@R;
@P1=@L;
end
D.Write(@P0);
if P0.Skip()!=0 then
repeat
D.Write(@P1);
until P1.Skip()!=0;
end
end
//putc('.');
if L.EOF()!=0 & R.EOF()!=0 then
if D.Temp=0 then
exit
end
if L.Temp=0 then
CFile @T=@L;
@L=@R;
@R=@T;
end
D.N=0;
L.N=1;
else
if L.EOF()!=0 then
CFile @T=@L;
@L=@R;
@R=@T;
end
D.N=L.N;
L.N=0;
end
D.Close();
R.Close();
CFile @T=@D;
@D=@R;
@R=@T;
R.Open ();
D.Create();
end
D.Close ();
R.Close ();
L.Close ();
end
]]>
Здесь один раз выполняется распределение серий из исходного файла (в пропорции
двух соседних чисел Фибоначчи), затем выполняется многократное слияние. Само
название алгоритма "многофазная сортировка" можно понимать как много фаз слияния,
хотя абсолютной уверенности в правильности этого нет.
Если число упрорядоченных серий в исходном файле не равно числу Фибоначчи,
временные файлы дополняются пустыми сериями. Также учтено, что при распределении
две несмежные серии могут слиться в одну (пример: 10,20;15,30;25,35;). Вот как
выполняется сортировка файла, содержащего 22 серии:
|
22x1
|
v
|
v
|
|
v
|
7x0+14x1
|
5x0+8x1
|
|
5x0+2x1+6x2
|
8x1
|
v
|
|
5x2
|
v
|
5x1+2x2+1x3
|
|
v
|
5x3
|
2x2+1x3
|
|
2x5+1x6
|
2x3
|
v
|
|
1x6
|
v
|
2x8
|
|
v
|
1x14
|
1x8
|
|
1x22
|
-
|
-
|
Циклов выполняется на два больше, чем при слиянии на двух парах лент (xSort), но эти
циклы более короткие.
В принципе можно не выполнять начальное распределение серий, но считать число
серий в исходном файле все равно нужно. Время работы так измененного алгоритма
немного больше, единственный плюс - не нужно думать о слиянии несмежных серий:
<![CDATA[
//--------------------------------
Data .Open ();
word Pred =1;
word Fib =1;
Data.N=0;
while Data.EOF()=0 do
repeat
until Data.Skip()!=0;
inc Data.N;
if Data.N>Fib then
word Temp=Fib;
Fib =Fib+Pred;
Pred=Temp;
end
end
Data .Close ();
Left .Create();
Left .Close ();
Data .N=Fib-Data.N;
Left .N=Pred;
CFile @L=@Data;
CFile @R=@Left;
CFile @D=@Right;
//--------------------------------
]]>
Для корректной работы примеров необходимо задать достаточное количество
дескрипторов файлов (т.е. установить параметр FILES в CONFIG.SYS/CONFIG.NT),
а также явно запросить их использование с помощью функции DOS 67H:
<![CDATA[
//Сортировка строк в текстовом файле TXTSORT.TXT
//CONFIG.SYS/CONFIG.NT:
//FILES=40
begin
asm mov AH,67H
asm mov BX,35
asm int 21H
CFile Temp [32];
fSort("TXTSORT.TXT","TXTSORT.001","TXTSORT.002");
//nSort("TXTSORT.TXT","TXTSORT.00?",@Temp,8);
//xSort("TXTSORT.TXT","TXTSORT.00?",@Temp,8);
//pSort("TXTSORT.TXT","TXTSORT.001","TXTSORT.002");
end
]]>
И последнее замечание. Хотя в приведенных функциях сортировки (в nSort и xSort)
явно не используются какие-либо сведения об устройстве файлов, независимость от
этого устройства не достигнута. Даже если сделать методы класса CFile виртуальными,
при реализации сравнения (CFile.Comp) и записи (CFile.Write) потребуется явное
преобразование типа. В данном случае оно совершенно безопасно, все же лучшим
решением является использование шаблонов.
Реализация класса CFile:
<![CDATA[
define bfSIZE 1024
define lnSIZE 256
struct CLine
char Buff [lnSIZE]; // Строка
int nChar; // Длина строки
int Comp(CLine @L); // Функция сравнения
end
struct CFile
char Buff [bfSIZE]; // Буфеp
int nChar; // Число символов в буфеpе
int pChar; // Указатель на текущий символ
char Name [13]; // Имя файла
word File; // Дескpиптоp файла
word Mode; // Pежим (1-чтение, 2-запись)
int Flag; // 1-конец файла
int Lock; // Данные пpочитаны?
word Swap; // Текущая стpока (0-Line1, 1-Line2)
word Temp; // 0-исходный файл, 1-вpеменный файл
word N; // Число пустых сеpий (для pSort)
CLine Line1;
CLine Line2;
CLine @Line (); // Ссылка на текущую стpоку
CLine @Pred (); // Ссылка на пpедыдущую стpоку
void Save (char Ch); // Запись символа
void Init (char @name); // Инициализация
void Open (); // Откpытие для чтения
void Create(); // Откpытие для записи (создание)
int EOF (); // Пpовеpка достижения конца файла (0-нет)
int Comp (CFile @F); // Сpавнение с дpугим файлом
void Write (CFile @F); // Запись стpоки
int Skip (); // Чтение следующей стpоки (0-не конец сеpии)
void Close (); // Закpытие
end
// Очередное повторение функций для работы с файлами
word creat(char @Name)
asm push DS
asm mov AH,3CH
asm mov CX,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word open(char @Name)
asm push DS
asm mov AH,3DH
asm mov AL,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word read(word F; void @Buff; word N)
asm push DS
asm mov AH,3FH
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
word write(word F; void @Buff; word N)
asm push DS
asm mov AH,40H
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
void close(word F)
asm mov AH,3EH
asm mov BX,SS:[BP+4]
asm int 21H
end
int CLine.Comp(CLine @L)
int M= nChar;
int N=L.nChar;
int I=0;
while I<M & I<N do
if Buff[I]<L.Buff[I] then
return -1;
end
if Buff[I]>L.Buff[I] then
return 1;
end
inc I;
end
if M<N then
return -1;
end
if M>N then
return 1;
end
return 0;
end
CLine @CFile.Line()
if Swap=0 then
return @Line1;
else
return @Line2;
end
end
CLine @CFile.Pred()
if Swap=0 then
return @Line2;
else
return @Line1;
end
end
void CFile.Save(char Ch)
if !(nChar<bfSIZE) then
write(File,@Buff,nChar);
nChar=0;
end
Buff[nChar]=Ch;
inc nChar;
end
void CFile.Init(char @name)
int I=0;
while name[I]!=#0 do
Name[I]=name[I];
inc I;
end
Name[I]=#0;
end
void CFile.Open()
File =open (@Name);
Mode =1;
nChar=0;
pChar=0;
Flag =0;
Lock =0;
Swap =0;
end
void CFile.Create()
File =creat(@Name);
Mode =2;
nChar=0;
end
int CFile.EOF()
if Lock!=0 then
return 0;
end
if Flag!=0 then
return 1;
end
CLine @Line=@Line();
int P=pChar;
int N=nChar;
int I=0;
while I<lnSIZE do
if P>=N then
N=read(File,@Buff,bfSIZE);
P=0;
if N=0 then
Flag=1;
if I=0 then
return 1;
end
exit
end
end
char Ch=Buff[P];
select
case Ch=#10:
inc P;
exit
case Ch!=#13:
Line.Buff[I]=Ch;
inc I;
end
inc P;
end
Line.nChar=I;
pChar =P;
nChar =N;
Lock =1;
return 0;
end
int CFile.Comp(CFile @F)
return Line().Comp(@F.Line());
end
void CFile.Write(CFile @F)
CLine @Line=@F.Line();
int N=nChar;
int L=Line.nChar;
int I=0;
while I<L do
if N>=bfSIZE then
write(File,@Buff,N);
N=0;
end
Buff[N]=Line.Buff[I];
inc N;
inc I;
end
nChar=N;
Save(#13);
Save(#10);
end
int CFile.Skip()
Swap=(Swap+1)%2;
Lock= 0;
if EOF()!=0 then
return 1;
end
if Line().Comp(@Pred())<0 then
return 1;
end
return 0;
end
void CFile.Close()
if Mode=2 then
if nChar>0 then
write(File,@Buff,nChar);
end
end
close(File);
end
]]>
Сайт создан в системе
uCoz