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, the BST, AVG, and WST arrays. Each one of these three arrays has 1000 integers where: 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.). Note: Make sure that all algorithms are tested with identical arrays. Therefore, at the beginning of your program, create three identical versions of the BST, AVG, and WST arrays where each algorithm sorts its own version.

2. 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 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 place). b. Increment comps with each comparison operation on the elements to be sorted. 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.

3. 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 recheck your code if it returns a false verification).