Description. This assignment takes an experimental approach to studying the effi
ID: 3785172 • Letter: D
Question
Description. This assignment takes an experimental approach to studying the efficiency of sorting algorithms. Two algorithms, Selection Sort and Merge Sort, are provided and you are asked to perform various experiments to characterize the behavior of the algorithms. As part of the experimentation, you must write a program to generate vectors of random data and time the algorithms on these vectors. By performing repeated experiments, you will investigate the rate of-growth behavior of the algorithms, their sensitivity to presorting, and the number of swaps vs inspections for each algorithm. Sorting and Efficiency For this assignment, you will experiment with two different sorting algorithms, selection sort and merge sort. To begin, you will need to copy the file Sorts.h, which contains definitions of the Selection Sort and M erge Sort functions 1. Write a main program named sortnums.cpp that can be used to compare the performance of these two algorithms. Your program should prompt the user for the number of items to be sorted, then construct a vector of that many random integers. It should then perform each of the sorts on that vector and time how long it takes (using the clock function from the ctime library). The time for each sort should be displayed in a readable format. 2. Perform 3 different executions of your program on each of the following list sizes: 500 items, 1000 items, 2000 items, and 4000 items. Report your timings in a table such as the one below 500 items 1000 items 2000 items 4000 items SELECTION SORT 1st timing 2nd timing: 3rd timing MERGE SORT 1st timing 2nd timing: 3rd timingExplanation / Answer
PROGRAM CODE:
/*
* sorts.cpp
*
* Created on: 01-Feb-2017
* Author: kasturi
*/
#include "sorts.h"
#include <iostream>
#include <ctime>
#include <string>
using namespace std;
void print(float difference, string message)
{
float seconds = difference/CLOCKS_PER_SEC;
cout<<message<<seconds<<" seconds"<<endl;
}
int main()
{
clock_t t1,t2;
float diff;
int num;
string message;
vector<int> numbers;
//Getting the value from user
cout<<"Enter the number of items: ";
cin>>num;
//Merge Sort
t1=clock();
for(int i=0; i<num; i++)
numbers.push_back((rand() % 100) + 1);
MergeSort(numbers, 0, num);
t2=clock();
diff = (float)t2-(float)t1;
message = "Running time of merge sort for " + to_string(num) + " items : ";
print(diff, message);
numbers.clear();
//Selection sort
t1=clock();
for(int i=0; i<num; i++)
numbers.push_back((rand() % 100) + 1);
SelectionSort(numbers, 0, num);
t2=clock();
diff = (float)t2-(float)t1;
message = "Running time of selection sort for " + to_string(num) + " items : ";
print(diff, message);
}
OUTPUT:
500 items:
Run #1:
Enter the number of items: 500
Running time of merge sort for 500 items : 0.001488 seconds
Running time of selection sort for 500 items : 0.001175 seconds
Run #2:
Enter the number of items: 500
Running time of merge sort for 500 items : 0.001485 seconds
Running time of selection sort for 500 items : 0.00117 seconds
Run #3:
Enter the number of items: 500
Running time of merge sort for 500 items : 0.001735 seconds
Running time of selection sort for 500 items : 0.001042 seconds
1000 items:
Run #1:
Enter the number of items: 1000
Running time of merge sort for 1000 items : 0.003069 seconds
Running time of selection sort for 1000 items : 0.004206 seconds
Run #2:
Enter the number of items: 1000
Running time of merge sort for 1000 items : 0.002975 seconds
Running time of selection sort for 1000 items : 0.004001 seconds
Run #3:
Enter the number of items: 1000
Running time of merge sort for 1000 items : 0.003014 seconds
Running time of selection sort for 1000 items : 0.003881 seconds
2000 items:
Run #1:
Enter the number of items: 2000
Running time of merge sort for 2000 items : 0.005857 seconds
Running time of selection sort for 2000 items : 0.009907 seconds
Run #2:
Enter the number of items: 2000
Running time of merge sort for 2000 items : 0.00436 seconds
Running time of selection sort for 2000 items : 0.008455 seconds
Run #3:
Enter the number of items: 2000
Running time of merge sort for 2000 items : 0.003703 seconds
Running time of selection sort for 2000 items : 0.008457 seconds
4000 items:
Run #1:
Enter the number of items: 4000
Running time of merge sort for 4000 items : 0.011533 seconds
Running time of selection sort for 4000 items : 0.034143 seconds
Run #2:
Enter the number of items: 4000
Running time of merge sort for 4000 items : 0.00691 seconds
Running time of selection sort for 4000 items : 0.036713 seconds
Run #3:
Enter the number of items: 4000
Running time of merge sort for 4000 items : 0.007266 seconds
Running time of selection sort for 4000 items : 0.036148 seconds