"C" PROGRAMMING LANGUAGE

7.18 Lab: Insertion Sort Algorithm The insertion sort algorithm updates its sorted array as each new data value is entered. It is an in-place algorithm, in that the sorted array at each step writes over the array from the previous step. Let us start with sorting in descending order (largest to smallest). The ascending order case follows as a simple modification to the descending case. Assume that we have thus far read N values and these are sorted in correct order (largest to smallest) in our array. We then read the next number, and we desire to place it in our array in the proper position. In order to do so, we compare the new input with the existing array values, starting with the last array element. If the new input has a value greater than the last array element, shift the array element to the next higher index (i.e., copy the N-th element to the N+1-th element). Continue to compare with lower indices, as long as the new input has a greater value than the current element, copy that element to the next higher index. At some point, the input value may not be greater than the array element, in this case, break out of the element-by-element testing and replace the previously compared element by the new input For example: Assume that we have already read these five numbers: 11, 5, 3, 2,6). The numbers are sorted as they are read, thus our array will look like the following (where beyond the fifth element the array values are undefined and hold some random value) 5 3 21 ? 2 Let the next input have a value of 4. We start by comparing the new input with the last array element (that is, 4 is compared to 1), the new value is larger so we copy the array element to the right, resulting in a new array of 5 3 21 1. _ . ? Our next step is to compare the element at the next lower index with the input (i.e, 4 compared to 2); again, the new value is larger, so we do the copy resulting in