4. The following sorting algorithm, called BadSort() is a modified version of StoogeSort() from the 2nd...

  

Transcribed Image Text:

4. The following sorting algorithm, called BadSort() is a modified version of StoogeSort() from the 2nd edition of CLRS, which seems to have been left out of the 3rd edition. BadSort(A.p.r) pre: p ≤r 1. if A[p]>A[r] 2. ( 3. if p + 1≥r 4. return 5. 6. 7. 8. 9. A[p] A[r] (swap) else q= [(rp+1)/3] BadSort (A, p, r— q) BadSort(A, p + q, r) BadSort(A, p, r — q) a. Use induction on the length m = r - p + 1 of A[pr] to prove the correctness of BadSort(). b. Write a recurrence relation for the number of array comparisons performed by BadSort() on an array of length n. c. Use the Master Theorem to find an asymptotic solution to this recurrence, and explain what is bad about BadSort(). 4. The following sorting algorithm, called BadSort() is a modified version of StoogeSort() from the 2nd edition of CLRS, which seems to have been left out of the 3rd edition. BadSort(A.p.r) pre: p ≤r 1. if A[p]>A[r] 2. ( 3. if p + 1≥r 4. return 5. 6. 7. 8. 9. A[p] A[r] (swap) else q= [(rp+1)/3] BadSort (A, p, r— q) BadSort(A, p + q, r) BadSort(A, p, r — q) a. Use induction on the length m = r - p + 1 of A[pr] to prove the correctness of BadSort(). b. Write a recurrence relation for the number of array comparisons performed by BadSort() on an array of length n. c. Use the Master Theorem to find an asymptotic solution to this recurrence, and explain what is bad about BadSort().

Answer rating: 100% (QA)

Proof of Correctness using Induction Base Case m 1 array of one elementtrivially sorted m 2 array of ... View the full answer