Well Friends, to deside which method shout be used you should ask Some important questions you should ask yourself are:
- How expensive are comparisons?
- Are comparisons monolithic, or is there a useful notion of partial comparison?
- How many items are there to sort?
- Are the items basically in random order?
- How limited is memory?
- How bad are cache misses?
To use the answers to those questions, you'll need to be familiar with sorting methods. I'm not going to teach you; there's lots of accessible literature on the subject. But some quick examples of how these criteria might influence your choice of algorithm:
- If there are very few items, then the fast algorithms don't pay for the overhead. Insertion sort is probably the way to go.
- If the cost of comparisons dwarfs everything else, then you may want to minimize the number of comparisons. It's hard to do better than something like insertion sort with binary search to find the insertion location.
- But if you can do partial comparisons, like with strings, then radix methods are an obvious candidate.
- If the problem has no outstanding characteristics, then quicksort is a good first choice, but it has some gotchas. You can read about that in a textbook.
- How expensive are comparisons?
- Are comparisons monolithic, or is there a useful notion of partial comparison?
- How many items are there to sort?
- Are the items basically in random order?
- How limited is memory?
- How bad are cache misses?
To use the answers to those questions, you'll need to be familiar with sorting methods. I'm not going to teach you; there's lots of accessible literature on the subject. But some quick examples of how these criteria might influence your choice of algorithm:
- If there are very few items, then the fast algorithms don't pay for the overhead. Insertion sort is probably the way to go.
- If the cost of comparisons dwarfs everything else, then you may want to minimize the number of comparisons. It's hard to do better than something like insertion sort with binary search to find the insertion location.
- But if you can do partial comparisons, like with strings, then radix methods are an obvious candidate.
- If the problem has no outstanding characteristics, then quicksort is a good first choice, but it has some gotchas. You can read about that in a textbook.
No comments:
Post a Comment