To begin, you need to write an algorithm to fill an array with random numbers. It should take as input the size of the array and generate numbers based on the size of the array. For example, if the array has 50,000 cells, it should fill with numbers between 1 and 50,000 (in random order). Youll also need a second method to fill an array with sorted, consecutive numbers. It is also ok to use a built-in function like Arrays.setAll() to fill your arrays. You will need to write both insertion sort and heap sort. Outlines of the code are given below. In your main method, fill arrays with 100000, 200000, 300000, 400000 and 500000 numbers. For each array size, make one that is filled with random numbers, and one that is filled with sequential numbers. This gives 10 arrays that must be sorted by two different sorting algorithms.

#ifndef HEAPSORT

#define HEAPSORT

#include

#include

#include "InsertionSort.h"

#include "Sortable.h"

using namespace std;

class HeapSort : public Sortable{

public:

HeapSort(int n, std::string randomOrSorted){

int array1[n];

int heapsize = n;

}

int parent(int i){

return (i-1)/2;

}

int left(int i){

int left = 2*i;

return left;

}

int right(int i){

int right = 2*i+1;

return right;

}

void maxHeapify(int i){

int l = left(i);

int r = right(i);

if(l<=heapsize && array1[l] > array1[i]){

largest = l;

}

else{

largest = i;

}

if(r<=heapsize && array1[r] > array1[largest]){

largest = r;

}

if(largest != i){

int temp = array1[i];

array1[i] = array1[largest];

array1[largest] = array1[i];

maxHeapify(largest);

}

}

void buildMaxHeap(){

for(int i= (heapsize/2); i > 0; i--){

maxHeapify(i);

}

};

void sort(){

buildMaxHeap();

int n;

int size = n;

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

int temp = array1[1];

array1[1] = array1[i];

array1[i] = temp;

n--;

maxHeapify(1);

}

}

};

#endif