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

Сортировка символьных строк

Для сортировки символьных строк проще всего создать массив символьных строк,  используя предусмотренный в языке TURBOПаскаль тип данных "string". Это дает вам простой способ индексирования и выполнения операций обмена при сохранении основного алгоритма сортировки неизменным.  Приводимая ниже версия алгоритма быстрой сортировки позволяет упорядочивать символьные строки в алфавитном порядке:

     type
       DataItem = string[80];
       DataArray = array [1..80] of DataItem;

    { алгоритм быстрой сортировки для символьных строк }
     procedure QsString(var item: DataArray; count:integer);

       procedure qs(l, r: integer; var it:DataArray);
         var
         i, l: integer;
         x, y: DataItem;
       begin
         i := l; j := r;
         x := it[(l+r) div 2];
         repeat
           while it[i] < x do i := i+1;
           while x < it[j] 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; { конец быстрой сортировки }

Следует отметить,  что потребовалось изменить только определение типа данного "DataItem" для того,  чтобы настроить алгоритм быстрой сортировки на упорядочивание символьных строк. Это оказывается возможным благодаря превосходной работе,  проделанной фирмой  Borland  по обеспечению использования в Паскале данных типа символьных строк.  На стандартном Паскале запись алгоритма сортировки символьных строк была бы значительно длинее.

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