You are required to choose two sorting algorithms from a specified list: $($P$.$S$.$ Please use merge sort instead of Heap sort for the second algorithm, also the skeleton code to be used will be at the end of the question$)$

the first algorithm must be Bubble Sort, while the second algorithm can be either Merge Sort or Heap Sort.

a$)$ Write a C$++$ program where you implement the two sorting algorithms you have chosen $-$ ensure that they are part of the same program and can be called using methods, functions and$/$or procedures.

b$)$ Continue in this C$++$ program and generate random input arrays of different sizes, specifically $100,1000,$ and $5000$ elements.

c$)$ Utilize the implemented TWO sorting algorithms to sort these randomly generated arrays.

d$)$ Generate a report to indicate:

$-$ The input size $($number of elements$).$

$-$ The execution time for the two different sorting algorithms.

$-$ The time complexity formulas for the two different sorting algorithms.

Typical output:

Input Size: $100$

XXXXXX Sort:

Execution Time: $0\mathrm{.}002$ seconds

YYYYY Sort:

Execution Time: $0\mathrm{.}001$ seconds

Input Size: $1000$

XXXXXX Sort:

Execution Time: $0\mathrm{.}05$ seconds

YYYY Sort:

Execution Time: $0\mathrm{.}01$ seconds

Input Size: $5000$

XXXXXX Sort:

Execution Time: $2\mathrm{.}5$ seconds

YYYYY Sort:

Execution Time: $0\mathrm{.}1$ seconds

The time complexity formula for XXXXX: Give the formula

The time complexity formula for YYYY: Give the formula

SKELETON CODE TO BE USED BELOW:

#include

#include

#include "COS$2611\_$As$2\_$P$1.$h$"$

using namespace std;

$//$Function for the first sorting algorithm

$//$Function for the second sorting algorithm

$//$Function to generate a random array of a given size

vector generateRandomArray$($int size$)\{$

vector arr$($size$)$;

srand$($time$(0))$;

for $($int i $=0$; i $$ size; $++$i$)\{$

arr$[$i$]=$ rand$()\%1000$; $//$adjust the range to play around with it

$\}$

return arr;

$\}//$generateRandomArray

$//$you can make this more code efficient $-$ did it this way for more clarity purposes

void measureSortingTimeFirstSortingAlgorithm$($vector& arr, double& timeExecuted, double& timeComplexity$)\{$

$//$measure start time

clock$\_$t startTime $=$ clock$()$;

$//$Call your first sorting algorithm

$//$measure end time

clock$\_$t endTime $=$ clock$()$;

$//$calculate executation time in secods for first sorting algorithm

timeExecuted $=($endTime $-$ startTime$)/$ CLOCKS$\_$PER$\_$SEC;

$//$calculate time comlexity for your sorting algorithm

timeComplexity $=0$; $//$this will then be the time complexity $-$ you must provide the code

$\}//$measureSortingTimeFirstSortingAlgorithm

void measureSortingTimeSecondSortingAlgorithm$($vector& arr $,$ double &timeExecuted, double &timeComplexity $)\{$

$//$measure start time

clock$\_$t startTime $=$ clock$()$;

$//$Call your second algortihm

$//$measure end time

clock$\_$t endTime $=$ clock$()$;

$//$calculate executation time in secods for first sorting algorithm

timeExecuted $=($endTime $-$ startTime$)/$ CLOCKS$\_$PER$\_$SEC;

$//$calculate time comlexity for your sorting algorithm

timeComplexity $=0$; $//$this will then be the time complexity $-$ you must provide the code

$\}//$measureSortingTimeSecondSortingAlgorithm

int main$()$

$\{$

cout $$ "COS$2611$ Assessment $2$ Project $1-$ Skeleton

$"$;

cout $$ "ARRAYS";

$//$generate an array with $100$ random elements

double timeExecuted$1,$ timeExecuted$2$;

double timeComplexity$1,$ timeComplexity$2$;

vector inputSizes $=\{100,1000,5000\}$;

for $($int size : inputSizes$)\{$

vector arr $=$ generateRandomArray$($size$)$;

$//$measure the sorting time for sorting algorithm

measureSortingTimeFirstSortingAlgorithm$($arr$,$timeExecuted$1,$timeComplexity$1)$;

measureSortingTimeSecondSortingAlgorithm$($arr$,$timeExecuted$2,$timeComplexity$2)$;

$//$The display of your results will go here.

$\}$

return $0$;

$\}//$main