Энциклопедия Turbo Pascal. Главы 1-4 - Сортировка последовательных файлов

ОГЛАВЛЕНИЕ

Сортировка последовательных файлов

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

Несмотря на то,  что такой подход к сортировке, когда дисковый файл рассматривается как массив,  имеет ряд преимуществ,  его нельзя применить к последовательным файлам  -  быстрый доступ к произвольному элементу в этом случае невозможен. Например, нельзя быстро прочитать произвольную запись из последовательного файла, расположенного на магнитной ленте.  По этой причине возникают трудности по применению любого ранее описанного метода сортировки массивов к сортировке последовательных файлов.

Имеется два подхода к сортировке последовательных файлов. Первый подход предусматривает считывание информации в оперативную память и сортировку при помощи одного из стандартных методов сортировки массивов. Несмотря на то, что при таком подходе сортировка будет выполняться быстро,  размеры оперативной памяти накладывают сильное ограничение на размер сортируемого файла.

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

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