[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?
Before you throw the baby out with the bath water, test Quicksort on representative data. No, Quicksort doesn't sort as fast with a lot of duplicates, but in my tests, Quicksort STILL beats a lot of/ or even all of, the suggested substitute sorters. It's work, but you can "tune" Quicksort, to handle data with more duplicates, etc. There's no replacement for an actual test on the actual system, with good representative data. > > 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? Once it's tuned, and tested, (and if Quicksort is OK otherwise for your purpose), I would change it when Hell froze over. :) How the pivot point is selected can be crucial, and when the sub groups get down to some single digit value (3-7 say), then having Quicksort switch over to a selection or insertion sort might be helpful. The pivot point is sometimes critical, but the switch is usually a small optimization. The important thing is not knowing when to switch away from Quicksort to save time - because that's REALLY rare, and the amount of time saved will be very small. The important thing to remember is to try and get your in-memory sorting, done by Quicksort, rather than some other (slower), program. That's the big time saver. Just for laughs, when you hear a particular sorting algorithm is good on some particular type of data, try it and compare it with Quicksort's performance, on the same data and system. I'd bet money you'll have some enlightening surprises. The only downside to this, is that Quicksort is easily "broken" - it may sort, but not at near the speed it could. If you tweak it, always test it! Adak --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
