2014-02-02
1703
Сортировка символьной информации отличается от сортировки числовых данных тем, что здесь следует учитывать при сравнении символов их лексикографическую упорядоченность в таблице кодов 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) сортировка строк по рангу.
