introduction To Algorithms-A3.pdf 3 Figure 2.2 The operation of INSERTION-SORT o
ID: 3905303 • Letter: I
Question
introduction To Algorithms-A3.pdf 3 Figure 2.2 The operation of INSERTION-SORT on the array A (5, 2, 4, 6, 1, 3 appear above the rectangles, and values stored in the array positions appear within (a)-(e) The iterations of the for loop of lines 1-8. In each iteration, the black rec key taken from A|LJ], which is compared with the values in shaded rectangles to its line 5. Shaded arrows show array values moved one position to the right in line 6, a indicate where the key moves to in line 8. (1 The final sorted array. INSERTION-SORT (A) 1 for j 2 to A.length 2 key AU 3 Insert AU] into the sorted sequence All. .j -1] 5 while i 0 and Ali]> key ?i + 1] = Ali] 8 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) dex j indicates the "current card" being inserted into the hand. At the b of each iteration of the for loop, which is indexed by j, the subarray c of elements Al..j 1] constitutes the currently sorted hand, and the re subarray AU + 1..nl corresponds to the pile of cards still on the table. elements A[l ..j -1] are the elements originally in positions 1 through now in sorted order. We state these properties of AlL invariant: .. j 1] formally as At the start of each iExplanation / Answer
Insertion sort, works on the principle of inserting the element on it's correct position,
in line 6-8, the compiler first searches for the correct position for current key
in line 6: The compiler pushes every element in the list to the keys position by one, such that the correct position that is supposed to be held by the key, will be emptied.
In line 7: decrement for the loop to ensure the movement of the postions
In line 8: Insert the key at the found position.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.