7.1.2. The value of q returned will be r.
We can modify the partition function by keeping a variable count which stores the total number of equal elements and if count = r-p+1 then we'll return (p+r)/2.
7.1.4. We can simply change the partition function i.e. instead of the comparsion A[i] <= x we'll make a comparision A[i] >= x.This way all the elements which are greater than x are put on the left side of x.
7.2.2. When all the elements have the same value the running time will be O(n^2) if we use the partition function given in the book.
7.2.3. When the array elements are sorted in decreasing order then every call to the partition function will return r-1 thus it'll give us the worst case time complexity of quicksort.Thus running time will be O(n^2).
7.3.2. In the worst case we'll have to make O(n) calls which seems obvious from worst case arguments about partition given in the previous question.
Though for the best case we may think that the number of calls made to the random function is O(log n) but this is wrong, in the best case also number of calls made will be O(n).
Proof: The best case occurs when the partitioning produces two subproblems of size atmost n/2. It is atmost this because onewill have bn/2c elements and one will have dn/2e − 1. The recurrence for the calls to RANDOMIZED-PARTITION is then
T(n) ≤ 2T(n/2) + Θ(1)
By case 1 of the Master Theorem, T(n) has the solution
T(n) = Θ(n) in the best case.
So, Θ(n) calls are made to RANDOM in the best and worst cases.
7.4.5. The value of 'k' picked will be such that insertion sort on an array of size 'k' performs better than the quicksort.
Isn't the right answer of 7.1-2 r instead of r-1? In the last iteration iside the for it makes i = i + 1, so i = r - 1, and then it returns i + 1 which is r - 1 + 1 == r.
ReplyDeleteSo the answer of the exercises 7.2-2 and 7.2-3 is straightforward because the division will be n-1, 0 resulting in quicksort's worst case.
Sorry, for my mistake(may be I overlooked it). It'll be r only. I'll update it thanks for pointing it out.
Delete