DUPLICATE ELEMENTS IN QUICKSORT Suppose that the determinist

DUPLICATE ELEMENTS IN QUICKSORT

Suppose that the deterministic quicksort algorithm described in class is executed on a sequence with duplicate elements. What happens in the partition step when all the elements of the input sequence are equal?

(a) How many comparisons are done on quicksort if the entire array is the same number?

(b) Describe a modified version of quicksort in which arrays of same number run in n1n1 comparisons. Hint: partition the array into three parts rather than two.

Solution

a)

If we are using the version of Quicksort in which the partitioning scheme produces two subarrays plus the pivot, and

one subarray contains elements less than or equal the pivot, and the other contains elements that are greater than

or equal to the pivot, then the partitioning will be unbalanced. Quicksort will do n 1 comparisons, and recurse

into the lower subarray of size n 1. Therefore, the total amount of work will be (n).

b)

If we are using the version of Quicksort in which the partitioning scheme produces three subarrays containing

respectively all elements strictly less than, all elements equal to, or all elements strictly greater than the pivot, then

Quicksort will put all the elements in the middle subarray and will not recurse into any array. So the amount of work

done is O(n).