Newer
Older
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
#include <iostream>
#include <ctime>
#include <chrono>
using namespace std;
void gnomeSort(int arr[], int size);
void combSort(int *arr, int size);
int main() {
int sizes[] = {1000, 10000, 20000, 40000, 80000, 100000, 200000};
for (auto &size: sizes) {
// Generate an array filled with random elements to be sorted by the algorithm
srand(time(nullptr));
// Create 5 different arrays with the same size and get the average time
long total_time_gnome = 0;
long total_time_comb = 0;
for (int i = 0; i < 5; i++) {
int arr[size];
for (int j = 0; j < size; j++) {
arr[j] = rand();
}
// Copy the array to be sorted by the comb sort
int arr_comb[size];
for (int j = 0; j < size; j++) {
arr_comb[j] = arr[j];
}
// Start the timer
auto start = chrono::high_resolution_clock::now();
// Sort the array using gnome sort
gnomeSort(arr, size);
// Stop the timer
auto stop = chrono::high_resolution_clock::now();
// Timer for comb sort
auto start2 = chrono::high_resolution_clock::now();
// Sort the array using comb sort
combSort(arr_comb, size);
// Stop the timer
auto stop2 = chrono::high_resolution_clock::now();
// Calculate the time
total_time_gnome += chrono::duration_cast<chrono::milliseconds>(stop - start).count();
total_time_comb += chrono::duration_cast<chrono::milliseconds>(stop2 - start2).count();
}
cout << "Gnome sort: time for " << size << " elements: " << total_time_gnome / 5 << " milliseconds" << endl;
cout << "Comb sort: time for " << size << " elements: " << total_time_comb / 5 << " milliseconds" << endl;
}
return 0;
}
void gnomeSort(int *arr, int size) {
// Sort the array using gnome sort
int index = 0;
while (index < size) {
if (index == 0) index++;
if (arr[index] >= arr[index - 1]) {
index++;
} else {
int temp;
temp = arr[index];
arr[index] = arr[index - 1];
arr[index - 1] = temp;
index--;
}
}
}
void combSort(int *arr, int size) {
// Sort the array using comb sort
int gap = size;
bool swapped = true;
while (gap != 1 || swapped) {
gap = max(1, (int) (gap / 1.3));
swapped = false;
for (int i = 0; i < size - gap; i++) {
if (arr[i] > arr[i + gap]) {
int temp;
temp = arr[i];
arr[i] = arr[i + gap];
arr[i + gap] = temp;
swapped = true;
}
}
}
}