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


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

     В отличие от файлов с прямым доступом последовательные файлы
обычно  не  используют  записи фиксированной длины и могут разме-
щаться на устройствах памяти, на которых трудно организовать пря-
мой доступ. Поэтому последовательные файлы на дисках используются
в тех случаях,  когда для решения конкретной задачи  удобнее  ис-
пользовать  записи  переменной  длины или когда устройство памяти
ориентировано на последовательный доступ.  Например,  большинство
текстовых файлов имеют последовательную организацию.
     Несмотря на то,  что такой подход к сортировке, когда диско-
вый файл рассматривается как массив,  имеет ряд преимуществ,  его
нельзя применить к последовательным файлам  -  быстрый  доступ  к
произвольному элементу в этом случае невозможен. Например, нельзя
быстро прочитать произвольную запись из  последовательного файла,
расположенного  на  магнитной  ленте.  По  этой причине возникают
трудности по применению любого ранее описанного метода сортировки
массивов к сортировке последовательных файлов.
     Имеется два подхода к  сортировке  последовательных  файлов.
Первый подход предусматривает считывание информации в оперативную
память и сортировку при помощи одного из стандартных методов сор-
тировки массивов. Несмотря на то, что при таком подходе сортиров-
ка будет выполняться быстро,  размеры оперативной памяти наклады-
вают сильное ограничение на размер сортируемого файла.
     При использовании второго подхода, получившего название сор-
тировки слиянием,  весь файл делиться на две равные части. В про-
цессе сортировки из каждого файла считывается по одному элементу,
эта  пара элементов упорядочивается и делается запись элементов в
третий файл,  расположенный на диске.  Новый файл затем снова де-
лится  на два файла и упорядоченные пары элементов объединяются в
упорядоченные группы элементов по четыре элемента в каждой. Затем
полученный  файл  снова  разделяется на два файла и вся процедура
повторяется до тех пор, пока файл не будет отсортирован. Эту сор-
тировку-слияние называют трехленточным слиянием, поскольку в этом
случае одновременно требуется иметь три файла /т.е. три накопите-
ля на магнитной ленте, если файл располагается на ленте/.
     Для того,  чтобы  лучше  понять  работу  сортировки-слияние,
рассмотрим следующую последовательность числе:
     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нец сортировки методом слияния }

 
« Предыдущая статья