Problem (page limit: 3 pages) A ssume that n is a power of two. Consider the fol

Question

Problem (page limit: 3 pages) A ssume that n is a power of two. Consider the following sorting algorithm: STRAIGHTEN(A1 T) : if 2 then ifA[2]«A111 then swap A A2 3: 4: end if 5: else WEIRDSORT(A1..T 1: ifn > 1 then 3 WEIRDSORT(A s: end if WEIRDSORT(All .. 6: fori1 to T do ) STRAIGHTEN(A1..) 8 end for 9: STRAIGHTEN (A1 STRAGHTEN (14+1,n/) STRAIGHTEN (AT1 10: 12: end if . Give an example proving that WEIRDSORT would not correctly sort if we removed lines 6-8 in STRAIGHTEN. 2. Give an ex ample proving that WEIRDSORT would not correctly sort if we swapped lines 10 & 11 in STRAIGHTEN 3. Prove by induction that WEIRDSORT correctly sorts any input array (of size a power of two). (Hint: Formulate a claim for what STRAIGHTEN 1s supposed to accomplish, and prove it.) 4. Write a recurrence to count the number of comparisons made by STRAIGHTEN on an array of size . Write a recurrence to count the number of comparisons made by WEIRDSORT on an array of size . Solve these two recurrences to obtain an asymptotic expression for the number of comparisons done by STRAIGHTEN and by WEIRDSORT. No need to show your calculations.

Explanation / Answer

Answer :

2)

Taking array with [4,5,3,1] as our test array.

wierdsort([4,5,3,1]) divides the problem into wierdsort[4,5] & wierdsort[3,1].

[4,5] divides problem into wierdsort[4]&wierdsort[5].

Now, straighten [4,5] is called and there's no change in position as 4 < 5. -----( array is [4,5,3,1] )

[3,1] divides problem into wierdsort[3]&wierdsort[1].

straighten [3,1] swaps positions of 3 and 1 and now the array is [1,3]. -----( array is [4,5,1,3] )

Now, straighten [4,5,1,3] is called.

since, n=4, n/4=1.

so loop in else executes just once, swapping A[2] and A[3] i.e 5 and 1. -----( array is [4,1,5,3] )

Now straighen(A[1..n/2]) = straighten(A[1,2]) straightens [4,1] to [1,4]. -----( array is [1,4,5,3] )

Now, after swap of line 10 & 11,

straighten(A[n/2+1 .. 3n/4])=straighten(A[2,3])=> does nothing as 4<5. ----( array is [1,4,5,3] )

straighten(A[n/2+1 .. n])=straighetn(A[3,4]=>) swaps [5,3] to [3,5] -----( array is [1,4,3,5] )

Thus, final sorted array we get is [1,4,3,5] which is wrong.

If the lines weren't swapped, straighten([5,3]) would've happened before straighteningA(2..3) and straighten A[2..3] would've straighten [4,3] resulting [1,3,4,5].

Thus, Swapping line 10 & 11 fails the algorithm to give correct solution.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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