Построение моделей алгоритмов в системе GRAPH

В качестве примера использования системы GRAPH для описания алгоритмов рассмотрим известный алгоритм сортировки «вставками».

Пусть нам задан массив натуральных чисел . Для простоты введем фиктивный наименьший элемент (для ЭВМ ).

Создадим словарь данных ПОП. В первую очередь в качестве конструктивного объекта для множества данных массив A (в языке C++ тип массива определяется описанием: typedef int MASSIV[200];). Переменные n, i, j, w описаны в таблице 1.

Таблица 1.

Алгоритм сортировки вставками представлен на рисунке 5.

Здесь

· образом обозначена вычислимая функция (объект) вывода на печать содержимого массива A (int k;printf("массив А: \n"); for (k=1;k<=n;k++) printf(" %d",A[k]); printf("\n"); getch(););

· образом обозначен объект «j++»;

· образом обозначен объект «i--»;

· образом обозначена пустая функция «// Конец».

Нулевому элементу массива (A[0]) присвоено значение -32000.

Работа алгоритма начинается с вызова корневой вершины (на рисунке 5 обведена «жирно»). В данном случае – печать исходного массива данных. Далее, последовательно, начиная с элемента A[j] (первоначально j=2) на участке массива A от j до 1 производится упорядочивание элементов в порядке возрастания их значений.

Для этого индексу «i» присваивается значение на 1 меньше j (вершина 1). В объекте 2 запоминается «старшее» (улучшаемое значение элемента) A[j]. При этом в цикле вершина 3 – вершина 4 производится перемещение элементов в направлении A[j], до тех пор, пока не выполнится логическая функция 2 (w<A[i]). В этом случае на «освободившееся» место вставляется элемент A[j] (объект 5). Очевидно, что на данный момент все элементы на участке от 1 до j оказываются упорядоченными.

В блоке 8 производится печать текущего состояния массива, в вершине 6 – увеличение индекса j на 1.

Алгоритм работает, пока не исчерпаются все числа массива A (предикат 3).

2. СЛОЖНОСТЬ АЛГОРИТМОВ