typo error :- we can make it *independent** of this input format On Sat, Sep 15, 2012 at 11:56 PM, atul anand <atul.87fri...@gmail.com>wrote:
> 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 <metta.sule...@gmail.com>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 algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
