#include #include #include #include #include #include using namespace std; void merge(string a[], string b[], int left, int mid, int right) { int nL = mid - left + 1; int nR = right - mid; string leftA[nL], rightA[nR], leftB[nL], rightB[nR]; for(int i = 0; i < nL; i++) { leftA[i] = a[nL+i]; leftB[i] = b[nL+i]; } for(int i = 0; i < nR; i++) { rightA[i] = a[mid+i+1]; rightB[i] = b[mid+i+1]; } int i = 0, j = 0, k = left; while(i < nL && j < nR) { if(leftA[i] <= rightA[j]) { a[k] = leftA[i]; b[k] = leftB[i]; i++; } else { a[k] = rightA[j]; b[k] = rightB[j]; j++; k++; } } while(i < nL) { a[k] = leftA[i]; b[k] = leftB[i]; i++; k++; } while(j < nR) { a[k] = rightA[j]; b[k] = rightB[j]; j++; k++; } } void mergeSort(string a[], string b[], int left, int right) { int mid; if(left < right) { mid = left + (right-1)/2; mergeSort(a,b,left,mid); mergeSort(a,b,mid+1,right); merge(a,b,left,mid,right); } } int menu() { int ch; cout<<"1. Time for sorting\n2. Unsorted List\n3. Sort\n4. Exit\nEnter Choice: "; cin>>ch; return ch; } int main() { int n; cout<<"Enter number of order ids: "; cin>>n; srand((unsigned) time(0)); string orderid[n], cost[n], originalorderid[n], originalcost[n]; for(int i = 0; i < n; i++) { int randNum = (rand()%n)+1; orderid[i] = "FD" + to_string(randNum); originalorderid[i] = orderid[i]; float a = 1.0; float randCostNum = (float(rand())/float(RAND_MAX) * a); randCostNum = (int)(randCostNum * 100 + 0.5); randCostNum = (float)randCostNum / 100; cost[i] = "RM" + to_string(randCostNum); originalcost[i] = cost[i]; } time_t start, end; time(&start); ios_base::sync_with_stdio(false); mergeSort(orderid, cost, 0, n-1); time(&end); double timeTaken = double(end - start); bool w = true; while(w) { int choice = menu(); switch(choice) { case 1 : cout << "Time taken by merge sort is : "<< timeTaken << setprecision(5); cout << " sec " << endl; break; case 2 : for(int i = 0; i < n; i++) { cout<
#include<iostream>
#include<string>
#include <cstdlib>
#include <ctime>
#include<time.h>
#include <iomanip>
using namespace std;
void merge(string a[], string b[], int left, int mid, int right) {
int nL = mid - left + 1;
int nR = right - mid;
string leftA[nL], rightA[nR], leftB[nL], rightB[nR];
for(int i = 0; i < nL; i++) {
leftA[i] = a[nL+i];
leftB[i] = b[nL+i];
}
for(int i = 0; i < nR; i++) {
rightA[i] = a[mid+i+1];
rightB[i] = b[mid+i+1];
}
int i = 0, j = 0, k = left;
while(i < nL && j < nR) {
if(leftA[i] <= rightA[j]) {
a[k] = leftA[i];
b[k] = leftB[i];
i++;
}
else {
a[k] = rightA[j];
b[k] = rightB[j];
j++;
k++;
}
}
while(i < nL) {
a[k] = leftA[i];
b[k] = leftB[i];
i++;
k++;
}
while(j < nR) {
a[k] = rightA[j];
b[k] = rightB[j];
j++;
k++;
}
}
void mergeSort(string a[], string b[], int left, int right) {
int mid;
if(left < right) {
mid = left + (right-1)/2;
mergeSort(a,b,left,mid);
mergeSort(a,b,mid+1,right);
merge(a,b,left,mid,right);
}
}
int menu() {
int ch;
cout<<"1. Time for sorting\n2. Unsorted List\n3. Sort\n4. Exit\nEnter Choice: ";
cin>>ch;
return ch;
}
int main() {
int n;
cout<<"Enter number of order ids: ";
cin>>n;
srand((unsigned) time(0));
string orderid[n], cost[n], originalorderid[n], originalcost[n];
for(int i = 0; i < n; i++) {
int randNum = (rand()%n)+1;
orderid[i] = "FD" + to_string(randNum);
originalorderid[i] = orderid[i];
float a = 1.0;
float randCostNum = (float(rand())/float(RAND_MAX) * a);
randCostNum = (int)(randCostNum * 100 + 0.5);
randCostNum = (float)randCostNum / 100;
cost[i] = "RM" + to_string(randCostNum);
originalcost[i] = cost[i];
}
time_t start, end;
time(&start);
ios_base::sync_with_stdio(false);
mergeSort(orderid, cost, 0, n-1);
time(&end);
double timeTaken = double(end - start);
bool w = true;
while(w) {
int choice = menu();
switch(choice) {
case 1 : cout << "Time taken by merge sort is : "<< timeTaken << setprecision(5);
cout << " sec " << endl;
break;
case 2 : for(int i = 0; i < n; i++) {
cout<<originalorderid[i]<<"\t\t"<<originalcost[i]<<endl;
}
break;
case 3 : for(int i = 0; i < n; i++) {
cout<<orderid[i]<<"\t\t"<<cost[i]<<endl;
}
break;
case 4 : w = false;
break;
default: w = false;
}
}
return 0;
}
Write a pseudocode for your solution above. Do ensure that the pseudocode models the entire logical flow of your program.
d. Illustrate the growth of the
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 (µs) 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 the n values. You
may then take the average of the running time for plotting the graph and for the discussion in the section below.
Step by step
Solved in 2 steps
