Shell sort algorithm
More...
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <utility>
#include <vector>
◆ compare()
template<typename T >
int compare |
( |
const void * |
a, |
|
|
const void * |
b |
|
) |
| |
function to compare sorting using cstdlib's qsort
88 T arg1 = *
static_cast<const T *
>(a);
89 T arg2 = *
static_cast<const T *
>(b);
◆ main()
int main |
( |
int |
argc, |
|
|
char * |
argv[] |
|
) |
| |
Main function
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";
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";
204 NUM_DATA =
atoi(argv[1]);
209 int *
data =
new int[NUM_DATA];
214 for (i = 0; i < NUM_DATA; i++) {
226 <<
"Data Sorted using custom implementation: " <<
std::endl;
229 double elapsed_time = (
end - start) * 1.f / CLOCKS_PER_SEC;
◆ 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 |
21 for (i = 0; i < LEN; i++) {
◆ 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.
147 float *
data =
new float[NUM_DATA];
148 float *data2 =
new float[NUM_DATA];
152 for (
int i = 0; i < NUM_DATA; i++) {
153 data[i] = data2[i] = ((
std::rand() % range) - (range >> 1)) / 100.;
160 double elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
161 std::cout <<
"Time spent sorting using shell_sort2: " << elapsed_time
169 elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
170 std::cout <<
"Time spent sorting using std::qsort: " << elapsed_time
173 for (
int i = 0; i < NUM_DATA; i++) {
174 assert(
data[i] == data2[i]);
◆ test_int()
void test_int |
( |
const int |
NUM_DATA | ) |
|
Test implementation of shell_sort on integer arrays by comparing results against std::qsort.
107 int *
data =
new int[NUM_DATA];
108 int *data2 =
new int[NUM_DATA];
112 for (
int i = 0; i < NUM_DATA; i++)
119 double elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
120 std::cout <<
"Time spent sorting using shell_sort2: " << elapsed_time
128 elapsed_time =
static_cast<double>(
end - start) / CLOCKS_PER_SEC;
129 std::cout <<
"Time spent sorting using std::qsort: " << elapsed_time
132 for (
int i = 0; i < NUM_DATA; i++) {
133 assert(
data[i] == data2[i]);