Write a C++ program that compares the execution time of Insertion Sort and Merge
ID: 3577289 • Letter: W
Question
Write a C++ program that compares the execution time of Insertion Sort and Merge Sort for inputs of different size.
The implementation of Insertion and Merge Sorts are the same as we discussed in class.
First we must randomly generate inputs of different size, but a “same input” generated, must be applied to both sorts.
The output of your program should look like:
Input Size
Insertion Sort (time in seconds)
Merge Sort (time in seconds)
100
xx.xx
xx.xx
1000
xx.xx
xx.xx
10,000
xx.xx
xx.xx
50,000
xx.xx
xx.xx
100,000
xx.xx
xx.xx
200,000
xx.xx
xx.xx
void Insertion (int A[ ], int n) // in reality the elements to be sorted are indexed from
// index 1 to index n
{
int i,j, temp;
A[0]=-32768; //smallest possible integer using 2 bytes integer representation
for (i=1; i<=n, i++) {
j=i;
(1) while ( A[j] < A[j-1]) { // swap
temp=A[j];
A[j]=A[j-1];
A[j-1]=temp;
j--;
}
}
}
void Merge (int A[ ], int low, int mid, int high) // we assume that B is a global // variable
{
int l=low, i=low, h=mid+1, k; // i is the index corresponding to array B
while ((l <=mid) && (h <=high)) { // exactly one of the pointers will reach its limit
if (A[l] <=A[h]) {
B[i]=A[l]; // push A[l] to B
l++; //increment l
}
else { // we must A[h] to B
B[i]=A[h];
h++;
}
i++;
} //end while
// now one of the pointer has reached its limit so we push the remaining
// elements into B.
if (l > mid) { // we pushed the remaining elements starting at A[h]
for (k=h: k <=high; k++) {
B[i]=A[k];
i++;
} // end for
else for (k=l; k <= mid; k++) // we push remaining elements starting at A[l]
B[i]=A[k];
i++;
} // end else
// Next we move B[low:high] to A[low:high]
for (k=low; k <=high; k++) {
A[k]=B[k];
} // enf for
} // end algorithm
We are now ready to sort using Mergesort
A12: void Mergesort (int low, int high)
{
if (low < high) { // if the sub-list has more than one element
int mid=(low + high)/2;
(1) Mergesort (low, mid); // we call Mergesort for the first half
(2) Mergesort (mid+1, high); we call Mergesort for the second half
// at this point the two halves are sorted
(3) Merge (A, low, mid, high);
}
} // end algorithm
Input Size
Insertion Sort (time in seconds)
Merge Sort (time in seconds)
100
xx.xx
xx.xx
1000
xx.xx
xx.xx
10,000
xx.xx
xx.xx
50,000
xx.xx
xx.xx
100,000
xx.xx
xx.xx
200,000
xx.xx
xx.xx
Explanation / Answer
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
#define CLK_TCK 10000
long length = 1000;
const long max_length = 200000;
int list[max_length];
void ReadFile()
{
ifstream fin("random.dat", ios::binary);
for (long i = 0; i < length; i++)
{
fin.read((char*)&list[i], sizeof(int));
}
fin.close();
}
void SortInsertion()
{
int temp;
for(long i = 1; i < length; i++)
{
temp = list[i];
long j;
for(j = i-1; j >= 0 && list[j] > temp; j--)
{
list[j+1] = list[j];
}
list[j+1] = temp;
}
}
void Merge(int *a, int l, int h, int m)
{
int i, j, k, c[300000];
i = l;
k = l;
j = m + 1;
while (i <= m && j <= h)
{
if (a[i] < a[j])
{
c[k] = a[i];
k++;
i++;
}
else
{
c[k] = a[j];
k++;
j++;
}
}
while (i <= m)
{
c[k] = a[i];
k++;
i++;
}
while (j <= h)
{
c[k] = a[j];
k++;
j++;
}
for (i = l; i < k; i++)
{
a[i] = c[i];
}
}
void Mergesort(int *a, int l, int h)
{
int m;
if (l < h)
{
m=(l+h)/2;
Mergesort(a,l,m);
Mergesort(a,m+1,h);
Merge(a,l,h,m);
}
return;
}
int main()
{
double t1, t2,t3,t4;
cout << "Input Size " <<"Insertion Sort (time in seconds) Merge Sort (time in seconds) ";
for (length = 100; length <= max_length; )
{
cout<<length << " ";
ReadFile();
t1 = clock();
SortInsertion();
t2 = clock();
cout << (t2 - t1)/CLOCKS_PER_SEC << " sec ";
ReadFile();
t3 = clock();
Mergesort(list,0,length-1);
t4 = clock();
cout << (t4 - t3)/CLOCKS_PER_SEC << " sec ";
switch (length)
{
case 100 :
length = 1000;break;
case 1000 :
length = 10000;
break;
case 10000 :
length = 50000;
break;
case 50000 :
length = 100000;
break;
case 100000 :
length = 200000;
break;
case 200000 :
length = 300000;
break;
}
}
return 0;
}
==================================================================================
Output:
akshay@akshay-Inspiron-3537:~/Chegg$ g++ sortingalo.c
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Input Size Insertion Sort (time in seconds) Merge Sort (time in seconds)
100 1e-06 sec 1e-05 sec
1000 9e-06 sec 9.5e-05 sec
10000 5.7e-05 sec 0.001097 sec
50000 0.000276 sec 0.006123 sec
100000 0.000524 sec 0.012814 sec
200000 0.001023 sec 0.027094 sec
==================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.