Randomized quick sort .. even the worst case in this algo is O(n^2) also, this is best sorting algo .. It is showed that nearly 20-25% of time O.S spends its time in sorting.In unix based systems , they are using this algo only .. A random choice will only choose from middle parts half the time. However, this is good enough. Imagine that you are flipping a coin over and over until you get *k* heads. Although this could take a long time, on average only 2*k* flips are required, and the chance that you won't get *k* heads after 100*k* flips is highly improbable. By the same argument, quicksort's recursion will terminate on average at a call depth of only 2(2log2*n*). http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
On Thu, Sep 8, 2011 at 11:08 PM, aayush jain <[email protected]> wrote: > very easy qus...which is the best sorting tech. n why????? > > -- > 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. > -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers <=> Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> * Mobile +91 8056127652* <[email protected]> -- 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.
