News for hackers. Stuff that matters.
Re:Bjarne Stroustrup Answers C++ Questions by butterisgood on Tuesday October 15, 2019 @09:00AM (#21257884)
A technique I’ve heard used but never tried is to run a single pass of bubble sort first. If you swap any elements, run quicksort.
Re:Bjarne Stroustrup Answers C++ Questions by gpderetta on Tuesday October 15, 2019 @09:07AM (#21257936)
C++ standard library implementations use introsort, so they never hit quicksort worst case.
Re:Bjarne Stroustrup Answers C++ Questions by KerrickStaley on Tuesday October 15, 2019 @02:12PM (#21261729)
std::sort is not required to use any specific algorithm; it only guarantees that it uses an O(N log N) worst-case algorithm (since C++11, before C++11 the guarantee was average-case O(N log N), see https://en.cppreference.com/w/cpp/algorithm/sort).
Re:Bjarne Stroustrup Answers C++ Questions by gpderetta on Tuesday October 15, 2019 @03:35PM (#21262739)
It is not guaranteed, but all the libraries do. In fact in the past the bound was O(N²) as the expectation was that quick sort would be the default choice, but because all implementations used introsort, the bound was thighened.
Re:Bjarne Stroustrup Answers C++ Questions by magicalhippo on Tuesday October 15, 2019 @09:06AM (#21257930)
QuickSort using middle element or median should perform optimally no?

The middle (median) element in a sorted array has only less elements on the left and greater elements on the right, so the first pass of the quicksort would do nothing and not recurse further.

Or am I missing something?

Re:Bjarne Stroustrup Answers C++ Questions by jonsen on Tuesday October 15, 2019 @09:56AM (#21258355)
Try this

  4 3 2 1 5 9 8 7 6
Re:Bjarne Stroustrup Answers C++ Questions by magicalhippo on Tuesday October 15, 2019 @10:16AM (#21258566)
I should have stayed in bed today...

Still, probably faster to incorporate a monotonic check in a quicksort first pass, than run a bubble-sort pass which probably won't help much anyway?

Re:Bjarne Stroustrup Answers C++ Questions by gpderetta on Tuesday October 15, 2019 @10:46AM (#21258960)
Introsort, which used by the C++ standard libraries, switches from quicksort to heapsort for the (sub)partition for which has exceeded the expected recursion depth, so it is guaranteed to run in worst case O(nlogn) for all inputs.

edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.