Алфавитная сортировка

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

- символы используемого алфавита имеют упорядоченные коды ASCI

- символы используемого алфавита не имеют упорядоченные коды ASCI;

Возможно использование сравнительных и распределительных методов.

Первый способ применим для случая, если известно, что символы используемого алфавита имеют упорядоченные коды ASCI, например буквы русского и латинского алфавитов, цифры.

Пример.

Требуется упорядочить по фамилии записи учета граждан. Запись имеет структуру:

= ФИО (FIO) – до 30 символов

= год рождения (GR) – диапазон от 1928 до 2005

Для этого используем сравнительную сортировку.

program sort;

const M=50;

type

INF=record

FIO: string[30];

GR: 1928..2005;

end;

var

X: array[1..M] of inf;

N: integer;

FLAG: 0..1;

T: INF;

I, J: integer;

begin

write('ВВЕДИТЕ К-ВО ЗАПИСЕЙ: ');

readln(N);

writeln('МАССИВ ДО СОРТИРОВКИ');

for I: =1 to N do

with X[I] do

begin

write('ВВЕДИТЕ FIO ', I, '-Й ЗАПИСИ '); READLN(FIO);

write('ВВЕДИТЕ GR ', I, '-Й ЗАПИСИ '); READLN(GR);

end;

J: =1;

repeat

FLAG: =0;

for I: =1 to N-J do

begin

if X[I].FIO > X[I+1].FIO then

begin

T: =X[I];

X[I]: =X[I+1];

X[I+1]: =T;

FLAG: =1;

end;

end;

J: =J+1

until FLAG=0;

writeln('МАССИВ ПОСЛЕ СОРТИРОВКИ');

for I: =1 to N do

with X[I] do

begin

writeln('ФАМИЛИЯ: ', FIO);

writeln('ГОД: ', GR);

end;

end.

Второй случай. Предполагается, что для всех символов используемого алфавита нельзя предусмотреть строго упорядоченный интервальный тип в заданном диапазоне порядковых позиций по таблице кодов ASCI, как, например, для цифр.

Первый способ.

А) Для символов произвольного алфавита можно применить перечисляемый тип и использовать тот факт, что в перечисляемом типе элементы упорядочены в порядке перечисления.

В случае сортировки текста в Турбо-Паскаль не нужно задавать строку образа упорядочения символов типа DATA, так как их порядковые позиции уже упорядочены в таблице кода ASСI

Используем распределительную(поразрядную) сортировку.

program sort;

const M=50;

type

INF=record

FIO: string[30];

GR: 1926..1998;

end;

var

X: array[1..M] of inf;

N: integer;

FLAG: 0..1;

T: INF;

I, J: integer;

L, L1, L2: integer;

DATA: string[72];

begin

write('ВВЕДИТЕ К-ВО ЗАПИСЕЙ: ');

readln(N);

writeln('МАССИВ ДО СОРТИРОВКИ');

for I: =1 to N do

with X[I] do

begin

write('ВВЕДИТЕ FIO ', I, '-Й ЗАПИСИ '); READLN(FIO);

write('ВВЕДИТЕ GR ', I, '-Й ЗАПИСИ '); READLN(GR);

end;

DATA: ='АаБбВвГгДдЕеЖжЗзИиЙйКкЛлМмНнОоПпРрСсТтУуФфХхЦцЧчШшЩщъыьЭэЮюЯя';

repeat

FLAG: =0;

for I: =1 to N-1 do

begin

L1: =length(X[I].FIO);

L2: =length(X[I+1].FIO);

if L1> =L2 then

L: =L1

else

L: =L2;

J: =1;

while (pos(X[I].FIO[J], DATA)=

pos(X[I+1].FIO[J], DATA)) and (J< L) do J: =J+1;

if pos(X[I].FIO[J], DATA) >

pos(X[I+1].FIO[J], DATA) then

begin

T: =X[I];

X[I]: =X[I+1];

X[I+1]: =T;

FLAG: =1;

end;

end;

until FLAG=0;

writeln('МАССИВ ПОСЛЕ СОРТИРОВКИ');

for I: =1 to N do

with X[I] do

begin

writeln('ФАМИЛИЯ: ', FIO);

writeln('ГОД: ', GR);

end;

end.

Б) Второй способ. Задачу сведем к сравнительному методу сортировки. Метод основан на вычислении и сортировке рангов исходного символьного массива, указывающих на место отдельной строки в отсортированном списке. Для этого необходимо выполнить предварительную работу по созданию таблицы рангов упорядоченных последовательностей символов.

Рассмотрим на примере букв русского алфавита и символа пробела. Пусть трубуется сортировать символьный массива X, содержащий

N строк по М символов в строке на заданную глубину G.

1 2 3... M

-------------------------------------

.

.

.

N

Для букв русского алфавита ранг R будем вычислять по следующей формуле

Сортировку можно организовать в два этапа:

1) вычисление ранга для каждой строки

2) сортировка строк по рангу.

Примеры