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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

с₁₁	с₁₂	...	с₁_j	...	с₁_k			– 1-я строка (стр₁)
с₂₁	с₂₂	...	с₂_j	...	…	с₂_l		– 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(стр₁, стр₂,…, стр_i,…, стр_n);

стр₁ = стр_min1;

стр_min2 = min(стр₂,…, стр_i,…, стр_n);

стр₂ = стр_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.

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