News for hackers. Stuff that matters.
Re:Bjarne Stroustrup Answers C++ Questions by cosarara on Tuesday October 15, 2019 @08:04AM (#21257583)
Question #1 was misunderstood. This is not about sorting a sorted vector, it is about processing a sorted vector, in general. The example code of the question sums the values. The example code of the answer does `sort(v.begin(), v.end());` in run(). It is obvious that sorting something that is already sorted shouldn't take much effort. Not so that adding all the values together should be faster if the values are sorted.
Re:Bjarne Stroustrup Answers C++ Questions by robmccoll on Tuesday October 15, 2019 @09:39AM (#21258202)
His answer does include what I would think is the correct reason in that specific case though - branch prediction on the if(data[c] >= 128) line. When the array is sorted, you would go from not taken to taken only once and likely get correct predictions nearly 100% of the time versus the shuffled list producing a rate around 50% depending on the predictor.

Also check out the first response for a nice explanation and an optimization to eliminate the branch. The author replaced it with a bit twiddling solution to either store the current element or zero if it is less than 128 in a temporary variable and then always add that to the sum.

Re:Bjarne Stroustrup Answers C++ Questions by Igelau on Tuesday October 15, 2019 @08:54AM (#21257851)
The already sorted collection is a classic example for Quicksort's worst-case scenario -- specifically for implementations where the pivot point is the first element.

It's not obviously easy either. You won't know if an arbitrary collection is already sorted unless you check each element.

Re:Bjarne Stroustrup Answers C++ Questions by greggman2 on Tuesday October 15, 2019 @09:02AM (#21257897)
I noticed that when I wrote a visulization. Plain quicksort on equal values is by far the slowest.

http://greggman.github.io/doodles/sort.html

Re:Bjarne Stroustrup Answers C++ Questions by Sohcahtoa82 on Tuesday October 15, 2019 @04:03PM (#21263049)
Interesting things happen on that page when you click on one of the sorts to see it in a bigger window, then you close it, then click it again. You can end up with multiple sorts running at the same time.
Re:Bjarne Stroustrup Answers C++ Questions by koolba on Tuesday October 15, 2019 @12:02PM (#21259948)
Very cool visualization!
Re:Bjarne Stroustrup Answers C++ Questions by mattmar96 on Tuesday October 15, 2019 @12:25PM (#21260266)
This is fantastic
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.

Re:Bjarne Stroustrup Answers C++ Questions by lordnacho on Tuesday October 15, 2019 @09:40AM (#21258220)
In this case the processing seems to be deciding whether the number in the array is in the top half or bottom half. Branch prediction (assuming some simple heuristic) on that would be wrong once if it's sorted, but half the time when it's not.
Re:Bjarne Stroustrup Answers C++ Questions by rhacker on Tuesday October 15, 2019 @09:03AM (#21257906)
It is also vague what "processing" means in this context. Just about everything you do is processing already, so there really shouldn't be a "reason" it is faster to "process" an unsorted or a sorted array. Now if we're given a hint at what the processing is, then we might be able to get further.
Re:Bjarne Stroustrup Answers C++ Questions by cosarara on Tuesday October 15, 2019 @09:05AM (#21257923)