pivot position plays important role in determining the time complexity of the algorithm. suppose array is already sorted then if you go by obvious means by selecting pivot element as the 1st element of the input array,then recurrence will be :- T(n)=T(n-1)+theta(n) hence complexity of the algo will be O(n^2). actually if you form a recurrence tree you will see that it form like a skewed tree , so at every stage you are not dividing the problem into 2 parts.
if we are lucky we will have pivot element arnd the center of the array,now this will divided the problem into T(n/2)+theta(n) = nlogn. so suppose you are competing in sorting challenge and me as your opponent will give you sorted input so that i can get a plus point over your algo. so how can we avoid this ?? now as we know by now that time complexity is dependent on the input format(inc/dec order or nearly sorted).we can make it interdependent of this input format by randomizing the input sequence OR we select random pivot instead of selecting 1st element as pivot. This is know as randomized quick sort.now quicksort will no longer dependent on the input sequence but worst case complexity still remain O(n^2) , because if your random generator function given input as sorted sequence complexity still be O(n^2). On Sat, Sep 15, 2012 at 7:43 PM, sulekha metta <[email protected]>wrote: > hi every one!! > how does pivot position effect the efficiency in quick sort > algorithm > thanks in advance > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
