Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
shell_sort2.cpp File Reference

Shell sort algorithm More...

#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <utility>
#include <vector>
Include dependency graph for shell_sort2.cpp:

Namespaces

 sorting
 Sorting algorithms.
 

Functions

template<class T >
void show_data (T *arr, size_t LEN)
 
template<typename T , size_t N>
void show_data (T(&arr)[N])
 
template<typename T >
void sorting::shell_sort (T *arr, size_t LEN)
 
template<typename T , size_t N>
void sorting::shell_sort (T(&arr)[N])
 
template<typename T >
void sorting::shell_sort (std::vector< T > *arr)
 
template<typename T >
int compare (const void *a, const void *b)
 
void test_int (const int NUM_DATA)
 
void test_f (const int NUM_DATA)
 
int main (int argc, char *argv[])
 

Detailed Description

Shell sort algorithm

Author
Krishna Vedala

Function Documentation

◆ 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  // return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
98  // return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)
99 }

◆ main()

int main ( int  argc,
char *  argv[] 
)

Main function

183  {
184  // initialize random number generator - once per program
185  std::srand(std::time(NULL));
186 
187  test_int(100); // test with sorting random array of 100 values
188  std::cout << "Test 1 - 100 int values - passed. \n";
189  test_int(1000); // test with sorting random array of 1000 values
190  std::cout << "Test 2 - 1000 int values - passed.\n";
191  test_int(10000); // test with sorting random array of 10000 values
192  std::cout << "Test 3 - 10000 int values - passed.\n";
193 
194  test_f(100); // test with sorting random array of 100 values
195  std::cout << "Test 1 - 100 float values - passed. \n";
196  test_f(1000); // test with sorting random array of 1000 values
197  std::cout << "Test 2 - 1000 float values - passed.\n";
198  test_f(10000); // test with sorting random array of 10000 values
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  // int array = new int[NUM_DATA];
209  int *data = new int[NUM_DATA];
210  // int array2 = new int[NUM_DATA];
211  int range = 1800;
212 
213  std::srand(time(NULL));
214  for (i = 0; i < NUM_DATA; i++) {
215  // allocate random numbers in the given range
216  data[i] = (std::rand() % range) - (range >> 1);
217  }
218 
219  std::cout << "Unsorted original data: " << std::endl;
220  show_data(data, NUM_DATA);
221  std::clock_t start = std::clock();
222  shell_sort(data, NUM_DATA); // perform sorting
224 
226  << "Data Sorted using custom implementation: " << std::endl;
227  show_data(data, NUM_DATA);
228 
229  double elapsed_time = (end - start) * 1.f / CLOCKS_PER_SEC;
230  std::cout << "Time spent sorting: " << elapsed_time << "s\n" << std::endl;
231 
232  delete[] data;
233  return 0;
234 }
Here is the call graph for this function:

◆ show_data() [1/2]

template<class T >
void show_data ( T *  arr,
size_t  LEN 
)

pretty print array

Parameters
[in]arrarray to print
[in]LENlength of array to print
18  {
19  size_t i;
20 
21  for (i = 0; i < LEN; i++) {
22  std::cout << arr[i] << ", ";
23  }
25 }
Here is the call graph for this function:

◆ show_data() [2/2]

template<typename T , size_t N>
void show_data ( T(&)  arr[N])

pretty print array

Parameters
[in]arrarray to print
[in]Nlength of array to print
32  {
33  show_data(arr, N);
34 }
Here is the call graph for this function:

◆ 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  // int array = new int[NUM_DATA];
147  float *data = new float[NUM_DATA];
148  float *data2 = new float[NUM_DATA];
149  // int array2 = new int[NUM_DATA];
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  /* sort using our implementation */
157  std::clock_t start = std::clock();
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  /* sort using std::qsort */
165  start = std::clock();
166  std::qsort(data2, NUM_DATA, sizeof(data2[0]), compare<float>);
167  end = std::clock();
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]); // ensure that our sorting results match
175  // the standard results
176  }
177 
178  delete[] data;
179  delete[] data2;
180 }
Here is the call graph for this function:

◆ 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  // int array = new int[NUM_DATA];
107  int *data = new int[NUM_DATA];
108  int *data2 = new int[NUM_DATA];
109  // int array2 = new int[NUM_DATA];
110  int range = 1800;
111 
112  for (int i = 0; i < NUM_DATA; i++)
113  data[i] = data2[i] = (std::rand() % range) - (range >> 1);
114 
115  /* sort using our implementation */
116  std::clock_t start = std::clock();
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  /* sort using std::qsort */
124  start = std::clock();
125  std::qsort(data2, NUM_DATA, sizeof(data2[0]), compare<int>);
126  end = std::clock();
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]); // ensure that our sorting results match
134  // the standard results
135  }
136 
137  delete[] data;
138  delete[] data2;
139 }
Here is the call graph for this function:
std::srand
T srand(T... args)
test_f
void test_f(const int NUM_DATA)
Definition: shell_sort2.cpp:145
show_data
void show_data(T *arr, size_t LEN)
Definition: shell_sort2.cpp:18
std::clock_t
std::clock
T clock(T... args)
test_int
void test_int(const int NUM_DATA)
Definition: shell_sort2.cpp:105
std::cout
std::atoi
T atoi(T... args)
std::qsort
T qsort(T... args)
std::rand
T rand(T... args)
data
int data[MAX]
test data
Definition: hash_search.cpp:24
std::endl
T endl(T... args)
compare
Definition: huffman.cpp:28
std::time
T time(T... args)
std::end
T end(T... args)
sorting::shell_sort
void shell_sort(std::vector< T > *arr)
Definition: shell_sort2.cpp:75