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
|
#include <time.h>
#include <iostream>
#include <stdio.h>
void MergeSort(int A[], int left, int right);
void Merge(int [], int left, int mid, int right);
void InsertionSort(int B[], int size);
void printA(int A[], int n);
using namespace std;
int main()
{
clock_t start1, finish1;
clock_t start2, finish2;
float TotalTime1=0; // merge sort time
float TotalTime2=0; // insertion sort time
int n=20; // input size
int MaxRep=1;
for(int Rep=1; Rep<=MaxRep; Rep++){
//create and intialize A with size n
int *A, *B;
srand ( time(NULL) );
A=new int[n];
B=new int[n];
for(int i=0; i<n; i++) {A[i]=(rand() /100); B[i]=A[i];}
// print the array before and after soring
if(n<25){ cout << "Array before sorting : " << endl; printA(A,n);}
start1 = clock(); //Start timing1
MergeSort(A,0,n-1);
finish1 = clock(); //Finish timing1
if(n<25){ cout << "Array after merge sort : " << endl; printA(A,n);}
start2 = clock(); //Start timing2
InsertionSort(B,n);
finish2 = clock(); //Finish timing2
if(n<25){ cout << "Array after insertion sort : " << endl; printA(B,n);}
TotalTime1+=(finish1 -start1);
TotalTime2+=(finish2 -start2);
}
cout <<endl << "Average Time Taken by Merge Sort = \t" << TotalTime1/MaxRep;
cout <<endl << "Average Time Taken by Insertion Sort = \t" << TotalTime2/MaxRep;
cout <<endl;
return 0;
}
void printA(int A[], int n){
cout << endl << "A=[";
for(int i=0; i<n; i++) cout << A[i] << ", ";
cout << " ]" << endl<< endl;
}
void MergeSort(int A[], int left, int right){
if (left < right) {
int mid = ((left + right) / 2);
MergeSort(A, left, mid);
MergeSort(A, mid+1, right);
Merge(A, left, mid, right);
}
}
void Merge(int A[], int left, int mid, int right)
{
int i = left;
int j = mid + 1;
int *tmp = new int[right - left + 1];
int k = 0;
while ((i <= mid) && (j <= right))
{
if (A[i] < A[j]) tmp[k++] = A[i++];
else tmp[k++] = A[j++];
}
while (i <= mid)
tmp[k++] = A[i++];
while (j <= right)
tmp[k++] = A[j++];
int x = left;
while(x<= right){
A[x] = tmp[x];
x++;
}
}
void InsertionSort(int B[], int size)
{
int key, j;
for (int i = 0; i <= size; i++)
{
key = B[i];
j = i - 1;
while ( j >= -1 && B[j] > key)
{
B[j+1] = B[j];
j = j - 1;
}
B[j+1] = key;
}
}
|
