Quadratic time to sort in a simple case?
Xinok
xinok at live.com
Tue Apr 23 10:42:05 PDT 2013
On Tuesday, 23 April 2013 at 14:12:01 UTC, bearophile wrote:
> Andrei Alexandrescu:
>
>> There's not "the C++ STL sort". Any implementation is fine as
>> long as it has O(n log n) expected run time.
>
> This seems to use the Introsort:
> http://www.sgi.com/tech/stl/sort.html
>
> I don't know if Xinok has tested a 2-pivot quicksort (called by
> the usual Introsort setting).
>
> Bye,
> bearophile
On an average case, two-pivot quick sort will increase the number
of comparisons by about 50%, reason being that about half the
elements will be greater than the first pivot and have to he
compared to the second pivot. There's also a greater complexity
given there are three partitions rather than two, increasing the
amount of I/O necessary.
Introsort is simply a quick sort which falls back to a heap sort
after so many recursions to guarantee O(n log n) performance.
I've implemented this using a median of five and it works
excellent. This is what I plan to contribute to Phobos.
Choosing a random pivot will always invoke "average" performance
where as finding the median of N elements usually achieves better
performance on sorted lists. You also have to be careful that
equal elements are distributed equally among both partitions,
else a list with many elements equal to the pivot will still
achieve poor performance. (equal elements would all fall onto one
side of the pivot)
More information about the Digitalmars-d-learn
mailing list