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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
/**
 * Igor Vrcel
 * Project 2
 * CSCI 362 
 */
#include <cstdlib> 
#include <ctime> 
#include <iostream>

using namespace std;

#define N 12800   //size of input sequence

void print(int a[]);

void insertionSort(int a[],int left, int right);

void mergeSort(int a[]);
void mergeSort(int a[], int tmpArray[], int left, int right);
void merge(int a[],int tmpArray[],int leftPos, int rightPos, int rightEnd);

void quicksort(int a[]);
void quicksort(int a[], int left, int right);
int median3(int a[], int left, int right);

int count = 0;

int main() 
{ 

	int a[N], input;
	double diff;
	clock_t start,end;   //initialize Begin and End for the timer

    srand(time(NULL));

	//load the array of size N(defined globally) with random ints <1-20000>
	for(int index=0; index < N; index++) 
       a[index] = (rand()%20000)+1; 

	cout <<"******************"<<endl;
	cout <<"1. Insertion Sort" << endl;
	cout <<"2. Quicksort" << endl;
	cout <<"3. Mergesort" << endl;
	cout <<"4. Quit" << endl;
	cout <<"******************"<<endl;
	cout <<"Select sorting algorithm: ";
	cin >> input;
	
	switch(input)
	{
		case 1: start = clock()*CLK_TCK;     //start the timer 
				insertionSort(a,0,N-1);
				end = clock()*CLK_TCK;       //stop the timer 
				diff = (end - start)/1000;   //the number of ticks from Begin to End /1000 to get milliseconds
				cout<<"Number of steps: "<<count<<endl;
				cout << "Running time: "<<diff<< " milliseconds."<<endl;
				//print(a);  //uncomment to see sorted list
				
				break;
		case 2: start = clock()*CLK_TCK;
			    quicksort(a);
			    end = clock()*CLK_TCK;
				diff = (end - start)/1000;
				cout<<"Number of steps: "<<count<<endl;
				cout << "Running time: "<<diff<< " milliseconds."<<endl;
				//print(a);  //uncomment to see sorted list
				break;
		case 3: start = clock()*CLK_TCK;
			    mergeSort(a);
			    end = clock()*CLK_TCK;
				diff = (end - start)/1000;
				cout<<"Number of steps: "<<count<<endl;
				cout << "Running time: "<<diff<< " milliseconds."<<endl;
				//print(a);  //uncomment to see sorted list
				break;
		case 4: cout << "Terminating..."<<endl;
			    exit(0);
			    break;

		default: cout << "Error, invalid input" <<endl;	
	}

	   
	   
}
/**
 * Print contents of array
 */
void print(int a[])
{
	int size=0;
	for(int p = 0; p < N; p++){
	   cout << a[p] << endl;
	   size++;
	}
}


/**
 * Simple insertion sort
 */
void insertionSort(int a[],int left, int right)
{
	int j, tmp;

	for(int p = left; p <= right; p++)
	{
		tmp = a[p];
		for(j=p;j>0 && tmp < a[j-1];j--){
			a[j] = a[j-1];
			count++;
		}
		a[j] = tmp;
	}
	
}

/**
 * Mergesort algorithm (driver)
 */

void mergeSort(int a[])
{
	int tmpArray[N];
	
	mergeSort(a,tmpArray,0,N-1);
}

/**
 * Internal method that makes recursive calls.
 * tmpArray holds merged result
 * a contains the numbers to be compared
 * left is left-most index of the subarray
 * right is the right-most index of the subarray
 */
void mergeSort(int a[], int tmpArray[], int left, int right)
{
	if(left < right)
	{
		int center = (left + right)/2;
		mergeSort(a,tmpArray,left,center);
		mergeSort(a,tmpArray,center+1, right);
		merge(a,tmpArray,left,center+1,right);
	}
}
/**
 * Internal method that merges two sorted halves of a subarray
 * tmpArray is an array to place merged result
 * a contains the numbers to be compared
 * leftPos is the left-most index of the subarray
 * rightPos is the index of the start of the second half
 * rightEnd is the right-most index of the subarray
 */
void merge(int a[],int tmpArray[],int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	//main loop
	while(leftPos <= leftEnd && rightPos <= rightEnd)
	{
		if(a[leftPos] <= a[rightPos])
		{
			tmpArray[tmpPos++] = a[leftPos++];
			count+=1;
		}
		else 
		{
			tmpArray[tmpPos++] = a[rightPos++];
			count+=1;
		}
	}

	while(leftPos <= leftEnd)   //copy rest of first half
	{
		tmpArray[tmpPos++] = a [leftPos++];
		count+=1;
	}

	while(rightPos <= rightEnd) //copy rest of right half
	{
		tmpArray[tmpPos++] = a[rightPos++];
		count+=1;
	}

	//copy tmpArray back
	for(int i = 0; i<numElements; i++, rightEnd--)
	{
		a[rightEnd] = tmpArray[rightEnd];
		count++;
	}

}
/**
 * Quicksort algorithm (driver)
 */
void quicksort(int a[])
{
	quicksort(a,0,N-1);
}
/**
 * Internal quicksort method that makes recursive calls
 * Uses media-of-three partitioning and a cutoff of 10
 * a contains the numbers to be compared
 * left is the left-most index of the subarray
 * right is the right-most index of the subarray
 */
void quicksort(int a[], int left, int right)
{
	if(left+10 <= right)
	{
		int pivot = median3(a,left,right);

		//begin partitioning
		int i = left, j = right - 1;
		for(;;)
		{
			while(a[++i]<pivot) {}
			while(pivot < a[--j]) {}
			if(i<j){
				swap(a[i],a[j]);
				count++;
			}
			else
				break;
		}
		count++;
		swap(a[i], a[right-1]); //restore pivot
		quicksort(a,left,i-1);  //sort small elements
		quicksort(a,i+1,right); //sort large elements		
	}
	else //do an insertion sort on the subarray
	    insertionSort(a,left,right);		
}

/**
 * Return median of left,center, and right
 * Order these and hide the pivot
 */
int median3(int a[], int left, int right)
{
	int center = (left +right)/2;
	if(a[center] < a[left]){
		swap(a[left],a[center]);
		count++;
	}
	if(a[right] < a[left]){
		swap(a[left],a[right]);
		count++;
	}
	if(a[right] < a[center]){
		swap(a[center],a[right]);
		count++;
	}
	//place pivot at position right-1
	swap(a[center],a[right-1]);
	return a[right-1];

}