Give an example proving that WEIRDSORT would not correctly sort if we swapped li

Question

Give an example proving that WEIRDSORT would not correctly sort if we swapped lines 10&11 in STRAIGHTEN.

Assume that n is a power of two. Consider the following sorting algorithm: STRAIGHTEN(A[1 .. T) 1: if n-2 then 2 if A2A1 then 3: 4: end if 5: else swap A A2] WEIRDSORT(A[1..n]) 1: if n > 1 then 2 WEIRDSORT(A[1.. 3: WEIRDSORT(A+1.. n]) for i 1 to ! do swap A[i+41+ A [i+91 7: 8 end for 9 STRAIGHTEN (A[1.. 7 10 STRAIGHTEN (A5+1.. n) STRAIGHTEN(A1.. n) 5: end if AIGHTEN (AB+1 .. T]) 12: end ilf

Explanation / Answer

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 G
• Subjects

---

---

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