![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алфавитная сортировка
Сортировка символьной информации отличается от сортировки числовых данных тем, что здесь следует учитывать при сравнении символов их лексикографическую упорядоченность в таблице кодов 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) сортировка строк по рангу.
Примеры
|