Provide tight upper and lower bounds on the running time of the QUICKSORT algori

Question

Provide tight upper and lower bounds on the running time of the QUICKSORT algorithm below. Show your answer (the running time) in recurrence and solve the recurrence. Justify your answer to the two cases below.

(1) when all elements are in A[p...r] are distinct and sorted in ascending order?

(2) when all elements are in A[p...r] are distinct and sorted in descending order?

QuickSort(A, p, r)

if p < r

   q = Partition(A, p, r)

   QuickSort(A, p, q 1)

   QuickSort(A, q + 1, r)

Partition(A, p, r)

x = A[r] # x is the pivot.

i = p 1

for j = p to r 1

   if A[j] x

      i = i + 1

      exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1

Explanation / Answer

1. ANS

Ascending Order

1) increase p pointer until T[p] > X

2) Decrease r pointer until T[r] <= X

3) if p < r then interchange T[p] with T[r]

4) if r <= p then interchange T[r] with T[i]

2. ANS

Descending Order

1) increase p pointer until T[p] < X

2) Decrease  r pointer until T[r] >= X

3) if p > r then interchange T[p] with T[r]

4) if r >= p then interchange T[r] with T[i]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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