|
Страница 13 из 60
Сортировка записей
По-видимому в большинстве прикладных программ, где использу-
ется сортировка, требуется сортировать группы данных. Хорошим
примером этого является список почтовых корреспонденций, посколь-
ку в этом случае фамилия, улица, город, страна и почтовый индекс
составляют связанную группу данных. При сортировке таких групп
данных используется ключ сортировки в операциях сравнения, но в
операциях обмена участвует вся запись целиком. Для того, чтобы
лучше понять этот процесс сначала создадим запись, которая будет
содержать необходимую информацию. Если в качестве примера исполь-
зовать почтовый адрес, то запись может иметь следующий вид:
type
address = record
name: string[30];
street: string[40];
city: string[20];
state: string[2];
zip: string[9];
end;
После описания адреса необходимо изменить следующим образом
определение данного "DataItem":
DataItem = address;
После выполнения этих изменений нужно скорректировать блок
сравнений в алгоритме быстрой сортировки, используя то поле, ко-
торое применяется в качестве ключа сортировки. В приводимой ниже
версии быстрой сортировки в качестве ключа используется поле фа-
милии "name". Это означает, что список почтовых корреспонденций
сортируется в алфавитном порядке фамилий.
{ быстрая сортировка записей с почтовым адресом }
procedure QsRecord(var item: DataArray; count:integer);
procedure qs(l, r:integer; var it:DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i].name < x.name do i := i+1;
while x.name < it[j].name do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end; {конец быстрой сортировки записей}
|