4 ms·
The quicksort implementation is incorrect. The code simply picking the left-most element as the pivot, and as a result it becomes pathologically slow for nearly
by HardyLeung 15y ago
The quicksort implementation is incorrect. The code simply picking the left-most element as the pivot, and as a result it becomes pathologically slow for nearly-sorted array -- for example, run bubblesort then quicksort, or run quicksort twice -- not to mention potential stack overflow problem due to O(N) recursive call.
- maggit 15y agoPoor choice of the pivot makes the implementation bad, but absolutely not incorrect.
- cschneid 15y agoThat's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time.
- leif 15y agoThere are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical). Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.
- xentronium 15y ago> That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time. Pick median of three random elements as pivot; it's hard to pick wrong pivot every time unless your RNG always returns 7.
- Robin_Message 15y agoWhy three random elements though? If you expect some structure in the array, then picking pivots based on that structure makes more sense (e.g. first, middle and last for sorted, reverse sorted for partially sorted arrays). On the other hand, if you are sorting unsanitised input, then random is good, but it should be secure pseudo-random numbers if it's important to your security/performance whilst under attack.
- deleted 15y ago[deleted]
- sirclueless 15y agoAdd the following right above the line "pivot = left" to fix it: VA.swap(left, Math.floor(Math.random() * (right - left + 1)) + left)
- CountHackulus 15y agoAlternatively you can insert this code for the median of 3 version: centre = (left + right) / 2; if VA.lt(left, centre) if VA.lt(centre, right) VA.swap(left, centre) else if VA.lt(left, right) VA.swap(left, right) else if VA.lt(centre, right) VA.swap(left, centre) else if VA.lt(left, right) VA.swap(left, right)
- thedufer 15y agoI said this in another comment, but I coded up the simplest version of each algorithm - the quicksort is correct, just not optimal. The focus was on letting people write their own code, not the pre-written algorithms.