Please help with task II using the C++ code below.

Thank you.

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int *ins_el;

int *bubble_el;

int *sel_el;

int *heap_el;

int *quick_el;

int *merge_el;

void insertionSort(int n)

{

int i, j;

int temp;

for (i = 1; i

{

temp = ins_el[i];

j = i - 1;

while (j > 0 && ins_el[j] > temp)

{

ins_el[j + 1] = ins_el[j];

j = j - 1;

}

ins_el[j + 1] = temp;

}

}

void bubbleSort(int n)

{

int i, j;

for (i = 0; i

{

for (j = 0; j

{

if (bubble_el[j] > bubble_el[j + 1])

{

int t = bubble_el[j];

bubble_el[j] = bubble_el[j + 1];

bubble_el[j + 1] = t;

}

}

}

}

void selectionSort(int n)

{

int i, j;

for (i = 0; i

{

for (j = i; j

{

if (sel_el[i] > sel_el[j])

{

int temp = sel_el[i];

sel_el[i] = sel_el[j];

sel_el[j] = temp;

}

}

}

}

int partition(int low, int high)

{

int pivot = quick_el[high];

int i = (low - 1), j;

for (j = low; j

{

if (quick_el[j]

{

i++;

int temp = quick_el[i];

quick_el[i] = quick_el[j];

quick_el[j] = temp;

}

}

int temp = quick_el[i + 1];

quick_el[i + 1] = quick_el[high];

quick_el[high] = temp;

return (i + 1);

}

void quickSort(int low, int high)

{

if (low

{

int pi = partition(low, high);

quickSort(low, pi - 1);

quickSort(pi + 1, high);

}

}

void merge(int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int *L = new int[n1];

int *R = new int[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i

L[i] = merge_el[l + i];

for (j = 0; j

R[j] = merge_el[m + 1 + j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i

{

if (L[i]

{

merge_el[k] = L[i];

i++;

}

else

{

merge_el[k] = R[j];

j++;

}

k++;

}

while (i

{

merge_el[k] = L[i];

i++;

k++;

}

while (j

{

merge_el[k] = R[j];

j++;

k++;

}

}

void mergeSort(int l, int r)

{

if (l

{

int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(l, m);

mergeSort(m + 1, r);

merge(l, m, r);

}

}

void randomPermu()

{

srand(time(NULL));

int rand_val;

int data[] = { 100, 200, 300, 400, 500, 1000, 2000, 4000, 10000 };

for (int i = 1; i

{

ins_el = new int[data[i]];

bubble_el = new int[data[i]];

sel_el = new int[data[i]];

quick_el = new int[data[i]];

merge_el = new int[data[i]];

for (int j = 0; j

{

rand_val = rand() % 100;

ins_el[j] = rand_val;

bubble_el[j] = rand_val;

quick_el[j] = rand_val;

merge_el[j] = rand_val;

}

clock_t start, finish;

start = clock(); //time in milliseconds

insertionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double ins_duration = (double)(10000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

bubbleSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double bubble_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

selectionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double sel_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

quickSort(0, i - 1);

finish = clock(); //time in milliseconds

double quick_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

mergeSort(0, i - 1);

finish = clock(); //time in milliseconds

double merge_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

cout

}

}

void sorted()

{

int data[] = { 100, 200, 300, 400, 500, 1000, 2000, 4000, 10000 };

for (int i = 1; i

{

ins_el = new int[data[i]];

bubble_el = new int[data[i]];

sel_el = new int[data[i]];

quick_el = new int[data[i]];

merge_el = new int[data[i]];

for (int j = 0; j

{

ins_el[j] = j + 1;

bubble_el[j] = j + 1;

quick_el[j] = j + 1;

merge_el[j] = j + 1;

}

clock_t start, finish;

start = clock(); //time in milliseconds

insertionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double ins_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

bubbleSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double bubble_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

selectionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double sel_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

quickSort(0, i - 1);

finish = clock(); //time in milliseconds

double quick_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

mergeSort(0, i - 1);

finish = clock(); //time in milliseconds

double merge_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

cout

}

}

void revSorted()

{

int data[] = { 100, 200, 300, 400, 500, 1000, 2000, 4000, 10000 };

for (int i = 1; i

{

ins_el = new int[data[i]];

bubble_el = new int[data[i]];

sel_el = new int[data[i]];

quick_el = new int[data[i]];

merge_el = new int[data[i]];

for (int j = 0; j

{

ins_el[j] = data[i] - j;

bubble_el[j] = data[i] - j;

quick_el[j] = data[i] - j;

merge_el[j] = data[i] - j;

}

clock_t start, finish;

start = clock(); //time in milliseconds

insertionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double ins_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

bubbleSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double bubble_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

selectionSort(i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

double sel_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

quickSort(0, i - 1);

finish = clock(); //time in milliseconds

double quick_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

mergeSort(0, i - 1);

finish = clock(); //time in milliseconds

double merge_duration = (double)(1000.0 * (finish - start) / CLOCKS_PER_SEC); //time in secs.

cout

}

}

int main()

{

cout

cout

sorted();

cout

cout

randomPermu();

cout

cout

revSorted();

system("Pause");

return 0;

}

the CPU running time in a table ( 2 ) Report the number of steps and (3) Plot the running time of the algorithm results Task 11; For each algorithm, and for each n (number of integers)-100, 200, 300, 400, 500, 1000, 2000,4000, 10000 measure its average running time and average number of steps for 50 randomly generated instances Note the input data should include 50 sets of n numbers with each number generated randomly in the range of [I, n]. Accumulated the total CPU time and the total number of steps for all 50 data sets, and then get the average CPU time and average total number of steps by dividing the total value by 50. What to turn in: (1) Well documented source code in C++ (2) Report the number of steps and the CPU running time in a table (3) Plot the running time of the algorithm results