Учебное пособие 80053

а) сортировка выбором; б) сортировка обменами;

в) сортировка включениями (вставками).

Далее следует пример программы, использующей алгоритм сортировки вставками.

#include <stdio.h>

#include <stdlib.h>

typedef int Item;

#define key(A) (A)

#define less(A, B) (key(A) < key(B))

#define exch (A, B) { Item t = A; A = В; В = t; }

#define compexch(A, B) if (less(B, A)) exch(A, B)

void sort (Item a[], int l, int r)

{ int i, j;

for (i = l+1; i <= r; i++)

for (j = i; j > 1; j--)

compexch(a[j-1], a [ j ]) ;

}

main(int argc, char *argv[])

{ int i, N = atoi (argv[1] ) , sw = atoi (argv[2]) ;

int *a = malloc(N*sizeof(int));

if (sw)

for (i = 0; i < N; i++)

a[i] = 1000*(1.0*rand()/RAND_MAX);

else {

20

N=0; while (scanf("%d", &a[N]) == 1) N++; }

sort(a, 0, N-1);

for (i = 0; i < N; i++) printf ("%3d ", a[i]);

printf("\n") ;

}

В программе в зависимости от значения sw сортируемый массив либо вводится из файла, либо заполняется случайными числами из диапазона [0..1000).

На этом занятии необходимо провести анализ времени работы алгоритмов сортировки в зависимости от количества сортируемых данных и их изначальной упорядоченности. В качестве сортируемого массива используйте массив целых чисел. Тексты других программ сортировки можно брать из материалов лекций или из других доступных источников.

Для измерения астрономического времени используется функция clock. Если измерить значение времени перед вызовом сортировки, а затем после нее, то разность этих времен есть длительность сортировки.

#include <time.h>

void prt_time(char *c){

float af;

t_end = clock();

af=(t_end - t_start) / (float)CLK_TCK;

printf("%s: %f\n", c, af);

}

. . .

clock_t t_start, t_end;

21

. . .

t_start = clock(); //перед стартом сортировки

prt_time("c"); //после сортировки

. . .

Функция prt_time считывает текущее время и печатает длительность интервала времени. Параметр функции prt_time

– буква, идентификатор интервала (позволяет различать несколько интервалов времени, отсчитываемых с момента старта).

Примечание: для сортировки можно использовать массив, содержащий любое количество элементов. Главное условие, которое должно выполняться – время на сортировку, затрачиваемое любым из предложенных в лабораторной работе алгоритмов, поддается измерению (больше 0). Для небольших по размеру массивов (порядка 1 000 элементов) время сортировки на современных компьютерах очень маленькое, поэтому повышения точности измерений необходимо многократно повторить процесс сортировки (порядка 10 раз). При этом перед очередным вызовом функции сортировки необходимо восстановить исходный не отсортированный массив.

Примерный порядок анализа алгоритма сортировки.

1.Заполнить массив для сортировки

2.Сохранить копию неотсортированного массива в переменную mas

3.Зафиксировать время перед началом сортировки

4.Организовать цикл для многократной сортировки (повторять repeat раз)

for (i = 0; i < repeat; i++ )

{

4.1.Вызов функции сортировки для массива

22

4.2. Скопировать все элементы из неотсортированного массива mas2

}

5. Вычислить время, затраченное на сортировку и вывести это время на экран (prt_time)

6. Повторить с 3 по 6 пункты для следующего алгоритма сортировки

Для того чтобы сравнение алгоритмов сортировки можно было считать корректным, каждый из них должен сортировать один и тот же массив значений!

Для исследования алгоритмов сортировки необходимо выполнить следующее.

1.Определить массив из 10 000 целых чисел и заполнить его случайными значениями.

2.Провести многократное выполнение сортировки массива несколькими алгоритмами поочередно. Зафиксировать время, потраченное на сортировку каждым алгоритмом.

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

4.Результаты полученных исследований оформите в виде таблицы.

Контрольные вопросы

1.В чем заключается сортировка методом вставки?

2.В чем заключается быстрая сортировка?

3.В чем заключается сортировка слиянием?

23

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная.

Шаг 2. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина.

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные.

// Программа поиска в глубину

void Depth_First_Search(int n, int **Graph, bool *Visited,

int Node){

Visited[Node] = true;

cout << Node + 1 << endl;

for (int i = 0 ; i < n ; i++)

if (Graph[Node][i] && !Visited[i])

Depth_First_Search(n,Graph,Visited,i);

}

Также часто используется нерекурсивный алгоритм поиска в глубину. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней.

Временная сложность зависит от представления графа. Если применена матрица смежности, то временная сложность равна O(n2), а если нематричное представление – O(n+m): рассматриваются все вершины и все ребра.

Поиск в ширину

25

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

Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины.

Алгоритм поиска в ширину

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста.

//Программа поиска в ширину

void Breadth_First_Search(int n, int **Graph,

bool *Visited, int Node){

26

int *List = new int[n]; //очередь

int Count, Head; // указатели очереди int i;

// начальная инициализация for (i = 0; i < n ; i++)

List[i] = 0;

Count = Head = 0;

// помещение в очередь вершины Node

List[Count++] = Node; Visited[Node] = true; while ( Head < Count ) {

//взятие вершины из очереди

Node = List[Head++]; cout << Node + 1 << endl;

// просмотр всех вершин, связанных с вершиной Node for (i = 0 ; i < n ; i++)

// если вершина ранее не просмотрена if (Graph[Node][i] && !Visited[i]){

// заносим ее в очередь

List[Count++] = i;

Visited[i] = true;

}

}

}

27

Сложность поиска в ширину при нематричном представлении графа равна O(n+m), ибо рассматриваются все n вершин и m ребер. Использование матрицы смежности приводит к оценке O(n2)

Задание

1.Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину.

2.Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в ширину.

3.Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины.

4.Перенумеруйте вершины графа в порядке обхода в глубину и вычислите среднюю плотность графа как частное от деления количества его ребер на число вершин.

Контрольные вопросы:

1.В чём состоит основная идея поиска в глубину?

2.В чём состоит основная идея поиска в ширину?

3.Какие результаты позволяют получить алгоритмы обхода графа?

28