Shell sort algorithm
More...
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <utility>
#include <vector>
|
namespace | sorting |
| for working with vectors
|
|
◆ compare()
template<typename T >
int compare |
( |
const void * | a, |
|
|
const void * | b ) |
function to compare sorting using cstdlib's qsort
87 {
88 T arg1 = *static_cast<const T *>(a);
89 T arg2 = *static_cast<const T *>(b);
90
91 if (arg1 < arg2)
92 return -1;
93 if (arg1 > arg2)
94 return 1;
95 return 0;
96
97
98
99}
◆ main()
int main |
( |
int | argc, |
|
|
char * | argv[] ) |
Main function
183 {
184
186
188 std::cout <<
"Test 1 - 100 int values - passed. \n";
190 std::cout <<
"Test 2 - 1000 int values - passed.\n";
192 std::cout <<
"Test 3 - 10000 int values - passed.\n";
193
195 std::cout <<
"Test 1 - 100 float values - passed. \n";
197 std::cout <<
"Test 2 - 1000 float values - passed.\n";
199 std::cout <<
"Test 3 - 10000 float values - passed.\n";
200
201 int i, NUM_DATA;
202
203 if (argc == 2)
204 NUM_DATA =
atoi(argv[1]);
205 else
206 NUM_DATA = 200;
207
208
209 int *
data =
new int[NUM_DATA];
210
211 int range = 1800;
212
214 for (i = 0; i < NUM_DATA; i++) {
215
217 }
218
222 shell_sort(
data, NUM_DATA);
224
226 <<
"Data Sorted using custom implementation: " <<
std::endl;
228
229 double elapsed_time = (
end - start) * 1.f / CLOCKS_PER_SEC;
231
233 return 0;
234}
int data[MAX]
test data
Definition hash_search.cpp:24
static void test_int()
Definition quick_sort_3.cpp:138
void test_f(const int NUM_DATA)
Definition shell_sort2.cpp:145
void show_data(T *arr, size_t LEN)
Definition shell_sort2.cpp:18
◆ show_data() [1/2]
template<class T >
void show_data |
( |
T * | arr, |
|
|
size_t | LEN ) |
pretty print array
- Parameters
-
[in] | arr | array to print |
[in] | LEN | length of array to print |
18 {
19 size_t i;
20
21 for (i = 0; i < LEN; i++) {
23 }
25}
◆ show_data() [2/2]
template<typename T , size_t N>
void show_data |
( |
T(&) | arr[N] | ) |
|
pretty print array
- Parameters
-
[in] | arr | array to print |
[in] | N | length of array to print |
◆ test_f()
void test_f |
( |
const int | NUM_DATA | ) |
|
Test implementation of shell_sort on float arrays by comparing results against std::qsort.
145 {
146
147 float *
data =
new float[NUM_DATA];
148 float *data2 = new float[NUM_DATA];
149
150 int range = 1000;
151
152 for (int i = 0; i < NUM_DATA; i++) {
153 data[i] = data2[i] = ((
std::rand() % range) - (range >> 1)) / 100.;
154 }
155
156
158 shell_sort(
data, NUM_DATA);
160 double elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
161 std::cout <<
"Time spent sorting using shell_sort2: " << elapsed_time
162 << "s\n";
163
164
168
169 elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
170 std::cout <<
"Time spent sorting using std::qsort: " << elapsed_time
171 << "s\n";
172
173 for (int i = 0; i < NUM_DATA; i++) {
174 assert(
data[i] == data2[i]);
175
176 }
177
179 delete[] data2;
180}
Definition huffman.cpp:36
◆ test_int()
void test_int |
( |
const int | NUM_DATA | ) |
|
Test implementation of shell_sort on integer arrays by comparing results against std::qsort.
105 {
106
107 int *
data =
new int[NUM_DATA];
108 int *data2 = new int[NUM_DATA];
109
110 int range = 1800;
111
112 for (int i = 0; i < NUM_DATA; i++)
114
115
117 shell_sort(
data, NUM_DATA);
119 double elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
120 std::cout <<
"Time spent sorting using shell_sort2: " << elapsed_time
121 << "s\n";
122
123
127
128 elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
129 std::cout <<
"Time spent sorting using std::qsort: " << elapsed_time
130 << "s\n";
131
132 for (int i = 0; i < NUM_DATA; i++) {
133 assert(
data[i] == data2[i]);
134
135 }
136
138 delete[] data2;
139}