This is an assignment for Algorithm course. # Using correctness of insertion sor

Question

This is an assignment for Algorithm course.

# Using correctness of insertion sort (use an array) to proof mathematical induction. Please see the below attachment to use that theory to answer your question. {precise your answer}

Chapter 2 Getting Started (a) 5 2 4 6 1 3 (b) 2 5 4 613 (c) 2 4 5 63 1 2 3 45 6 1 2 3 45 6 (d) 2 4 5 61 3 (e) 2456 (f) 12 345 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 Aj], 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) I forj= 2 to A. length 1 - key = A[j] 3l/ Insert ALj] into the sorted sequence A[1..j -1] 4 5 whilei 0 and Ali] >key A[i +1] = key

Explanation / Answer

In Order to prove the correctness of insertion sort by Mathematical induction , we have to prove the following cases.

We have to prove that P ( n) is true for all positive integers, from n=1.

As per our algorithm , we start the iteration at j = 2. that is , for j = 2 only A [ j ] is moved.

This means the elements at the left side of j are sorted and those at the right side are unsorted. Thus we can say that for

P(n) = the subarray A 1, A2 . . . , An is sorted at the start of iteration n + 1 .

1. To prove that P(1) is true :

When j = 2, there is a single element to the left,  

that is , the sub array is trivially sorted.

Hence P(1) is true.

2. we Assume that P(n) is true for some n.

3. Derive that P(n+1) is also true for some n.

we have to prove that the subarray remains sorted at the end iteration. To prove this we consider two subarrays A 1, A2........An and A'1 , A'2 ...............A'n and prove that (A' j1 <= A' j ) for any j .

There are three possibilities here.

So by there 3 conditions , the sort is satisfied. Thus by  by mathematical induction correctness of insertion sort has been proved.

Hence the proof.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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