4 ms·
The already sorted collection is a classic example for Quicksort's worst-case scenario -- specifically for implementations where the pivot point is the first el
by Igelau 7y ago
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.
- butterisgood 7y agoA 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.
- magicalhippo 7y agoQuickSort 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?
- jonsen 7y agoTry this 4 3 2 1 5 9 8 7 6
- magicalhippo 7y agoI 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?
- gpderetta 7y agoIntrosort, 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.
- gpderetta 7y agoC++ standard library implementations use introsort, so they never hit quicksort worst case.
- KerrickStaley 7y agostd::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 https://en.cppreference.com/w/cpp/algorithm/sort).
- gpderetta 7y agoIt 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.
- greggman2 7y agoI noticed that when I wrote a visulization. Plain quicksort on equal values is by far the slowest. http://greggman.github.io/doodles/sort.html http://greggman.github.io/doodles/sort.html
- koolba 7y agoVery cool visualization!
- mattmar96 7y agoThis is fantastic
- Sohcahtoa82 7y agoInteresting 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.