Сортировка записей в файле

Для работы большинства рассмотренных выше алгоритмов сортировки массивов требуется произвольный доступ к элементам. Записи в файле обычно могут быть прочитаны лишь в порядке их следования и перестановка двух записей невозможна. Пожалуй, единственное исключение - файл записей фиксированной длины, размещенный на диске (т.е. не на ленте), но и в этом случае надо учитывать, что смена дорожки на диске происходит далеко не мгновенно, так что скорость произвольного доступа заметно меньше скорости последовательного. В силу этих причин для сортировки файлов используются алгоритмы, основанные на идее распределения/слияния. Они используют только последовательный доступ к записям, но требуют наличия свободного пространства на внешних носителях (что может быть обеспечено). Такой алгоритм (dSort) был рассмотрен и он легко адаптируется для сортировки файлов. Он может быть улучшен путем использования большего числа временных файлов (лент) и объединения циклов распределения/слияния.

Все приведенные ниже примеры выполняют сортировку строк в текстовом файле (длина строк в пределах от нуля до заданного максимального значения). Отсортированный файл записывается на место исходного. Файлы сложнее массивов и для работы с ними будет использован специальный класс CFile, в котором реализованы операции обмена с диском и необходимые операции сравнения. Важно отметить, что в алгоритмах распределения/слияния сравниваются только текущие записи из разных файлов и текущая запись файла с предыдущей записью этого же файла. Эти сравнения помещены в методы Comp и Skip:

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 - обычная структура, все его методы - обычные функции, но с дополнительным параметром - ссылкой на файл:

struct CFile ... end void Init(CFile @File; char @name) ... end ... Соответственно, вместо Data.Init(@name) нужно писать Init(@Data,@name). В данном конкретном случае оба способа примерно эквивалентны, но выбран вариант с использованием классов.

Во всех приведенных ниже примерах широко используются ссылки на экземпляры классов. Возможно, это не очень хорошо, но пока так...

"Очевидная" реализация функции распределения/слияния сходна с dSort:

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).

За счет увеличения числа временных файлов можно сократить число проходов:

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 - новое основание логарифма в формуле расчета числа проходов.

Наконец, можно объединить циклы распределения/слияния:

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), основанный на несимметричном распределении записей исходного файла по лентам. Этот алгоритм не столь очевиден, как предыдущие, вот его упрощенная версия (используются два временных файла):

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), но эти циклы более короткие.

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

//-------------------------------- 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:

//Сортировка строк в текстовом файле 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:

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