On 10/9/10 9:05 CDT, "Jérôme M. Berger" wrote:
Seth Hoenig wrote:
2010/10/8 "Jérôme M. Berger"<jeber...@free.fr>
Steven Schveighoffer wrote:
On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke<rain...@eldwood.com>
wrote:
I can't say I've ever cared about the big-O complexity of an operation.
Then you don't understand how important it is.
If big O complexity is so important, then why does everyone use
quicksort (which is O(n**2)) and not heap sort or merge sort (which
are O(n*log(n)))?
Jerome
Because on average quicksort is faster than heap sort, and uses much less
space than merge sort. Also, trivial guards can be put in place to avoid
running quicksort in a worst case (pre-sorted data) scenario.
I rest my case.
Jerome
In fact, guards can be put to ensure that the _expected_ (not average,
not best-case) complexity is O(n log n). This makes the risk of hitting
a worst-case scenario negligible in a principled manner.
http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
http://docs.google.com/viewer?a=v&q=cache:MdBVR26N5UsJ:www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf+randomized+quicksort&hl=en&gl=us&pid=bl&srcid=ADGEESi3GTSxfHWkeb_f14H0pkbigduS94qJVc9XLQ7aPa6lPUJ5JZbggI0izFe3ogiVOJCYcVkGtdumaS9hBvrGw0-TA_yZQj2qd1-AEudKyEWEGXnO4sTwqCZL95OpFkdFHDF2WXFV&sig=AHIEtbT1R0q5RIR4rob17QUKlYVl90vXyQ
Currently std.algorithm.getPivot picks the middle of the range as the
pivot, but I made it modular such that it can be improved in a number of
ways (i.e. randomized, median-of-3, median-of-5, etc).
Andrei
