In this problem you will test and analyze the Insertion, Heap, and Quick sort algorithms. To carry out this task, write a C++ program with the following requirements:

1. Analyze the algorithms by sorting, in ascending order, arrays of 1000 integers.

2. Create three arrays, BST, AVG, and WST, each has 1000 integers as follows:

a. BST has 1000 integers already sorted in ascending order (e.g., 10, 20, 30, etc.).

b. AVG has 1000 randomly generated integers, where each integer is between 0 and 100,000.

c. WST has 1000 integers sorted in descending order (e.g., 1000, 990, 980, etc.).

3. To test all algorithms with identical arrays, test each algorithm with the following 1000-integer arrays: tBST, tAVG, and tWST. Make sure that before testing each algorithm, these three arrays (tBST, tAVG, and tWST) are re-initialize as copies from BST, AVG, and WST respectively (you can write a function to carry out the copy task).

4. Define two global integer variables: moves and comps. Initialize these variables to zero before every call to a sorting algorithm. Add any necessary code to the algorithms implementation to carry out the following:

a. Increment moves with every movement of any of the elements to be sorted from one "place" to another. Consider that the swap operation, of two different values, requires three movements of two elements. However, the following is not considered a move: making a "copy" of an element that will not result eventually of that element being copied to another location in the array (i.e., the element stays in its original place when it was copied). For example, in Insertion sort algorithm the copy operation "key A[j]" does not increment "moves" as that A[j] might ended up staying in its place (i.e., not moved). Only if we need to move that A[j] to another location in the array, then "moves" needs to be incremented,

b. Increment comps with each comparison operation on the elements to be sorted (not their indices).

c. After each call to the sorting algorithms functions (3 algorithms 3 arrays = 9 calls), write to a text file, sort.txt, the values of moves and comps correspond to each algorithm.

5. To ensure that the algorithms are implemented correctly, you need to verify that the arrays are sorted after calling each algorithm. One way to do that is to confirm that every element i in the array has a value less than or equal to the value of element i+1 (write a function for this task and re-check your code if it returns a false verification).

6. After running your program, copy the numbers in the text file, sort.txt, to an excel sheet. Use these numbers to generate two graphs. One graph compares the number of moves needed by the three algorithms for the three cases: best, average, and worst. Another graph does the same but for the number of comparisons performed by the algorithms.

In your homework report, answer the following questions:

i. Why does the Insertion sort algorithm result in zero moves when sorting an already sorted array (the best case)?

ii. Why does the Insertion sort algorithm result in 999 comparisons when sorting an already sorted array (the best case)?

iii. Based on the two excel graphs, how does each algorithm perform under different scenarios (best, average, and worst)?

rogramming Hints - The following C++ code show you how to create a text file and write a text message in it: - The following C++ code show you how to generate 5 random integers. Each integer is between 0 and 100. \#include int main(){ int A[5] srand(time(NULL)); //call this only once at the beginning to // allow rand() to generate a different // succession of random values. for (int i=0;i