Реализовать функции сортировки методом "пузырька" и методом быстрой сортировки(рекурсивная реализация) для целых числел в порядке невозрастания абсолютных величин для исследования и сравнения эффективности алгоритмов.
git clone https://github.com/NNakleskin/sort-homework.git
Код автоматически генерирует и проводит все необходимые для анализа тесты. Для работы программы необходимо подать на вход число n - количество чисел для составления файлов и дальнейшей сортировки данных в них. Результаты выполнения кода и исходные файлы находятся в папке data.
gen_files.h:
gen_rand(int n) - принимает на вход число n и создает файл data1.txt с n рандомных чисел.
gen_rev(int n) - принимает на вход число n и создает файл data2.txt с числами от n до 1.
gen_rev(int n) - принимает на вход число n и создает файл data2.txt с числами от 1 до n.
sort_func.h:
bubble_sort(int* a, int n, int* count) - принимает на вход указатель на массив с числами, длину массива и массив count[2], в котором count[0] - это число сравнений, а count[1] - число перестановок в результате выполнения кода. Функция сортирует массив.
qsort_alg(int* a, int first, int last, int count[2]) - принимает на вход указатель на массив с числами, номер первого числа, номер последнего числа и массив count[2], в котором count[0] - это число сравнений, а count[1] - число перестановок в результате выполнения кода. Функция сортирует отрезок массива от first до last.
data1.txt - файл с рандомными числами.
data2.txt - файл с отсортированными по убыванию числами.
data3.txt - файл с отсортированными по возрастанию числами.
output1.1.txt - файл с отсортированными рандомными числами методом "пузырька".
output1.2.txt - файл с отсортированными рандомными числами методом бытрой сортировки.
output2.1.txt - файл с отсортированными числами (в изначальном формате от n до 1) методом "пузырька".
output2.2.txt - файл с отсортированными числами (в изначальном формате от n до 1) методом быстрой сортировки.
output3.1.txt - файл с отсортированными числами (в изначальном формате от 1 до n) методом "пузырька".
output3.2.txt - файл с отсортированными числами (в изначальном формате от 1 до n) методом быстрой сортировки.
results.txt - файл с результатами работы программы (количество сравнений и перестановок для каждого случая).
count_cmp - количество сравнений.
count_swap - количество перестановок.
1. Метод «пузырька» (см. [1] 130-132; [2] 27-28; [3] 101-102).
2. Быстрая сортировка, рекурсивная реализация ([3] 114-117).
1. Кнут Д. Искусство программирования для ЭВМ. Том 3. — М.: Мир, 1978.
2. Лорин Г. Сортировка и системы сортировки. — М.: Наука, 1983.
3. Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989.