You can use some techniques to improve quicksort:
- randomized pivot - use insertion sort for small vector ~10 - use non recursive approach - median of some element chosed randomized - when you have many duplicate keys, you can use 3-way partition<http://www.sorting-algorithms.com/quick-sort-3-way> Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jan 6, 2011 at 12:52 AM, Gene <[email protected]> wrote: > This is correct. It ensures there can be no degenerate partitions and > improves the worse case run time to be asymptotically equal to the average > case. > > In practice you would want to use a simple pivot selection algorithm and > only resort to SELECT when the simple algorithm fails to produce a partition > within a fixed fraction of 50/50. > > > > > -- > 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]<algogeeks%[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.
