Hi I just want to make sure if my C++ code follows the directions.

Requeriments:

Assignment Sorting

Benchmark each of the sorting methods listed below.

Insertion Sort

Bubble Sort

Selection Sort

Heap Sort.

Quick Sort.

Merge Sort.

Benchmark each of the above sorting methods for data sizes of 10000, 20000, 30000, 40000 and 50000. Display the results in a table as shown below. The table should have rows and columns. However, the rows and columns need not be separated by lines. Add two more columns for Selection and Insertion Sorts

Data Size	Heap Sort Time In Seconds	Merge Sort Time In Seconds	Quick Sort Time In Seconds	Bubble Sort
100000
200000
300000
400000
500000

Notes:

Do not use a local array for keeping data values. Use a global array for this purpose. You can use dynamically allocated arrays if you wish.

Generate the data using a random generator and store it in a global array for use in sorting. If you use a local array of large size, you will run out of stack space.

Calculate the time taken by a sort routine in seconds as below:

#include

clock_t start, finish; start =clock( ); //time in milliseconds sort( ); finish=clock( ); //time in milliseconds //the constant CLOCKS_PER_SEC below is equal to 1000 double duration = (double) ( (finish-start)/CLOCKS_PER_SEC ); //time in secs. cout <

Code:

#include

#include

#include

using namespace std;

void insertionSort(int arr[], int n)

{

int i, j;

int temp;

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

{

temp = arr[i];

j = i - 1;

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

{

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = temp;

}

}

void bubbleSort(int arr[], int n)

{

int i, j;

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

{

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

{

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

{

int t = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = t;

}

}

}

}

void heapify(int arr[], int n, int i)

{

int largest = i;

int l = 2 * i + 1;

int r = 2 * i + 2;

if (l < n && arr[l] > arr[largest])

largest = l;

if (r < n && arr[r] > arr[largest])

largest = r;

if (largest != i)

{

int temp = arr[i];

arr[i] = arr[largest];

arr[largest] = temp;

heapify(arr, n, largest);

}

}

void heapSort(int arr[], int n)

{

int i = 0;

for (i = n; i >= 0; i--)

heapify(arr, n, i);

for (i = n; i > 0; i--)

{

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

}

}

int partition(int arr[], int low, int high)

{

int pivot = arr[high];

int i = (low - 1), j;

for (j = low; j <= high - 1; j++)

{

if (arr[j] <= pivot)

{

i++;

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

int temp = arr[i + 1];

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

arr[high] = temp;

return (i + 1);

}

void quickSort(int arr[], int low, int high)

{

if (low < high)

{

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}

}

void merge(int arr[], 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 < n1; i++)

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

for (j = 0; j < n2; j++)

R[j] = arr[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 < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

void mergeSort(int arr[], int l, int r)

{

if (l < r)

{

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

// Sort first and second halves

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

}

}

void selectionSort(int arr[],int n) {

// One by one move boundary of unsorted subarray for (int i = 0; i < n-1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; if(min_idx != i) { double temp=arr[i]; arr[i]=arr[min_idx]; arr[min_idx]=temp; }

} }

int main()

{

srand(time(NULL));

cout << "DataSize BubbleSort InsertionSort Heap Sort Quick Sort MergeSort selectionsort ";

int rand_val;

for (int i = 100000; i < 500000; i += 100000)

{

int *ins_el = new int[i];

int *bubble_el = new int[i];

int *heap_el = new int[i];

int *quick_el = new int[i];

int *merge_el = new int[i]; int *selection_el = new int[i];

for (int j = 0; j < i; j++)

{

rand_val = rand() % 1000;

ins_el[j] = rand_val;

bubble_el[j] = rand_val;

heap_el[j] = rand_val;

quick_el[j] = rand_val;

merge_el[j] = rand_val;

selection_el[j]=rand_val; }

clock_t start, finish;

start = clock(); //time in milliseconds

insertionSort(ins_el, i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

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

start = clock(); //time in milliseconds

bubbleSort(ins_el, i);

finish = clock(); //time in milliseconds

//the constant CLOCKS_PER_SEC below is equal to 1000

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

start = clock(); //time in milliseconds

heapSort(heap_el, i);

finish = clock(); //time in milliseconds

double heap_duration = (double)((finish - start) / CLOCKS_PER_SEC); //time in secs.

start = clock(); //time in milliseconds

quickSort(quick_el, 0, i - 1);

finish = clock(); //time in milliseconds

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

start = clock(); //time in milliseconds

mergeSort(quick_el, 0, i - 1);

finish = clock(); //time in milliseconds

double merge_duration = (double)((finish - start) / CLOCKS_PER_SEC); //time in secs. start = clock(); //time in milliseconds

selectionSort(selection_el,i);

finish = clock(); //time in milliseconds

double selection_duration = (double)((finish - start) / CLOCKS_PER_SEC); cout << i << " \t" << ins_duration << " \t" << bubble_duration << " \t" << heap_duration << " \t" << quick_duration << " \t" << merge_duration <<" \t"<

}

return 0;

}