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
namespace	sorting
	for working with vectors

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

                                          {
    T arg1 = *static_cast<const T *>(a);
    T arg2 = *static_cast<const T *>(b);
 
    if (arg1 < arg2)
        return -1;
    if (arg1 > arg2)
        return 1;
    return 0;
 
    //  return (arg1 > arg2) - (arg1 < arg2); // possible shortcut
    //  return arg1 - arg2; // erroneous shortcut (fails if INT_MIN is present)
}

main()

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

Main function

                                 {
    // initialize random number generator - once per program
    std::srand(std::time(NULL));
 
    test_int(100);  // test with sorting random array of 100 values
    std::cout << "Test 1 - 100 int values - passed. \n";
    test_int(1000);  // test with sorting random array of 1000 values
    std::cout << "Test 2 - 1000 int values - passed.\n";
    test_int(10000);  // test with sorting random array of 10000 values
    std::cout << "Test 3 - 10000 int values - passed.\n";
 
    test_f(100);  // test with sorting random array of 100 values
    std::cout << "Test 1 - 100 float values - passed. \n";
    test_f(1000);  // test with sorting random array of 1000 values
    std::cout << "Test 2 - 1000 float values - passed.\n";
    test_f(10000);  // test with sorting random array of 10000 values
    std::cout << "Test 3 - 10000 float values - passed.\n";
 
    int i, NUM_DATA;
 
    if (argc == 2)
        NUM_DATA = atoi(argv[1]);
    else
        NUM_DATA = 200;
 
    // int array = new int[NUM_DATA];
    int *data = new int[NUM_DATA];
    // int array2 = new int[NUM_DATA];
    int range = 1800;
 
    std::srand(time(NULL));
    for (i = 0; i < NUM_DATA; i++) {
        // allocate random numbers in the given range
        data[i] = (std::rand() % range) - (range >> 1);
    }
 
    std::cout << "Unsorted original data: " << std::endl;
    show_data(data, NUM_DATA);
    std::clock_t start = std::clock();
    shell_sort(data, NUM_DATA);  // perform sorting
    std::clock_t end = std::clock();
 
    std::cout << std::endl
              << "Data Sorted using custom implementation: " << std::endl;
    show_data(data, NUM_DATA);
 
    double elapsed_time = (end - start) * 1.f / CLOCKS_PER_SEC;
    std::cout << "Time spent sorting: " << elapsed_time << "s\n" << std::endl;
 
    delete[] data;
    return 0;
}

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]	arr	array to print
[in]	LEN	length of array to print

                                   {
    size_t i;
 
    for (i = 0; i < LEN; i++) {
        std::cout << arr[i] << ", ";
    }
    std::cout << std::endl;
}

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]	arr	array to print
[in]	N	length of array to print

                            {
    show_data(arr, N);
}

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.

                                {
    // int array = new int[NUM_DATA];
    float *data = new float[NUM_DATA];
    float *data2 = new float[NUM_DATA];
    // int array2 = new int[NUM_DATA];
    int range = 1000;
 
    for (int i = 0; i < NUM_DATA; i++) {
        data[i] = data2[i] = ((std::rand() % range) - (range >> 1)) / 100.;
    }
 
    /* sort using our implementation */
    std::clock_t start = std::clock();
    shell_sort(data, NUM_DATA);
    std::clock_t end = std::clock();
    double elapsed_time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    std::cout << "Time spent sorting using shell_sort2: " << elapsed_time
              << "s\n";
 
    /* sort using std::qsort */
    start = std::clock();
    std::qsort(data2, NUM_DATA, sizeof(data2[0]), compare<float>);
    end = std::clock();
 
    elapsed_time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    std::cout << "Time spent sorting using std::qsort: " << elapsed_time
              << "s\n";
 
    for (int i = 0; i < NUM_DATA; i++) {
        assert(data[i] == data2[i]);  // ensure that our sorting results match
                                      // the standard results
    }
 
    delete[] data;
    delete[] data2;
}

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.

                                  {
    // int array = new int[NUM_DATA];
    int *data = new int[NUM_DATA];
    int *data2 = new int[NUM_DATA];
    // int array2 = new int[NUM_DATA];
    int range = 1800;
 
    for (int i = 0; i < NUM_DATA; i++)
        data[i] = data2[i] = (std::rand() % range) - (range >> 1);
 
    /* sort using our implementation */
    std::clock_t start = std::clock();
    shell_sort(data, NUM_DATA);
    std::clock_t end = std::clock();
    double elapsed_time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    std::cout << "Time spent sorting using shell_sort2: " << elapsed_time
              << "s\n";
 
    /* sort using std::qsort */
    start = std::clock();
    std::qsort(data2, NUM_DATA, sizeof(data2[0]), compare<int>);
    end = std::clock();
 
    elapsed_time = static_cast<double>(end - start) / CLOCKS_PER_SEC;
    std::cout << "Time spent sorting using std::qsort: " << elapsed_time
              << "s\n";
 
    for (int i = 0; i < NUM_DATA; i++) {
        assert(data[i] == data2[i]);  // ensure that our sorting results match
                                      // the standard results
    }
 
    delete[] data;
    delete[] data2;
}

Here is the call graph for this function: