Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
140 lines (112 sloc) 4.05 KB
/* Jonathan Plona
* November 15, 2008
* CS 361
* Bonus Project */
#include <iostream> //cin, cout
#include <cstdlib> //rand, srand
#include <sys/time.h> //gettimeofday
#include <fstream> //ofstream
#include <algorithm> //sort
#include "my_sorts.h"
using namespace std;
void fill_array(int a[], int size, int seed);
void get_input(int& size, int& step, int& randseed, int& test_code, string& filename);
void set_switches(bool switches[], int code);
double time_diff(timeval before, timeval after);
double run_sort(void (*sortfunc)(int*, int), int test_data[], int test_size);
inline void stl_sort(int data[], int size) { sort(data, data + size); }
void check_sort(int data[], int size);
const int num_sorts = 7;
int main(int argc, char* argv[])
{
//Pointers to the sort functions.
void (*sorts[num_sorts])(int*, int) = {&insertion_sort, &merge_sort_pub, &iter_merge_sort, &stl_sort, &quicksort1, &quicksort2, &quicksort3};
string sort_names[num_sorts] = {"InsertionSort", "MergeSort-R", "MergeSort-I", "STL Sort", "Quicksort", "QSort-Rand", "QSort-MedOf3"};
bool sort_switches[num_sorts];
int max_size, step, seed, test_code;
string filename = argc == 2 ? argv[1] : "";
get_input(max_size, step, seed, test_code, filename);
set_switches(sort_switches, test_code);
ofstream output("output.csv");
output << "Data Size";
for(int x = 0; x < num_sorts; ++x)
if(sort_switches[x]) output << "," << sort_names[x];
output << endl;
int test_data[max_size];
if(filename != "") {
ifstream in(filename.c_str());
in >> test_data[0];
for(int i = 0; i < max_size; ++i)
in >> test_data[i];
}
double time_taken;
//Loop through test sizes
for(int test_size = step; test_size <= max_size; test_size += step) {
cout << "Testing " << test_size << " elements..." << endl;
output << test_size;
for(int x = 0; x < num_sorts; ++x)
if(sort_switches[x]) {
if(filename == "") fill_array(test_data, test_size, seed); //Reset data
time_taken = run_sort(sorts[x], test_data, test_size);
output << "," << time_taken;
}
output << endl;
}
cout << "Output stored in file 'output.csv'" << endl;
output.close();
return 0;
}
double run_sort(void (*sortfunc)(int*, int), int test_data[], int test_size)
{
timeval before, after;
gettimeofday(&before, NULL);
(*sortfunc)(test_data, test_size);
gettimeofday(&after, NULL);
check_sort(test_data, test_size);
return time_diff(before, after);
}
void set_switches(bool sort_switches[], int code)
{
//Translate test code into array of bools
for(int x = 0; x < num_sorts; ++x) {
if(code % 2 == 0) sort_switches[x] = false;
else sort_switches[x] = true;
code = code >> 1;
}
}
void fill_array(int a[], int size, int seed)
{
srand(seed);
for(int x = 0; x < size; ++x) a[x] = rand();
}
void get_input(int& size, int& step, int& randseed, int& test_code, string& filename)
{
if(filename == "") {
cout << "An array of random elements will be created for you." << endl;
cout << "Please enter the maximum number of test data: " << endl;
cin >> size;
cout << "Please enter the desired step size: " << endl;
cin >> step;
cout << "Please enter a seed integer less than " << INT_MAX << ": " << endl;
cin >> randseed;
} else {
ifstream in(filename.c_str());
in >> size;
step = size;
randseed = 0;
in.close();
}
cout << "Please enter a test code: ";
cin >> test_code;
}
double time_diff(timeval before, timeval after)
{
return (after.tv_sec + after.tv_usec/1000000.0) - (before.tv_sec + before.tv_usec/1000000.0);
}
void check_sort(int data[], int size) {
for(int i = 0; i < size - 1; ++i)
if(data[i] > data[i + 1]) {
cout << "Oops..." << endl;
break;
}
}