Display a C++ program that compares the execution times of Heap, Insertion Sort and Merge Sort for inputs of different size.

QUESTION

Display a C++ program that compares the execution times of Heap, Insertion Sort and Merge Sort for inputs of different size. The time, in seconds, must be formatted with at least two decimal numbers.

First, we must randomly generate inputs of different size, but the “same input” generated, must be applied to the three sorts. However, the random inputs must be copied to three different arrays, one for each sort, to make sure that they are not previously sorted by another sorting technique.

 

 

SUMMARY

A random array is generated and is taken as input. This array is then passed to sorting techniques: heap sort, merge sort, and insertion sort. To figure out which technique is more efficient, the time taken to process the array for each of the three algorithms is calculated as execution times and is printed.

 

EXPLANATION

Insertion Sort (execution times) : 

a) Best Case : O(n)

b) Average Case : O(n^2)

c) Worst Case : O(n^2)

 

Merge Sort (execution times) : 

a) Best Case : O(nlogn)

b) Average Case : O(nlogn)

c) Worst Case : O(nlogn)

 

Heap Sort (execution times) : 

a) Best Case : O(nlogn)

b) Average Case : O(nlogn)

c) Worst Case : O(nlogn)

 

The better time complexity would be shown by either merge or heap sort.

 

 

CODE

#include <bits/stdc++.h>
using namespace std;
#include <vector>
void mergesort(vector<int>& l, vector<int>& r, vector<int>& nums);
void insertionsort(vector<int> &nums)
{
for (auto it=nums.begin(); it != nums.end(); it++)
{ 
/* to find the upper bound */
auto ins_point = upper_bound(nums.begin(), it, *it);
rotate(ins_point, it, it+1); 
}
}
void sort(vector<int> &nums)
{
if (nums.size() <= 1) 
return;
int midd = nums.size() / 2;
vector<int> left;
vector<int> right;
for (size_t i = 0; i < midd;i++)
left.push_back(nums[i]);
/* for copying right half elements */
for (size_t i = 0; i < (nums.size()) - midd; i++)
right.push_back(nums[midd + i]);
sort(left);
sort(right);
/* merging the 2 */
mergesort(left,right,nums);
}
void mergesort(vector<int>& l, vector<int>& r, vector<int>& nums)
{
int ls = l.size();
/* to have the right array size */
int rs = r.size();
int i=0,j=0,k=0;

while (j < ls && k < rs) 
{
if (l[j] < r[k])
{
nums[i] = l[j];
j++;
}
else
{
nums[i] = r[k];
k++;
}
i++;
}
/* copying remaining elements of the left array */
while (j < ls)
{
nums[i] = l[j];
j++;
i++;
}
/* copying the remaining elements of the right array*/
while (k<rs)
{
nums[i]=r[k];
k++; 
i++;
}
}
void Heapify(int nums[], int n, int j)
{
int large = j; 
int lt = 2 * j + 1; 
int rt = 2 * j + 2; 
if (lt < n && nums[lt] > nums[large])
large = lt;
if (rt < n && nums[rt] > nums[large])
large = rt;
if (large != j) {
swap(nums[j], nums[large]);
Heapify(nums, n, large);
}
}
void heapsort(int nums[], int n)
{
for (int j = n / 2 - 1; j >= 0; j--)
Heapify(nums, n, j);
for (int j = n - 1; j >= 0; j--)
{
swap(nums[0],nums[j]);
Heapify(nums, j, 0);
}
}
int main()
{
vector<int> nums1,nums2;
int nums3[1000000];
for(int j=0;j<1000000;j++)
{
int y=rand()%50;
nums1.push_back(y);
nums2.push_back(y);
nums3[j]=y;
}
time_t s11,e11;
time(&s11);
insertionsort(nums1);
time(&e11);
double time_insertion=double(e11-s11)*1000;
cout<<"Time taken for Insertion sort (in milliseconds) : ";
cout<<fixed<<time_insertion<<setprecision(5);
cout<<endl<<endl;


time_t S2,E2;
time(&S2);
sort(nums2);
time(&E2);
double time_merge=double(E2-S2)*1000;
cout<<"Time taken for Merge sort (in milliseconds) : ";
cout<<fixed<<time_merge<<setprecision(5);
cout<<endl<<endl;


time_t S3,E3;
time(&S3);
heapsort(nums3,1000000);
time(&E3);
double time_heap=double(E3-S3)*1000;
cout<<"Time taken for Heap sort (in milliseconds) : ";
cout<<fixed<<time_heap<<setprecision(5);
cout<<endl<<endl;
}

 

OUTPUT

 

 

Also, read perform the XOR-based long division (polynomial division) on 1100110000111002(15 bits) and a divisor 10112