just wanted to know if the below is correct. I am trying to solve this using the insertion sort algorithm. I have tried to attempt the below array and have come up with these answers. Please could you let me know if this is correct, and if i have the correct understanding. Many Thanks.
Reverse sorted sequence:
15, 12, 10, 4
12, 15, 10, 4
12, 10, 15, 4
12, 10, 4, 15
10, 12, 4, 15
10, 4, 12, 15
10, 4, 12, 15 (no swap)
4, 10, 12, 15
As stated in LECTURE NOTES ON DATA STRUCTURE on page 176
Suppose, you want to sort elements in ascending as in above figure. Then,
Step 1: The second element of an array is compared with the elements that appears before it (only first element in this case). If the second element is smaller than first element, second element is inserted in the position of first element. After first step, first two elements of an array will be sorted.
Step 2: The third element of an array is compared with the elements that appears before it (first and second element). If third element is smaller than first element, it is inserted in the position of first element. If third element is larger than first element but, smaller than second element, it is inserted in the position of second element. If third element is larger than both the elements, it is kept in the position as it is. After second step, first three elements of an array will be sorted.
Step 3: Similary, the fourth element of an array is compared with the elements that appears before it (first, second and third element) and the same procedure is applied and that element is inserted in the proper position. After third step, first four elements of an array will be sorted.