Руководство программиста

Описание структуры программы

Exp.exe

Исходный код программы состоит из двух модулей:

· Exp.c содержит алгоритмы ввода и вывода информации на экран, генерации случайных чисел, генерации массива с учетом заданных пользователем параметров.

· Sorts.c содержит алгоритмы сортировок пузырьком и слиянием, а так же функцию сравнения двух переменных типа float, необходимую для работу стандартной функции qsort.

Tests.exe

Исходный код программы состоит из модуля Tests.cpp, содержащего алгоритмы ввода и вывода информации и алгоритм серийного запуска программы Exp.exe.

Описание структур данных

Exp.exe

1. int num – количество элементов в сортируемом массиве.

2. int seed – инициализатор генератора случайных чисел.

3. int stype – номер алгоритма сортировки:

· 1 – qsort;

· 2 – сортировка пузырьком;

· 3 – сортировка слиянием.

4. float* arr – сортируемый динамический массив.

5. int i – переменная циклов.

6. LARGE_INTEGER freq, sQP, fQP – переменные, используемые для замера времени сортировки.

Tests.exe

1. int innum, ternum – начальное и конечное количество элементов в сортируемом массиве.

2. int step – шаг (число, на которое увеличивается количество элементов);

3. int seed – инициализатор генератора случайных чисел.

4. int stype – номер алгоритма сортировки:

· 1 – qsort;

· 2 – сортировка пузырьком;

· 3 – сортировка слиянием.

5. char *app – название программы для серийного эксперимента.

6. FILE* fTime, fElem – переменные для работы с файлами.

 

Описание алгоритмов

Сортировка пузырьком

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива.

Реализация алгоритма представлена в приложении 1.

Сортировка слиянием

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

2. Получившиеся в результате последнего разбиения два отсортированных массивы «сливаются» в один отсортированный (выбором меньшего из двух элементов).

3. Процедура слияния повторяется для всех совершенных разбиений.

Реализация алгоритма представлена в приложении 2.

Результаты экспериментов