Курсовая работа: Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

Из выше сказанного следует, что в процессе работы потребуются следующие переменные:

n – количество элементов массива;

A – сортируемый массив;

i – переменная цикла (по исходной последовательности);

j – переменная внутреннего цикла (по готовой последовательности);

x – i-й ключ (переносимый элемент).

Все переменные целого типа.

2.4 Описание схемы алгоритма

Блок-схема данного алгоритма изображена на рис. 2 в Приложении.

Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блоки 1, 2), затем организуется цикл по всей длине массива, во время которого ставится «барьер» (блок 3) и проводится сравнение i-го ключа с элементами готовой последовательности (стоящими раньше него). При этом все элементы, большие этого ключа (это условие проверяется в блоке 4), сдвигаются вправо (блок 5). Это происходит до тех пор, пока не встретится элемент меньший либо равный данному ключу (по крайней мере барьеру). Тогда i-й ключ вставляется в эту позицию (блок 6).

2.5 Контрольные примеры решения задачи с помощью алгоритма сортировки простыми включениями

Пример сортировки массива, отсортированного случайным образом.

Пусть задан такой массив из восьми элементов: (32,43,2,30,82,8,5,52) (см. Таб. 1).

Начальные ключи	32	43	02	30	82	08	05	52
i = 2	32	43	02	30	82	08	05	52
i = 3	02	32	43	30	82	08	05	52
i = 4	02	30	32	43	82	08	05	52
i = 5	02	30	32	43	82	08	05	52
i = 6	02	08	30	32	43	82	05	52
i = 7	02	05	08	30	32	43	82	52
i = 8	02	05	08	30	32	43	52	82

Пошаговое решение:

Шаг 1:

1) i=2;

2) x=43; a[0]=43; j=1;

3) x > a[j]=32;

3.2) a[2]= 43;

4) i=3; i ≤ n=8 → п. 2;

Шаг 2:

2)x=2; a[0]=2; j=2;

3) x < a[j]=43;

3.1) a[3]=43; j=1; → п. 3;

3) x < a[j]=32;

3.1) a[2]=32; j=0; → п. 3;

3) x = a[j];

3.2) a[1]=2;

4) i=4; i<n → п. 2;