Another thing, you should consider if the sort method is adaptive or not. For instance, quicksort 2-way is not adpative but quicksort 3-way is.
Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jan 6, 2011 at 10:19 AM, Wladimir Tavares <[email protected]>wrote: > 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.
