Illustrate the growth of the algorithm by: i. providing a table that reports the growth of the sorting algorithm in the implementation above; and ii. plot a graph to illustrate the growth of the sorting algorithm. To illustrate the growth of your sorting algorithm, run the program with at least the following n values (n represents the number of order ids that was generated): 1,000; 5,000; 32,000; 512,000; 1,000,000. The growth of the algorithm is typically measured in millisecond (ms) or microsecond (us) or nanosecond (ns). The growth rate of your sorting algorithm may vary due to your processor speed, memory capacity and etc. Therefore, to illustrate the consistency of the growth rate of your program, you will need to perform and report a minimum of 5 trial runs on each of then values. You may then take the average of the running time for plotting the graph and for the discussion in the section below.
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<bits/stdc++.h>
using namespace std;
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0;
int j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
int main()
{
srand(time(0));
long int n;
cout<<"Enter the number of orders ";
cin>>n;
int ids[n],cost[n],sorted_ids[n],sorted_cost[n];
for(int i=0;i<n;i++)
{
ids[i]=rand();
}
for(int i=0;i<n;i++)
{
cost[i]=rand();
}
while(1)
{
cout<<"1. Unsorted Order ids and their cost"<<endl;
cout<<"2. Sorted Order ids and their cost"<<endl;
cout<<"3. exit"<<endl;
int choice;
cin>>choice;
if(choice == 1)
{
cout<<"Order ID\t Cost"<<endl;
for(int i=0;i<n;i++)
{
cout<<"FD"<<ids[i]<<"\t\t RM"<<cost[i]<<endl;
}
}
else if(choice==2)
{
for(int i=0;i<n;i++)
{
sorted_ids[i]=ids[i];
}
time_t start,end;
time(&start);
mergeSort(sorted_ids,0,n);
for(int i=0;i<n;i++)
{
int j;
for(j=0;j<n;j++)
{
if(ids[j]==sorted_ids[i])
{
sorted_cost[i]=cost[j];
break;
}
}
}
time(&end);
double time_taken = double(end-start);
cout<<"Time taken to mergesort is "<<time_taken<<" sec"<<endl;
cout<<"Order ID\t Cost"<<endl;
for(int i=0;i<n;i++)
{
cout<<"FD"<<sorted_ids[i]<<"\t\t RM"<<sorted_cost[i]<<endl;
}
}
else if(choice==3)
{
break;
}
else
{
cout<<"Invalid choice"<<endl;
}
}
}
Step by step
Solved in 4 steps with 3 images
