Write a program to display the running time of the sorts des

Write a program to display the running time of the sorts described below. Test the sorts on array of various sizes (specified below). Arrays of the same size should contain identical entries. Use the function clock from to time each sort.

Note: This is in c++

Instruction:

You are to compare the relative performance of different sorting algorithms on the same data set and the same algorithm on different data sets.

Choose one sorting algorithm from each category listed below (for a total of 3):

O(n^2) : Selection sort, insertion sort or bubble sort.

O(n logn) : merge sort or quick sort.

O(n): counting sort, bucket sort or radix sort.

**Please only use the options listed above.

Randomly generate 1000, 10000, and 100000 integer values in the range of 0 to 1,000,000 to be inseted into the data structures. Note that the list (i.e. the input values) itself should not be sorted and all the algorithms should use the same input file when the input size is the same.

ALSO, test the speed of the algorithms when the input array is already sorted (for the same input data).

The following output should be provided for an average of 10 sorts of each algorithm and input size:

1. The cpu time. (note that the generation process should not affect these values)

2. The number of comparisons

3. The number of swaps.

Now run the algorithm with 1,000,000 values!

NOTE: you can run 2 instances of algorithms that take mroe than one hour.

Deliverables:

1. Source code for your classes

2. A main file that tests the classes with randomly generated data

3. Test output of your algorithms (with a tabulau of each run and their averages.

Here is an example they gave on how to time code:

#include

clock_t start = clock();

doSomething();

clock_t finish = clock();

double overallTime = static_cast(finish - start) / CLOCKS_PER_SEC;

Solution

C++ program for bubble sort:

Bubble sort is a technique used in soring. Here the sorting is done with the comparision done between the adjacent elements. If the adjacent elements are found in the wrong order then swapping will be done. This has got the name as bubble sort because , just like bubbles the smaller or lighter elements comes at start and the bigger or heavier elements at the end.

# include<iostream> // lib file inclusion

using namespace srt;

int main() // main calause

{

int a [50] , n,i,j,temp //# declaration of the variables

cout <<\"Enter the size of the array:\" // the \" \" statement will be printed in the screen

cin>>n; // value entered by the user will be stored in the n variable.

cout<<\"Enter the array elements;

for(i=0;i<n;i++) \\\\for statement for the intermental

cin>>a[i]; \\\\every for loop gives the new input value for the i

for(i=1;i<n;++i) //nested for loop is used here to check for the conditions

{

for(j=0;j<(n-i);++j)

if (a[j]>a[j+1]) // comparision is done here for finding thr greater number

{

temp = a[j];

a[j]=a[j+1];

a[j+1) = temp // general swapping of the values

}

}

cout<<\" Array after bubble sort:\" //after sorting the value wil be dsiaplyed

for(i=0;i<n;i++)

cout<<\" \"a[i];

return0;

}