This is computer algorithm class.

here is the book http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf

Implement the InsertionSort algorithm (P. 18 of the text) in C++. Test your code on arrays of various sizes - does it behave correctly and intelligently for arrays with negative numbers? for arrays of size 0? for arrays of n identical values?

Chapter 2 Getting Started (a) 5 2 4 613 (b) 2 5 4 613 (c) 2 4 5 (d) 2 4 5 61 3 (e) 2 45 6 (f) 23 45 6 Figure 2.2 The operation of INSERTION-SORT on the array A-(5, 2, 4, 6,1, 3). Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles. (a-e) The iterations of the for loop of lines 1-8. In each iteration, the black rectangle holds the key taken from AU), which is compared with the values in shaded rectangles to its left in the test of line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows indicate where the key moves to in line 8. (f) The final sorted array INSERTION-SORT (A) 1 for j = 2 to A. length 3 4 Insert Alj] into the sorted sequence Al.j - 5 whilei 0 and Ai] > key Ali + 1] = Ali! Ali+1]=key Loop invariants and the correctness of insertion sort Figure 2.2 shows how this algorithm works for A (5, 2.4. 6. 1. 3). The in dex j indicates the "current card" being inserted into the hand. At the beginning of each iteration of the for loop, which is indexed by j, the subarray consisting of elements A[l..j - 1 constitutes the currently sorted hand, and the remaining subarray ALj 1..n] corresponds to the pile of cards still on the table. In fact, elements A[1j-1) are the elements originally in positions 1 through j-1, but now in sorted order. We state these properties of A[1 -j-l] formally as a loop invariant At the start of each iteration of the for loop of lines 1-8, the subarray A [1 . J-1] consists of the elements originally in A [1j-1], but in sorted order We use loop invariants to help us understand why an algorithm is correct. We must show three things about a loop invariant