Description. This assignment takes an experimental approach to studying the effi
ID: 3787234 • 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 Merge 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.Explanation / Answer
Selection Sort:-Selection Sort Complexity is O(n^2).
void selectionSort(int* a, int size)
{
for (int i = 2; i < size; i++)
{
for (int j = i; j >= 1; j--)
{
if (a[j] < a[j - 1])
{
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
Merge sort:- Merge sorting complexity is O(nlogn).
void merge(int* a, int first, int middle, int last)
{
int j,i0,i1;
i0 = first;
i1 = middle;
// While there are elements in the left or right runs
for (j = first; j < last; j++) {
// If left run head exists and is <= existing right run head.
if (i0 < middle && (i1 >= last || a[i0] <= a[i1])){
b[j] = a[i0];
i0++;
}
else{
b[j] = a[i1];
i1++;
}
}
}
void split(int* a, int first, int last)
{
if (last - first<2)
return;
int middle = floor((first + last) / 2);
//cout<<first<<" "<<middle<<" "<<last<<endl;
split(a, first, middle);
split(a, middle, last);
merge(a, first, middle, last);
copyArray(a,b, first, last);
}
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <ctime>
#include <sys/time.h>
#include <fstream>
#include <math.h>
using namespace std;
int* b;
bool odd;
bool enablePrinting=false;
//Selection Sort
void selectionSort(int* a, int size)
{
for (int i = 2; i < size; i++)
{
for (int j = i; j >= 1; j--)
{
if (a[j] < a[j - 1])
{
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
/////////////////////////////
//Insertion Sort
void insertionSort(int* a, int size)
{
for (int i = 1;i < size;i++)
{
int x = a[i];
int j = i;
while (j > 0 && a[j-1] > a[j])
{
int temporaryVariable=a[j];
a[j] = a[j-1];
a[j-1]=temporaryVariable;
j --;
}
a[j] = x;
}
}
/////////////////////////////
//Merge Sort
void merge(int* a, int first, int middle, int last)
{
int j,i0,i1;
i0 = first;
i1 = middle;
// While there are elements in the left or right runs
for (j = first; j < last; j++) {
// If left run head exists and is <= existing right run head.
if (i0 < middle && (i1 >= last || a[i0] <= a[i1])){
b[j] = a[i0];
i0++;
}
else{
b[j] = a[i1];
i1++;
}
}
}
void copyArray(int* a,int* b, int first, int last)
{
for(int k = first; k < last; k++)
a[k] = b[k];
}
void split(int* a, int first, int last)
{
if (last - first<2)
return;
int middle = floor((first + last) / 2);
//cout<<first<<" "<<middle<<" "<<last<<endl;
split(a, first, middle);
split(a, middle, last);
merge(a, first, middle, last);
copyArray(a,b, first, last);
}
/////////////////////////////
int* populateArray(int size)
{
b=new int[size];
int* a = new int[size];
for (int i = 0;i < size;i++)
{
srand(rand()*i);
a[i] = rand() % 100;
b[i]=-1;
}
return a;
}
void printArray(int* a,int size)
{
for (int i = 0;i < size;i++)
{
if(enablePrinting)
cout<<a[i]<<" ";
}
if(enablePrinting)
cout<<endl;
}
long long now()
{
struct timeval timeNow;
gettimeofday(&timeNow, NULL);
return (timeNow.tv_sec * 1000000 + timeNow.tv_usec);
}
int diff(timespec end, timespec start)
{
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return temp.tv_sec;
}
int main()
{
int sizes[10] ={10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000};
long long start, end;
ofstream CFile ("comparison.csv");
CFile<<"SIZE;Selection;Insertion;Merge"<<endl;
for (int i = 0;i < 10;i++)
{
int size = sizes[i];
long long selectionSortTimeSum = 0;
long long insertionSortTimeSum = 0;
long long mergeSortTimeSum = 0;
for (int j = 0;j < 1;j++)
{
//==Selection==//
int* a = populateArray(size);
start = now();
selectionSort(a, size);
printArray(a,size);
end = now();
selectionSortTimeSum= end- start;
//==Merge==//
a = populateArray(size);
start = now();
split(a, 0, size);
printArray(a,size);
//NOW LIST IS SORTED ON THE 2ND HALF OF A
end = now();
mergeSortTimeSum = end- start;
//==Insertion==//
a = populateArray(size);
start = now();
insertionSort(a, size);
printArray(a,size);
end = now();
insertionSortTimeSum = end- start;
}
cout << "Selection " << size << " : " << selectionSortTimeSum << endl;
cout << "Insertion " << size << " : " << insertionSortTimeSum << endl;
cout << "Merge " << size << " : " << mergeSortTimeSum << endl;
CFile<<size<<";"<<selectionSortTimeSum<<";"<<insertionSortTimeSum<<";"<<mergeSortTimeSum<<endl;
}
return 0 ;
}
N is the number of integers in an unsorted array.
Array Size
Selection Sort Time
Merge Sort Time
9999
181675
1551
19990
715737
2600
29999
15832654
4032
39999
2746640
5880
49999
4267589
6916
59999
6193661
9502
69999
8561373
10793
Array Size
Selection Sort Time
Merge Sort Time
9999
181675
1551
19990
715737
2600
29999
15832654
4032
39999
2746640
5880
49999
4267589
6916
59999
6193661
9502
69999
8561373
10793