logo
Конспект лекций Дискретная математика

1.3.2. Построение моделей алгоритмов в системе graph

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

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

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

Таблица 1.

Словарь данных

Имя данного

Тип

Класс данного

Нач. значение

Комментарий

A

MASSIV

I

{-32000,18,4,56,65,37,63,66}

Массив, который необходимо отсортировать

n

int

I

6

Размерность массива A

j

int

I

2

Цикл

i

int

V

0

Счетчик

w

int

V

0

Промежуточный элемент

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

Здесь

Нулевому элементу массива (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).