The analysis of the expected running time of randomized quicksort in Section 7.4

Question

The analysis of the expected running time of randomized quicksort in Section 7.4.2 assumes that all element values are distinct. In this problem, we examine what happens when they are not. The Partition procedure returns an index q such that each element of A [p middot middot q - 1] is less than or equal to A [q] and each clement of A [q + 1 .. r] is greater than A [q]. Modify the PARTITION procedure to produce a procedure PARTITION' (A, p, r), which permutes the elements of A[p .. r] and returns two indices q and t, where p lessthanorequalto q lessthanorequalto t lessthanorequalto r, such that all elements of A [q .. t] are equal, each element of A [p middot middot q - 1] is less than A [q], and each element of A[t + 1 .. r] is greater than A[q]. Like Partition, your Partition' procedure should take Theta (r - p) time. Partition into {x}.

Explanation / Answer

PARTITION’(A, p, r)

q = p

t = r

index = p+1

key = A[p]

while index < t + 1

if A[index] < key

Exchange A[q] and A[index]

q = q + 1

else if A[index] > key

Exchange A[t] and A[index]

t = t - 1

else

index = index+ 1

return (q, t)



here is the algorithm for PARTITION', Let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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