|
Страница 11 из 39
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); 1
Так как тип параметра 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.
|