C++ InsertionSort and HeapSort exercise:

The program: 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). You'll 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. Do the sorting and record how long each array took to sort. Use a function like System.currentTimeMillis() to get an exact time. Implementing the Algorithms: All algorithms should be implemented in Java, C++ or C#. YOU MUST USE POLYMORPHISM AS A WAY OF ENSURING THAT CLASSES THAT PERFORM SIMILAR FUNCTIONS ARE IMPLEMENTED IN THE SAME WAY. You should start by creating an interface (or abstract class), with a name like Sortable, containing an unimplemented method called sort. Then you should create a separate class that implements Sortable for each sorting algorithm. Your main method should then call the algorithms using code like this: Sortable insertion Sort1 = new Insertion Sort(500000, random); insertionSort1. sort(); Below is an outline of your code. This is just to give the idea. Feel free to modify the code in the ways to need to in order to make it work. public interface Sortable { public void sort(int n); } public class Insertion Sort implements Sortable { private int[] arr; public Insertion Sort(int n, String random OrSorted){ // create an array and make it sorted or unsorted depending on the // parameter } public void sort() { for (int i = 1; i = 0 && arr[i] > key) { arr[j + 1] = arr[i]; j = j - 1; } arr[j + 1] = key; } } public class Heap Sort implements Sortable { private int[] arr; private int heapsize; public Heap Sort(int n, String random OrSorted) { // your code here } public int parent(int i) { return (i-1)/2; } public int left(int i) { } public int right(int i) { } public maxHeapify(int i) { } public void buildMaxHeap() { } public void sort() { } }