Энциклопедия Turbo Pascal. Главы 9-11 - TurboSort

TurboSort

Инструментарий баз данных предоставляет функцию  TurboSort, которая является разновидностью QuickSort. Она может быть использована для сортировки любого типа данных, если их длина равна по меньшей мере двум байтам. QuickSort используется, так как это самая быстрая сортировка в большинстве ситуаций, как вы видели в Главе 1.  TusboSort  находится в файле SORT.BOX, который должен быть включен в каждую программу, использующую ее. TurboSort объявляется следующим образом

  function TurboSort(ItemSize: integer): integer; 

ItemSize - это размер данных, которые будут сортироваться; он должен быть вычислен с помощью  SizeOf. Значение, возвращаемое TurboSort, интерпретируется, как показано в таблице 9-3. TurboSort может сортировать до 32767 элементов. Хотя функция будет пытаться сортировать их в оперативной памяти для скорости, она будет использовать временный файл на диске, когда это необходимо.

Таблица 9-3  Коды возврата TurboSort

-------------------------------------------------------------
 Значение           Смысл
-------------------------------------------------------------
    0        Сортировка выполнена успешно
    3        В компьютере нет достаточной памяти
    8        Длина элемента меньше 2
    9        Более 32767 входных элементов для сортировки
    10       Ошибка записи на диск
    11       Ошибка чтения с диска
    12       Нет возможности создать временный файл на диске
--------------------------------------------------------------

InP, OutP и Less

TusboSort имеет три фазы работы: ввод данных, которые будут сортироваться, сортировка данных и вывод отсортированных данных. Для того, чтобы помочь TurboSort выполнить свою работу, вы должны создать три процедуры, называемые InP, OutP, Less. Данные процедуры декларируются как forward с помощью SORT.BOX, но вы должны создать действительную реализацию.

Процедура InP используется для передачи  TurboSort  данных, которые должны сортироваться, по одному элементу за раз. Действительная передача выполняется, используя SortRelease, которая также определена в SORT.BOX. Она объявляется следующим образом

     procedure SortRelease(item); 

Так как тип параметра item не задан, могут сортироваться данные любого типа. Простая процедура InP, которая считывает десять целых, введенных с клавиатуры, и передает их TurboSort для сортировки, показана ниже:

     procedure InP;
     var
       f: integer;
     begin
       for i:=1 to 10 do ReadLn(data[i]);
       for i:=1 to 10 do SortRelease(data[i]);
     end; {InP}

Процедура OutP  используется для поэлементного чтения отсортированных данных из TurboSort с помощью SortReturn, определенной в SORT.BOX. SortReturn объявляется следующим образом:

     procedure SortReturn(item); 

Так как тип параметра  item не задан, то могут быть возвращены данные любого типа. Процедура OutP может не обладать информацией о том, сколько элементов данных будет возвращаться, поэтому функция SorEOS может быть использована для проверки на конец данных. Следующая простая процедура OutP может быть использована с целыми числами, генерируемыми процедурой InP, показанной ранее:

     procedure OutP;
     var
       data: integer;
     begin
       repeat
         SortReturn(data);
         write(data,' ');
       until SortEOS;
     end; {OutP}

Функция Less является наиболее важной из трех рассматриваемых, так как она вызывается каждый раз, когда сравниваются два элемента. Функция Less возвращает  TRUE, если первый аргумент меньше второго.  Less декларирована в SORT.BOX, как имеющая два параметра, называемые Х и У, которые вы должны перекрыть с двумя логическими переменными, имеющими тот же самый тип, что и сортированные данные. Перекрытие реализуется с  помощью  команды alsolute. Например, данная версия Less может быть использована для сравнения двух целых переменных:

     function Less;
     var
       first: char absolute X;
       second: char absolute Y;
     begin
       Less := first < second;
     end; {Less}

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

     program simple_sort;

     var
       data: array [1..10] of integer;
       result: integer;

     {$i sort.box} {read in the sort routines}

     procedure InP;
     var
       f: integer;
     begin
       for i:=1 to 10 do ReadLn(dara[i]);
       for i:=1 to 10 do SortRelease(data[i]);
     end; {InP}

     function Less;
     var
       first: char absolute X;
       second: char absolute Y;
     begin
       Less := first < second;
     end; {Less}

     procedure OutP;
     var
       data: integer;
     begin
       repeat
         SortReturn(data);
         write(data, ' ');
       until SortEOS;
     end; {OutP}

     begin
       result:=TurboSort(sizeOf(integer));
       writeLn('sort result; ', result);
     end.