Assume the array A = [7, 2, 8, 12, 0, 3, 8, 3] is sorted with the Insertion Sort

Question

Assume the array A = [7, 2, 8, 12, 0, 3, 8, 3] is sorted with the Insertion Sort pseudo-code given below. (This is the same as the one in our current slides page 37; I just added curly braces around the body of the for loops for clarity.)   Write the array at the end of each iteration of the for j loop (immediately after the instruction ‘A[i+1] = key’ finished).  

If you want to check your understanding before answering, an example of this is shown in the slides. But the purpose of this exercise is to get you familiar with reading and understanding code/pseudo-code.

In order to match my answer exactly, write the arrays one after the other, use square brackets around the array numbers, separate them by comma, do not include ANY spaces. ALSO DO NOT WRITE THE ORIGINAL ARRAY. (Hint: there should be 7 arrays in your answer.)

If you do not match the answer because you did not follow these instructions, you will not get the points. The format (not actual data) of your answer should be like the line shown below (for 3 arrays). (Remember that you will have 7 arrays on your line in your):

[7,2,8,12,0,3,8,3][7,2,8,12,0,3,8,3] [7,2,8,12,0,3,8,3]

[7,2,8,12,0,3,8,3][7,2,8,12,0,3,8,3][7,2,8,12,0,3,8,3]

(In the pseudo-code below, indexes start from 0, and the array A has N elements.)

Insertion-Sort(A,N)

for j = 1 to N-1 {

key = A[j]

i = j-1

while (i>=0) and (A[i]>key) {

A[i+1] = A[i]

i = i–1

     }

A[i+1] = key

}

Explanation / Answer

[2, 7, 8, 12, 0, 3, 8, 3] ==> Because 7>2 so swap
[2, 7, 8, 12, 0, 3, 8, 3]==> 7<8 do not change anything
[2, 7, 8, 12, 0, 3, 8, 3]==> 8<12 do not change anything
[0 ,2, 7, 8, 12, 3, 8, 3]==> 0 is less than 12,8,7,2 , so bring it to begenning
[0 ,2, 3, 7, 8, 12, 8, 3]==> 3 is less than 12,8,7 , so bring it to after 2
[0 ,2, 3, 7, 8, 8, 12, 3]==> 8 is less than 12 so bring it to after 8
[0 ,2, 3, 3, 7, 8, 8, 12]==> 3 is less than 12,8,7,3 so bring it to after 3

So total there are 7 arrays

Thanks, let me know if there is any doubts

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.