I've written six functions to code for the following six sorting algorithms in C++ via headers.

a. Selection Sort

b. Bubble Sort

c. Insertion Sort

d. Merge Sort

e. Quick Sort

f. Heap Sort

The header files are already created and work properly. They're written as shown through #include.

These are the header files:

bubblesort.h

void bubblesort(int arr[], int n)

{

int i, j;

bool swapped;

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

{

swapped = false;

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

{

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

{

swap(&arr[j], &arr[j+1]);

swapped = true;

}

}

// IF no two elements were swapped by inner loop, then break

if (swapped == false)

break;

}

}

heapsort.h

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

{

int largest = i; // Initialize largest as root

int l = 2 * i + 1; // left = 2*i + 1

int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

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

largest = l;

// If right child is larger than largest so far

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

largest = r;

// If largest is not root

if (largest != i) {

swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}

}

// main function to do heap sort

void heapsort(int arr[], int n)

{

// Build heap (rearrange array)

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i > 0; i--) {

// Move current root to end

swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);

}

}

insertionsort.h

void insertionsort(int arr[], int n)

{

int i, key, j;

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

{

key = arr[i];

j = i - 1;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > key)

{

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

j = j - 1;

}

arr[j + 1] = key;

}

}

mergesort.h

void merge(int arr[], int l, int m, int r)

{

int n1 = m - l + 1;

int n2 = r - m;

// Create temp arrays

int L[n1], R[n2];

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

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

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

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

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

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

// Initial index of first subarray

int i = 0;

// Initial index of second subarray

int j = 0;

// Initial index of merged subarray

int k = l;

while (i < n1 && j < n2) {

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

arr[k] = L[i];

i++;

}

else {

arr[k] = R[j];

j++;

}

k++;

}

// Copy the remaining elements of

// L[], if there are any

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

// Copy the remaining elements of

// R[], if there are any

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

}

// l is for left index and r is right index of the sub-array of arr to be sorted

void mergesort(int arr[],int l,int r){

if(l>=r){

return;//returns recursively

}

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

mergesort(arr,l,m);

mergesort(arr,m+1,r);

merge(arr,l,m,r);

}

selectionsort.h

void selectionsort(int arr[], int n)

{

int i, j, min_idx;

// One by one move boundary of unsorted subarray

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

{

// Find the minimum element in unsorted array

min_idx = i;

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

if (arr[j] < arr[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);

}

}

quicksort.h

void swap(int* a, int* b)

{

int t = *a;

*a = *b;

*b = t;

}

/* This function takes last element as pivot, places

the pivot element at its correct position in sorted

array, and places all smaller (smaller than pivot)

to left of pivot and all greater elements to right

of pivot */

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

{

int pivot = arr[high]; // pivot

int i = (low - 1); // Index of smaller element

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

{

// If current element is smaller than the pivot

if (arr[j] < pivot)

{

i++; // increment index of smaller element

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i + 1], &arr[high]);

return (i + 1);

}

/* The main function that implements QuickSort

arr[] --> Array to be sorted,

low --> Starting index,

high --> Ending index */

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

{

if (low < high)

{

/* pi is partitioning index, arr[p] is now

at right place */

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

// Separately sort elements before

// partition and after partition

quicksort(arr, low, pi - 1);

quicksort(arr, pi + 1, high);

}

}

Mainly, I'm having problems on knowing the proper code on how to let the sort functions use the 10 generated arrays.

Question:

Use the generated 10 arrays in the code to give as the input to your six sorting functions and measure the duration of each function. Comment the statements you used to print the sorted array after each sorting function, as you need to measure only the time taken to sort.The output of each sort is the time taken in milliseconds to sort the given unsorted array. You can use "#include " or "#include" to measure the duration of a function in C++. While measuring the time you only need to measure the time taken by each sorting algorithm to convert the unsorted array into a sorted array. Note: The additional time taken, such as to construct your input unsorted array and to print your sorted array to console should not be included while measuring the duration of the sort.

Code:

// main.cpp

#include

#include

#include

#include

//#include "selectionsort.h"

//#include "bubblesort.h"

//#include "insertionsort.h"

//#include "mergesort.h"

//#include "quicksort.h"

//#include "heapsort.h"

using namespace std;

// function prototypes

void generateData();

void readData();

//main method

int main()

{

// seed random time

srand(time(NULL));

// call function to generate data

generateData();

// call function to read data to arrays

readData();

return 0;

}

// (1) function to generate 10 unique dataset files

void generateData()

{

// initialize the dataset sizes

int sizes[] = {1000, 4000, 8000, 10000, 40000,

80000, 100000, 400000, 800000, 1000000};

// create datasets

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

{

// create file

ostringstream ss;

ss << i;

string ch = ss.str();

string filename = "filename" + ch + ".txt";

fstream file;

// open file

file.open(filename.c_str(), ios::out);

// write random numbers to file

for (int j = 0; j < sizes[i]; j++)

{

// random number to file

file << rand() % 1000000;

// comma

if (j != sizes[i]-1)

{

file << ',';

}

}

// close file

file.close();

}

// print message to console

cout << "Files Generation Completed!" << endl;

}

// (2) function to read the data into 10 arrays

void readData()

{

// initialize the dataset sizes

int sizes[] = { 1000, 4000, 8000, 10000, 40000,

80000, 100000, 400000, 800000, 1000000};

// arrays of integers

int **arr = new int *[10];

// read datasets

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

{

// create file

ostringstream ss;

ss << i;

string ch = ss.str();

string filename = "filename" + ch + ".txt";

fstream file;

// open file

file.open(filename.c_str(), ios::in);

// array created depending on size

arr[i] = new int[sizes[i]];

// read numbers from file

string data;

getline(file, data);

stringstream numsStr(data);

for (int j = 0; j < sizes[i]; j++)

{

string numStr;

getline(numsStr, numStr, ',');

int num = stoi(numStr);

arr[i][j] = num;

}

// close file

file.close();

}

// print message to console

cout << "Unsorted Arrays Generation Completed!" << endl;

// values are now saved to arrays arr

// example:

//

// to print array 1, uncomment the next line

// for (int j = 0; j < sizes[0]; j++) cout << arr[0][j] << " ";

// to print array 2, uncomment the next line

//for (int j = 0; j < sizes[1]; j++) cout << arr[1][j] << " ";

}