Run time Analysis of QuickSort ,Nature of Input,Pivot strategies

Question Determine the running time of QuickSort for

a.Sorted input
b.reverse -ordered input
c.random input
d. When all the elements are equal



Solution:This solution is being written with the assumption that middle element of the array is chosen as the pivot.The answers differ based on the pivot selection as well.
a.Sorted input
In the case of sorted input,the left and right pointers of the sub arrays pass each other with out a single swap in all the iterations.The problem is divided in to 2 equal problems in all but the base case of unit size array.Hence the recurrence relation for this case is T(N)=2*T(N/2)+O(N).Hence the complexity in this case is O(NlogN).

b.reverse-ordered input

This case is identical to the previous case except that we have so many swaps in each iteration.The left and right pointers swap the content on each increment in their directions.This effects only the O(N) part of the recurrence relation that we have in the previous case.But as the swap is of complexity O(1), the complexity of each iteration remains the same.And the division of the array is still even.So the complexity doesn't change.Hence it is still O(NlogN)

c.Random Input
Well there are theorems asserting that the complexity of quicksort on a random input is O(NlogN).We will prove it by considering evenly the chances of even and worst splits.
let's consider that good and bad splits alternate in the iterations, with good splits in the best case (N/2) and bad ones in the worst (N-1).
So every two levels, the array's been cut in half,which means, it's still exponential reduction -- O(NlogN ).

d. When all the elements are equal

It is as good as the sorted array.So the complexity is O(NlogN).

Question The ones who are familiar with QuickSort might also be well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?


Solution:Choosing the middle element never makes it unlikey that the QuickSort will require quadratic time.One might encounter an input in which the middle element is always the maximum in all iterations.Then the complexity will be quadratic.

example:a={1,3,2} choosing 3 as pivot produces 2 subproblems , one of size 0 and other of size 2.In the next iteration,with out loss of generality take 2 as the pivot.It produces a sub array of size 1 and another of size 0.Thus an input can always be generated in such a way that QuickSort routine always gives rise to 2 subarrays,one of them being of size 0.Hence quadratic time is not always avoidable.

Question What is the worst-case behavior (number of comparisons) for quick sort?
Solution:As we have seen in the previous question,because of a bad pivot selection we might at the worst run in to quadratic time complexity.

Question In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:
a.The first element of the array
b.The last element of the array
c.The middle element of the array
d.The largest element of the array
e.The median of the array
f.Any of the above


Solution:while the choices a,b,c will always not guarantee O(NlogN) complexity,choice d always gives quadratic run time.choice e guarantees even partition of the array.Hence it is the optimal partition.
hence the sol is e.

Question In its worst case QuickSort behaves like:
a.Bubble sort
b.Selection sort
c.Insertion sort
d.Bin sort


Solution:In the worst ,the pivot selected will always be the maximum element leading to quadratic time complexity.In this case as it depicts the behaviour of bubble sort,where in maximum element always bubbles to the end.

for more questions click here