Постановка задачи
В программе реализуется два метода сортировки массива чисел и проводится их экспериментальное сравнение.
Для сравнения используются методы быстрой и медленной сортировки, а именно, пирамидальная сортировка и сортировка методом «пузырька». Элементами массива являются 64-разрядные целые числа. В результате каждой из сортировок числа должны быть упорядочены по невозрастанию.
Структура программы и спецификация функций
Функция void BubbleSort(long long int *a, int n) - сортировка методом "пузырька". Параметры функции: a - указатель на сортируемый массив, n - количество элементов в массиве.
Функция void HeapSort (long long int *a, int n) - пирамидальная сортировка. Параметры функции: a - указатель на сортируемый массив, n - количество элементов в массиве.
Функция static void sift(long long int *a, int n, int i) - просеивание элементов через кучу. Параметры функции: a - указатель на сортируемый массив, n - количество элементов в массиве, i - корневой узел поддерева, которое преобразовывается в двоичную кучу.
Функция void swap (long long int *a, long long int *b) - обмен значениями. Параметры функции: a - указатель на первую переменную, b - указатель на вторую переменную.
Функции-компараторы cmp1 и cmp2 для встроенной функции qsort. Прототип функции: int cmp1(const void *a, const void *b). Параметры функции: a, b - указатели на элементы массива.
Функция void gen (int n, int MassivType) - генерация массива тремя способами, в зависимости от введенного параметра. Параметры функции: n - длина массива, MassivType - целое число, задающее порядок построения элементов в массиве.
В качестве счетчиков числа сравнений и перемещений для каждой из сортировок использовались глобальные переменные: long long int comp и long long int mov. Для средних значений этих показателей использовались глобальные переменные: long double compB, movB, compP, movP.
Файлы
sort_t.pdf - отчет о проделанной работе
sort.c - программный код на C