7.5 Сортировка
Сортировка — это процесс размещения элементов в списке в некоторой числовой или лексикографической последовательности (порядке). Различаются следующие виды сортировки.
Обменная сортировка. При этом способе наименьший элемент выдвигается в начало списка, следующий по величине — на вторую позицию и т.д. Для списка N элементов производится N(N – 1)/2, т.е. O(N2) операций. Естественно, что для больших значений N использование этой сортировки нецелесообразно.
Алгоритм:
EXCHANGE_SORT procedure(LIST,N);
declare LIST(N); /* массив сортировки */
do I=1 to N-1;
do J=I+1 to N;
if LIST(J)< LIST(I) then
Reverse(LIST(J), LIST(I));
end;
end;
end EXCHANGE_SORT;
Сортировка слиянием. Данный способ сортировки схож с методом разбиения на подзадачи. Вначале неотсортированный список делится на две части, затем каждая часть сортируется независимо. После этого списки объединяются.
Алгоритм:
MERGE_SORT procedure(LIST,N);
declare LIST(N); /* массив сортировки */
call MERGE_SORT(LIST(1:N/2),N/2,
(LIST(N/2+1:N),N/2));
/* объединение отсортированных списков */
end MERGE_SORT;
Процедура слияния отсортированных списков размером K выполняется за 2×K операций путем просмотра первого элемента в каждом списке и перенесения меньшего из двух в новый список. Эти два действия повторяются для каждого из 2×K элементов списка, получается 4×K операций. Так как каждый из списков уже отсортирован, нужно проверить только первые элементы. Хотя для реализации этого способа нужна память большого объема, время сортировки путем последовательного разбиения каждого из подсписков на два можно уменьшить до величины
7.6 Алгоритм выбора из конечного состояния
Часто задача может быть сведена к множеству действий, зависящих от текущего состояния программы. Такой способ решения задачи называется выбором из конечного состояния и обычно включает таблицу, описывающую выполняемые действия. Строки таблицы определяют состояние программы, а столбцы — возможные действия. Элементы таблицы описывают выполнение возможных действий, в частности имя вызываемой подпрограммы для обработки действий.
Переменными в этом случае являются текущее состояние программы и допустимое воздействие, определяемое внешней средой. Пересечение этих значений в матрице решений определяет ответное действие и новое состояние программы. Такие состояния (алгоритмы) наиболее характерны для лексического анализатора трансляторов. Решение подобных задач строится по типу модели конечного автомата.
Таблица состояний:
|
A |
B |
C |
… |
I |
J |
K |
… |
Y |
Z |
1 |
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
N–1 |
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|
|
|
|
|
|
N+1 |
|
|
|
|
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
|
|
M |
|
|
|
|
|
|
|
|
|
|