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


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

     Для сортировки символьных строк проще всего  создать  массив
символьных строк,  используя предусмотренный в языке 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  по  обеспечению использования в Паскале данных типа
символьных строк.  На стандартном Паскале запись алгоритма сорти-
ровки символьных строк была бы значительно длинее.
     Следует учитывать,  что  операции сравнения символьных строк
выполняются больше времени,  чем операции сравнения символов, так
как  в первом случае каждый раз делается проверка нескольких эле-
ментов.

 
« Предыдущая статья