Description This assignment takes an experimental approach t

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.

Solution

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