big-O notation is also misleading, for the reasons we discussed (and because of some practical reasons, such as hidden architectural costs), and should not be used for speed claims. Benchmarks are the proper tool for speed measurements. That said, quicksort's worst case performance is O(n^2) and this does show up with distressing frequency in real data.
But, I should also point out that quicksort is unstable only if it is implemented that way. The quicksort implementation at http://code.jsoftware.com/wiki/Essays/Quicksort is an example of a stable quicksort, since it retains the original order of equal elements. If I recall correctly, Microsoft's qsort is an example of an unstable quicksort (because the mechanism used for copying equal elements reverses them). Thanks, -- Raul On Fri, Oct 27, 2017 at 5:44 AM, Erling Hellenäs <[email protected]> wrote: > I understand that. Still big-O is used as a speed estimate and Quicksort is > one of the best sorts. The video is misleading. /Erling > > Den 2017-10-27 kl. 10:59, skrev Raul Miller: >> >> Not exactly - big-O notation is not about speed, it's about shape of >> the resource consumption curve. >> >> If one algorithm consistently is 1000x slower than another, for all >> choices of data, they would both have the same big-O structure. >> >> It's important to understand these things when discussing them. >> >> Thanks, >> > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
