Especially when writing 'standard' (non-HPC) applications, do you consider what sorting algorithm to pick, or just settle with quicksort (which is what most libraries just call sort)? To some extent it may be profitable in specific situations, but on the other hand proper optimization requires some time to analyse the problem and make benchmarks.
Add a comment
|
6 Answers
In general, using the default methods unless there is a specific need to do something more exotic keeps everything a lot more readable/understandable down the road IMHO.
If you experience (or in some cases, strongly suspect) that you have a performance problem that is the time to add complexity.
On the other hand, if you are using a low enough language that there is not a built-in sort for the kind of objects you need to sort try to pick one or two that cover all your bases and implement those.
Always call the library routines provided, unless you have very, very good reason not to do so (and you need to document why it is so).
This is because sorting algorithms are hard to get absolutely right. There was a bug in the Java quicksort with very large datasets, which was identified, fixed and delivered to customers by Sun, so you didn't have to.
Also the default sort in Java 7 has been upgraded to a newer, better sort. Also for free.
Unless the default sort is provably not good enough for you, stick with it.
At a conference once I heard a nice story about this.
At Microsoft someone was writing a VB app (c. VB 3) and mailed a bunch of people saying that he had a load of values and he wanted them to appear in the combobox in order, how should he go about it.
Everyone dived for their old computer science text books, looking up highly efficient routines and porting them to Visual Basic and mailing them to him. One guys just mailed back "how many values in the combobox?".
"About 50" came the reply.
"Just set the sorted property to TRUE".
In 99.9999% of instances sorting is best done using a library, control or in the SQL select as the performance difference between the library routine and anything you write will be negligible and the effort and maintenance overhead will massively outweigh the consequences.
answered Dec 22, 2010 at 13:27
This is the time to pull out the classic quote about premature optimization. In most cases, it really doesn't matter. Heck, with the speed of CPUs these days, you could probably bubble sort most data sets and not really notice much. But when you're sorting really large data sets, and sort performance starts to become an issue, then you should definitely look at other options.
answered Sep 20, 2010 at 22:23
-
Bubble sort? Its performance is the worst for average and worst-case, and equals insertion sort for best case. There is no reason that it should be used.– HippoNov 20, 2010 at 4:47
-
1@Hippo: I wasn't actually advocating using bubble sort. I meant that modern computers are fast enough that in most cases it doesn't matter how slow your algorithm is because the user won't notice. Nov 20, 2010 at 4:59
-
Although it obviously doesn't matter to the bits and timeslices. I find merge sort to be easier to write and understand than quicksort. So if I'm going to write my own sorting algorithm I'd use that.
answered Sep 20, 2010 at 22:21
-
Viva mergesort! And a mildly better constant term, and no horrific worst-case. Oct 14, 2010 at 16:16
At least in a competently written library, I'd expect the built-in sort to be implemented as an Introsort rather than just a Quicksort. The difference rarely matters much, but Introsort eliminates the bad worst-case performance of Quicksort with minimal effect on the more common cases.
To answer your question, however: yes -- that's what you should usually start with, and until/unless you have profiler results indicating that it's a problem, that's where it should remain.
answered Sep 20, 2010 at 22:51
