CS375-SPG15-Project/mergesort.cpp at master · meibenny/CS375-SPG15-Project · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/* Implementation of merge sort.
 *
 */
#include "timer.cpp"
#include "auxiliary_functions.cpp"
#include <vector>
#include <climits>
using namespace std;

//Function prototypes
vector<int> mergeSort(vector<int> & a);
vector<int> merge(vector<int> & vec, vector<int> & left, vector<int> & right);


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

	vector<int> numbers;
	vector<int> holder;
	if(!correctArgumentFormat(argc, argv))
	{
		exit(1);
	}
	string input_file = argv[1];
	int success;
	success = readInputFile(input_file, holder);
	if(success != 0)
	{
		cout<<"error reading input file. exit."<<endl;
		exit(1);
	}

	/*
	 *  Begin timing sequence of:
	 *  Mergesort
	 */
	int numRuns = 5;
	struct timeval start[numRuns];
	struct timeval end[numRuns];

	vector<float> time;
	for(int i = 0; i < numRuns; i++)
	{
		numbers.clear();
		numbers.assign(holder.begin(), holder.end());
		start[i] = startTime(&start[i]);

		//Perform a mergesort
		numbers = mergeSort(numbers);
		end[i] = endTime(&end[i]);
		time.push_back(calculateTime(&start[i], &end[i]));
	}
	calcAvgTime(time);
	/*
	 *  End timing sequence of:
	 *  Mergesort
	 */

	string output_file = argv[2];
	success = outputToFile(output_file, numbers);
	if(success != 0)
	{
		cout<<"error outputtting to file. exit."<<endl;
		exit(1);
	}


	return 0;
}
vector<int> mergeSort(vector<int> & a)
{
	//Return vector if only one element
	if(a.size() == 1)
	{
		return a;
	}
	//Split the vector in half
	auto iter = a.begin() + (a.size() / 2);
	vector<int> left(a.begin(), iter);
	vector<int> right(iter, a.end());

	//Recursively call merge sort
	left = mergeSort(left);
	right = mergeSort(right);

	return (merge(a, left, right));


}
vector<int> merge(vector<int> & vec, vector<int> & left, vector<int> & right)
{

	vector<int> mergeVec;
	u_int l_rover = 0, r_rover = 0;

	while(l_rover < left.size() && r_rover < right.size())
	{
		//Take the smaller of the two available values
		if(left[l_rover] < right[r_rover])
		{
			mergeVec.push_back(left[l_rover]);
			l_rover++;
		}
		else
		{
			mergeVec.push_back(right[r_rover]);
			r_rover++;
		}
	}

	//Place the numbers left over into the return vector
	while(l_rover < left.size())
	{
		mergeVec.push_back(left[l_rover]);
		l_rover++;

	}
	while(r_rover < right.size())
	{
		mergeVec.push_back(right[r_rover]);
		r_rover++;

	}

	return mergeVec;
}