Using the PARTITION and QUICKSORT routines bellow, what value of q does each PAR

Question

Using the PARTITION and QUICKSORT routines bellow, what value of q does each PARTITION return for the following cases? Justify your answer for each case.

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

(2) when all elements 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

Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases.

1) Array is already sorted in same order.
2) Array is already sorted in reverse order.
3) All elements are same (special case of case 1 and 2)

Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.

Following is recurrence for worst case.

T(n) = T(0) + T(n-1) + theta(n)
which is equivalent to
T(n) = T(n-1) + O(n)
The solution of above recurrence is O(n^2).

(1) when all elements in A[p..r] are distinct and sorted in ascending order?
   this is the worst case situation: O(n^2)

(2) when all elements in A[p..r] are distinct and sorted in descending order?
   this is the worst case situation: O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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