Ранжирование массива символьных строк по алфавиту

Ранжирование массива символьных строк по алфавиту в принципе реализуется использованием методик сортировки символов в строке.

Математически оптимальный вариант – на первом шаге выполнить сортировку символьных строк по первой их букве. При наличии блоков строк с одинаковыми первыми буквами осуществить сортировку каждого блока по второй букве. При необходимости, полученные новые блоки с двумя одинаковыми начальными буквами ранжируются по третьей букве и т.д.

Оптимальный по количеству шагов выполнения алгоритм достаточно сложно реализуется.

Более простой вариант – последовательное попарное сравнение символов двух соседних строк, от первой буквы и далее.

Каждое сравнение определяет возможность одного из вариантов:

· буквы одинаковы (коды равны);

· буква текущей строки ближе к началу алфавита, чем буква последующей строки (код первой меньше кода второй);

· буква текущей строки дальше от начала алфавита, чем буква последующей строки (код первой больше кода второй).

Первый и второй варианты подтверждают правильное расположение по алфавиту сравниваемых строк. Третий – предписывает поменять строки местами.

Существенное увеличение количества выполняемых операций компенсируется значительным упрощением алгоритма ранжирования строк, то есть простотой его реализации на ЭВМ.

Упорядочение символов в строке по алфавиту рассмотрим на конкретной задаче (9.7) о символьном массиве.

Постановка задачи

Дан не упорядоченный список студенческой группы. Количество студентов не превышает 25, количество символов в каждой строке (фамилия, имя, отчество) не более 30. Требуется отранжировать исходный массив строк по алфавиту.

Формирование математической модели

Исходные данные

СТР(N, М) –массив символьных строк;

N £ 25 – максимальное количество строк массива;

М £ 30 – максимальное количество символов в строке;

n – реальное количество строк массива.

Модель массива СТР(N, М):

с11 с12 ... с1j ... с1k     – 1-я строка (стр1)
с21 с22 ... с2j ... с2l   – 2-я строка (стр2)
     
сi1 сi2 ... сij ... сil сim – i-я строка (стрi)
     
сn1 сn2 ... сnj ... сnk     – n-я строка (стрn)

i, j – текущие индексы строки массива и символа в строке;

i = i + 1, j = j + 1 – законы изменения индексов;

1 i n, 1 j m – диапазоны изменения индексов элементов.

Характерная особенность массивов символьных строк – длины строк (количество символов каждой) различны, не более максимально возможного значения, заданного в описателе.

Внимание! При составлении расчетных зависимостей под минимальной будем понимать строку с наименьшим кодом.

Расчётные зависимости

стрmin1 = min(стр1, стр2,…, стрi,…, стрn);

стр1 = стрmin1;

стрmin2 = min(стр2,…, стрi,…, стрn);

стр2 = стрmin2;

стрmin i = min(стрi,…, стрn-1, стрn);

стрi = стрmin i;

стрmin n-1 = min(стрn-1,стрn);

стрn-1 = стрmin n-1;

Выбор метода решения

Решение задачи реализуем модифицированным методом «пузырька», описанным ранее:

· присвоить индексу внешнего цикла его начальное значение (i = 1) – зафиксировать номер i строки стрi, с которой идет сравнение;

· присвоить индексу внутреннего цикла его начальное значение через внешний (j = i+1);

· сравнить зафиксированное значение стрi с текущим стрj (стрi > стрj);

· выполнить переприсваивание стрпр = стрi, стрi = стрj и стрj = стрпр, если условие выполняется;

· изменить индекс внутреннего цикла по закону j = j + 1;

· повторять три предыдущих пункта пока j £ n;

· изменить индекс внешнего цикла по закону i = i + 1;

· повторять предыдущие пункты, кроме первого, пока i £ n-1;

· прекратить решение при i > n-1.

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