3 Заключение
В ходе выполнения лабораторной работы №1 были оценены алгоритмические сложности алгоритмов сортировки, таких как: сортировка
«Расческа», сортировка Шелла, быстрая сортировка, пирамидальная сортировка.
Приложение А (обязательное)
#include <stdio.h> #include <stdlib.h> #include <time.h>
//количество массивов, создаваемых для каждой размерности const int arrays_count = 1000;
//количество размерностей массива (1,2,3,4,5,10,15 и т.д.) const int sizes_count = 15;
//значения размерностей массива
const int sizes[15] = {1, 2, 3, 4, 5, 10, 15, 20, 25, 30, 50, 75, 100, 250, 500};
//диапазон значений для генерации массива const int min_val = -100;
const int max_val = 100;
//количество перестановок int swaps;
//количество сравнений int compares;
//сортировка "расческой"
void combSort(int *arr, int size)
{
double factor = 1.247; //фактор уменьшения int step = size - 1; //шаг сортировки
int tmp; //переменная для обмена элементов
//когда step = 1, выполняется последняя итерация цикла (эквивалентна одному проходу сортировки пузырьком)
while (step >= 1)
{
for (int i = 0; i + step < size; i++)
{
if (arr[i] > arr[i + step])
{
tmp = arr[i];
arr[i] = arr[i + step]; arr[i + step] = tmp;
swaps++; //увеличим количество перестановок
}
compares++; //увеличим количество сравнений (if)
}
step = step / factor; //уменьшим шаг сортировки compares++; //увеличим количество сравнений (while)
}
compares++; //увеличим количество сравнений (while, когда мы в него не зашли)
}
//заполнение массива случайными значениями void fill(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = rand() % max_val + min_val;
}
}
//вывод массива
void print(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//использовать текущее время в качестве начального числа для генератора случайных чисел
srand (time(0));
//размер массива int size;
//указатель на массив int *a[arrays_count];
//время, затраченное на сортировку double elapsed_time;
//переменные для замеров времени типа clock_t clock_t begin, end;
//выводим заголовок таблицы с расчетами printf("size\toperations\ttime\n");
//цикл перебора размерностей массива for (int i = 0; i < sizes_count; i++)
{
//обнулим количества перестановок и сравнений compares = 0;
swaps = 0;
//получаем размер массива size = sizes[i];
//выводим размер массива printf("%d\t", size);
//выделяем память под массивы for (int j = 0; j < arrays_count; j++)
{
a[j] = (int*)malloc(sizeof(int) * size);
}
//заполняем массивы
for (int j = 0; j < arrays_count; j++)
{
fill(a[j], size);
}
//фиксируем время начала сортировки begin = clock();
//сортируем массивы
for (int j = 0; j < arrays_count; j++)
{
combSort(a[j], size);
}
//фиксируем время окончания сортировки end = clock();
//вычисляем время, затраченное на сортировки (clock() / CLOCKS_PER_SECS)
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
//выводим среднее значение количества перестановок + количества сравнений
printf("%8.3lf\t", (swaps + compares) / (double)arrays_count);
//выводим среднее время сортировки printf("%lf", elapsed_time / arrays_count); printf("\n");
}
return 0;
}
Приложение Б (обязательное)
#include <stdio.h> #include <stdlib.h> #include <time.h>
//количество массивов, создаваемых для каждой размерности const int arrays_count = 1000;
//количество размерностей массива (1,2,3,4,5,10,15 и т.д.) const int sizes_count = 15;
//значения размерностей массива
const int sizes[15] = {1, 2, 3, 4, 5, 10, 15, 20, 25, 30, 50, 75, 100, 250, 500};
//диапазон значений для генерации массива const int min_val = -100;
const int max_val = 100;
//количество перестановок int swaps;
//количество сравнений int compares;
//сортировка Шелла
void shellSort(int* arr, int size)
{
int tmp; //переменная для обмена элементов for (int s = size / 2; s > 0; s = s / 2)
{
for (int i = 0; i < size; i++)
{
for (int j = i + s; j < size; j = j + s)
{
if (arr[i] > arr[j])
{
tmp = arr[j]; arr[j] = arr[i]; arr[i] = tmp;
swaps++; //увеличим количество перестановок
}
compares++; //увеличим количество сравнений
}
}
}
compares++; //до того, как войти в цикл while
}
//заполнение массива случайными значениями void fill(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = rand() % max_val + min_val;
}
}
//вывод массива
void print(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//использовать текущее время в качестве начального числа для генератора случайных чисел
srand (time(0));
//размер массива int size;
//указатель на массив int *a[arrays_count];
//время, затраченное на сортировку double elapsed_time;
//переменные для замеров времени типа clock_t clock_t begin, end;
//выводим заголовок таблицы с расчетами printf("size\toperations\ttime\n");
//цикл перебора размерностей массива for (int i = 0; i < sizes_count; i++)
{
//обнулим количества перестановок и сравнений compares = 0;
swaps = 0;
//получаем размер массива size = sizes[i];
//выводим размер массива printf("%d\t", size);
//выделяем память под массивы for (int j = 0; j < arrays_count; j++)
{
a[j] = (int*)malloc(sizeof(int) * size);
}
//заполняем массивы
for (int j = 0; j < arrays_count; j++)
{
fill(a[j], size);
}
//фиксируем время начала сортировки begin = clock();
//сортируем массивы
for (int j = 0; j < arrays_count; j++)
{
shellSort(a[j], size);
}
//фиксируем время окончания сортировки end = clock();
//вычисляем время, затраченное на сортировки (clock() / CLOCKS_PER_SECS)
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
//выводим среднее значение количества перестановок + количества сравнений
printf("%8.3lf\t", (swaps + compares) / (double)arrays_count);
//выводим среднее время сортировки printf("%lf", elapsed_time / arrays_count); printf("\n");
}
return 0;
}
Приложение В (обязательное)
#include <stdio.h> #include <stdlib.h> #include <time.h>
//количество массивов, создаваемых для каждой размерности const int arrays_count = 1000;
//количество размерностей массива (1,2,3,4,5,10,15 и т.д.) const int sizes_count = 15;
//значения размерностей массива
const int sizes[15] = {1, 2, 3, 4, 5, 10, 15, 20, 25, 30, 50, 75, 100, 250, 500};
//диапазон значений для генерации массива const int min_val = -100;
const int max_val = 100;
//количество перестановок int swaps;
//количество сравнений int compares;
//быстрая сортировка
void quickSort(int* arr, int first, int last)
{
int tmp; //переменная для обмена элементов
int left, right, middle; //переменные для правой и левой границ и центра if (first < last)
{
left = first; //левая граница right = last; //правая граница
middle = arr[(left + right) / 2]; //опорный элемент (центр)
do
{
//пропускаем уже отсортированные участки while (arr[left] < middle)
{
left++; compares++;
}
while (arr[right] > middle)
{
right--; compares++;
}
compares = compares + 2; //увеличим количество сравнений (2 верхних while, когда мы в них не зашли)
if (left <= right)
{
tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++;
right--;
swaps++; //увеличим количество перестановок
}
compares = compares + 2; //увеличим количество сравнений (верхний if и нижний while)
}
while (left <= right);
quickSort(arr, first, right); //сортируем левый подмассив quickSort(arr, left, last); //сортируем правый подмассив
}
compares++; //увеличим количество сравнений (первый if)
}
//заполнение массива случайными значениями void fill(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = rand() % max_val + min_val;
}
}
//вывод массива
void print(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//использовать текущее время в качестве начального числа для генератора случайных чисел
srand (time(0));
//размер массива int size;
//указатель на массив int *a[arrays_count];
//время, затраченное на сортировку double elapsed_time;
//переменные для замеров времени типа clock_t clock_t begin, end;
//выводим заголовок таблицы с расчетами printf("size\toperations\ttime\n");
//цикл перебора размерностей массива for (int i = 0; i < sizes_count; i++)
{
//обнулим количества перестановок и сравнений compares = 0;
swaps = 0;
//получаем размер массива size = sizes[i];
//выводим размер массива printf("%d\t", size);
//выделяем память под массивы for (int j = 0; j < arrays_count; j++)
{
a[j] = (int*)malloc(sizeof(int) * size);
}
//заполняем массивы
for (int j = 0; j < arrays_count; j++)
{
fill(a[j], size);
}
//фиксируем время начала сортировки begin = clock();
//сортируем массивы
for (int j = 0; j < arrays_count; j++)
{
quickSort(a[j], 0, size - 1);
}
//фиксируем время окончания сортировки end = clock();
//вычисляем время, затраченное на сортировки (clock() / CLOCKS_PER_SECS)
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
//выводим среднее значение количества перестановок + количества сравнений
printf("%8.3lf\t", (swaps + compares) / (double)arrays_count);
//выводим среднее время сортировки printf("%lf", elapsed_time / arrays_count); printf("\n");
}
return 0;
}
Приложение Г (обязательное)
#include <stdio.h> #include <stdlib.h> #include <time.h>
//количество массивов, создаваемых для каждой размерности const int arrays_count = 1000;
//количество размерностей массива (1,2,3,4,5,10,15 и т.д.) const int sizes_count = 15;
//значения размерностей массива
const int sizes[15] = {1, 2, 3, 4, 5, 10, 15, 20, 25, 30, 50, 75, 100, 250, 500};
//диапазон значений для генерации массива const int min_val = -100;
const int max_val = 100;
//количество перестановок int swaps;
//количество сравнений int compares;
//формирование пирамиды
void siftDown(int* arr, int root, int bottom)
{
int tmp; //переменная для обмена элементов int maxChild; //индекс максимального потомка
int done = 0; //флаг того, что пирамида сформирована
//пока не дошли до последнего ряда while ((root * 2 <= bottom) && (!done))
{
if)
compares = compares + 2; //увеличим количество сравнений (while и нижний
//если мы в последнем ряду if (root * 2 == bottom)
{
maxChild = root * 2; //запоминаем левый потомок
}
//иначе запоминаем больший потомок из двух else
{
if (arr[root * 2] > arr[root * 2 + 1]) maxChild = root * 2; else maxChild = root * 2 + 1;
compares++; //увеличим количество сравнений
}
//если элемент вершины меньше максимального потомка if (arr[root] < arr[maxChild])
{
tmp = arr[root]; //меняем их местами arr[root] = arr[maxChild]; arr[maxChild] = tmp;
root = maxChild;
swaps++; //увеличим количество перестановок
}
else done = 1; //пирамида сформирована compares++; //увеличим количество сравнений
}
}
//пирамидальная сортировка void heapSort(int* arr, int size)
{
int tmp; //переменная для обмена элементов
//формируем нижний ряд пирамиды for (int i = (size / 2); i >= 0; i--)
{
siftDown(arr, i, size - 1);
}
//просеиваем через пирамиду остальные элементы for (int i = size - 1; i >= 1; i--)
{
tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
swaps++; //увеличим количество перестановок siftDown(arr, 0, i - 1);
}
}
//заполнение массива случайными значениями void fill(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
arr[i] = rand() % max_val + min_val;
}
}
//вывод массива
void print(int *arr, int size)
{
for (int i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
//использовать текущее время в качестве начального числа для генератора случайных чисел
srand (time(0));
//размер массива int size;
//указатель на массив int *a[arrays_count];
//время, затраченное на сортировку double elapsed_time;
//переменные для замеров времени типа clock_t clock_t begin, end;
//выводим заголовок таблицы с расчетами printf("size\toperations\ttime\n");
//цикл перебора размерностей массива for (int i = 0; i < sizes_count; i++)
{
//обнулим количества перестановок и сравнений compares = 0;
swaps = 0;
//получаем размер массива size = sizes[i];
//выводим размер массива printf("%d\t", size);
//выделяем память под массивы for (int j = 0; j < arrays_count; j++)
{
a[j] = (int*)malloc(sizeof(int) * size);
}
//заполняем массивы
for (int j = 0; j < arrays_count; j++)
{
fill(a[j], size);
}
//фиксируем время начала сортировки begin = clock();
//сортируем массивы
for (int j = 0; j < arrays_count; j++)
{
heapSort(a[j], size);
}
//фиксируем время окончания сортировки end = clock();
//вычисляем время, затраченное на сортировки (clock() / CLOCKS_PER_SECS)
elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
//выводим среднее значение количества перестановок + количества сравнений
printf("%8.3lf\t", (swaps + compares) / (double)arrays_count);
//выводим среднее время сортировки printf("%lf", elapsed_time / arrays_count); printf("\n");
}
return 0;
}