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

Сортировка записей

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

     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; {конец быстрой сортировки записей}