-
Notifications
You must be signed in to change notification settings - Fork 0
/
project.c
181 lines (148 loc) · 6.19 KB
/
project.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h> // Added math library for exp function
#include "sorting_functions.h"
#define SMALL_SIZE 100
#define MEDIUM_SIZE 1000
#define LARGE_SIZE 10000
#define NUM_ALGORITHMS 6
// Wrapper function for mergeSort
void wrapperMergeSort(int arr[], int size) {
mergeSort(arr, 0, size - 1);
}
// Wrapper function for quickSort
void wrapperQuickSort(int arr[], int size) {
quickSort(arr, 0, size - 1);
}
// Wrapper function for heapSort
void wrapperHeapSort(int arr[], int size) {
heapSort(arr, size);
}
// Function to generate a random array of a given size
int* generateRandomArray(int size) {
int* arr = (int*)malloc(size * sizeof(int));
for (int i = 0; i < size; i++) {
arr[i] = rand(); // Generates random integers
}
return arr;
}
// Function to generate a sorted array in ascending order
int* generateAscendingArray(int size) {
int* arr = (int*)malloc(size * sizeof(int));
for (int i = 0; i < size; i++) {
arr[i] = i;
}
return arr;
}
// Function to generate a sorted array in descending order
int* generateDescendingArray(int size) {
int* arr = (int*)malloc(size * sizeof(int));
for (int i = 0; i < size; i++) {
arr[i] = size - i - 1;
}
return arr;
}
// Function to generate a mixed array with both positive and negative numbers
int* generateMixedArray(int size) {
int* arr = (int*)malloc(size * sizeof(int));
for (int i = 0; i < size; i++) {
arr[i] = (i % 2 == 0) ? rand() : -rand();
}
return arr;
}
// Function to free the memory allocated for an array
void freeArray(int* arr) {
free(arr);
}
// Function to measure the execution time of a sorting function
double measureSortingTime(void (*sortingFunction)(int[], int), int arr[], int size) {
clock_t start_time = clock();
sortingFunction(arr, size);
clock_t end_time = clock();
double sorting_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;
return sorting_time;
}
// Function to save timing data to a CSV file
void saveTimingData(double data[][NUM_ALGORITHMS], int sizes[], int numSizes, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
return;
}
// Write CSV header
fprintf(file, "Array Size, Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort\n");
// Write timing data
for (int i = 0; i < numSizes; i++) {
fprintf(file, "%d", sizes[i]);
for (int j = 0; j < NUM_ALGORITHMS; j++) {
fprintf(file, ", %f", data[i][j]);
}
fprintf(file, "\n");
}
fclose(file);
}
// Function to apply Gaussian smoothing to an array
void applyGaussianSmoothing(double* data, int size, double sigma) {
double* smoothedData = (double*)malloc(size * sizeof(double));
for (int i = 0; i < size; i++) {
double sum = 0.0;
double weightSum = 0.0;
for (int j = -3; j <= 3; j++) {
int index = i + j;
if (index >= 0 && index < size) {
double weight = exp(-(j * j) / (2.0 * sigma * sigma));
sum += data[index] * weight;
weightSum += weight;
}
}
smoothedData[i] = sum / weightSum;
}
// Copy smoothed data back to the original array
for (int i = 0; i < size; i++) {
data[i] = smoothedData[i];
}
free(smoothedData);
}
int main() {
srand(time(NULL));
int sizes[] = {SMALL_SIZE, MEDIUM_SIZE, LARGE_SIZE};
double randomTimingData[sizeof(sizes) / sizeof(sizes[0])][NUM_ALGORITHMS];
double bestCaseTimingData[sizeof(sizes) / sizeof(sizes[0])][NUM_ALGORITHMS];
double worstCaseTimingData[sizeof(sizes) / sizeof(sizes[0])][NUM_ALGORITHMS];
double mixedCaseTimingData[sizeof(sizes) / sizeof(sizes[0])][NUM_ALGORITHMS];
const char* sortingFunctionNames[] = {"Bubble Sort", "Selection Sort", "Insertion Sort", "Merge Sort", "Quick Sort", "Heap Sort"};
for (int i = 0; i < sizeof(sizes) / sizeof(sizes[0]); i++) {
int* arr = generateRandomArray(sizes[i]);
// Corrected function pointer declaration
void (*sortingFunctions[])(int[], int) = {bubbleSort, selectionSort, insertionSort, wrapperMergeSort, wrapperQuickSort, wrapperHeapSort};
for (int j = 0; j < NUM_ALGORITHMS; j++) {
// Measure and compare sorting times for random, best-case, and worst-case scenarios
randomTimingData[i][j] = measureSortingTime(sortingFunctions[j], arr, sizes[i]);
int* bestCaseArray = generateAscendingArray(sizes[i]);
int* worstCaseArray = generateDescendingArray(sizes[i]);
int* mixedCaseArray = generateMixedArray(sizes[i]);
bestCaseTimingData[i][j] = measureSortingTime(sortingFunctions[j], bestCaseArray, sizes[i]);
worstCaseTimingData[i][j] = measureSortingTime(sortingFunctions[j], worstCaseArray, sizes[i]);
mixedCaseTimingData[i][j] = measureSortingTime(sortingFunctions[j], mixedCaseArray, sizes[i]);
freeArray(bestCaseArray);
freeArray(worstCaseArray);
freeArray(mixedCaseArray);
}
freeArray(arr);
}
// Apply Gaussian smoothing to the timing data
double sigma = 1.0; // You can adjust the sigma value for desired smoothing
for (int i = 0; i < sizeof(sizes) / sizeof(sizes[0]); i++) {
applyGaussianSmoothing(randomTimingData[i], NUM_ALGORITHMS, sigma);
applyGaussianSmoothing(bestCaseTimingData[i], NUM_ALGORITHMS, sigma);
applyGaussianSmoothing(worstCaseTimingData[i], NUM_ALGORITHMS, sigma);
applyGaussianSmoothing(mixedCaseTimingData[i], NUM_ALGORITHMS, sigma);
}
// Store the smoothed timing data in separate CSV files
saveTimingData(randomTimingData, sizes, sizeof(sizes) / sizeof(sizes[0]), "smoothed_random_data.csv");
saveTimingData(bestCaseTimingData, sizes, sizeof(sizes) / sizeof(sizes[0]), "smoothed_best_case_data.csv");
saveTimingData(worstCaseTimingData, sizes, sizeof(sizes) / sizeof(sizes[0]), "smoothed_worst_case_data.csv");
saveTimingData(mixedCaseTimingData, sizes, sizeof(sizes) / sizeof(sizes[0]), "smoothed_mixed_case_data.csv");
return 0;
}