[EMAIL PROTECTED] wrote: > Hi, > > > Hope that you can help me with this one. Relative to what I have read > "Quicksort" it is a very good sorting algorithm. However, there can be > trouble if there is a high level of duplicates. > I have 2 questions based upon this
> Q1: Can anyone recommend a good sorting algorithm that works well with > a high level of duplicates are present? Any good quicksort partitioning scheme will handle duplicates without taking a performance hit, e.g., Sedgewick's version which stops on equal keys. http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html If you have a huge number of duplicates, consider 3-way quicksort. It runs in linear time on some inputs, e.g., if there a constant number of distinct values. > Q2: At what point should one considered moving from quicksort -> other > algorithm that works well with duplicates? Are there any useful metrics > in determining the level of duplicates e.g. > Duplicate Level = Total # of Duplicates / Total quantity of Elements > At what point should you consider crossing over? There are certainly some reasons why you might prefer another sorting algorithm over quicksort, e.g., stability, but duplicates should not be one of them. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
