Talk:Sorting algorithms/Quicksort

Task statement is buggy

If array elements are all equal then pseudocode's version of quicksort never returns. A 14:52, 14 July 2008 (UTC)

---

Details I'm uncertain on:

• Should it be the in-place form of quicksort, or is it unspecified?
• What is a discrete type?
• Should the program as given work for all arrays with indexes "of any discrete type", or should I pick one "discrete type" and give an example with that?

--Kevin Reid 15:42, 3 October 2007 (MDT)

I'd say follow example of the Bubble Sort page (from which I stole the text). In other words, do whatever is most comfortable in your language, perhaps pointing out the design choices made. --IanOsgood 19:02, 3 October 2007 (MDT)

Yeah, the problem statement is completely wrong. The algorithm described is not the real quicksort but a bastardized version that was promoted by the Haskell community that avoids mutation at the cost of asymptotically more space consumption and, consequently, it is practically worthless because it runs hundreds of times slower than a real quicksort (but it can be written concisely in Haskell!). The problem statement should be changed to a real in-place quicksort that actually works. --Jon Harrop

Algorithm description

Would someone care to add some text describing the Quicksort algorithm? I.e., its worst-case completion time, a pseudocode implementation, what the pivot does, etc. --Short Circuit 03:28, 7 October 2007 (MDT)

UnixPipes solution

It seems to me that the UnixPipes implementation violates the conditions given on Category:UnixPipes: There you find:

It does not include programming problems solved with normal shell by using the control structures available as a part of shell outside of pipelines.

However the quicksort implementation here uses the following shell constructs:

• named function
• while loop
• case statement

So either the example, or the UnixPipes description is wrong. --Ce 15:41, 7 April 2008 (MDT)

The intension in UnixPipes description is to include only those solutions that use the pipelines as computational paradigm. (So as to exclude the imperative solutions in normal shell) Since I do not seem to have captured the intension correctly, I will remove that line from UnixPipelines until I can think of a better way to put it. Thanks for the attention. Rahul 02:36, 8 April 2008 (MDT)

MATLAB... works?

Does MATLAB work? It defines a function named quicksort, but then calls qsort; and the return after the function declaration... if it is like Octave, it makes the program terminate so that the test is never run (maybe the file where you stored the code was called qsort? this could fix something... but doesn't MATLAB complain about the fact that your file is called qsort while your function is quicksort? --ShinTakezou 23:04, 25 June 2009 (UTC)

I've fixed that; I'm used to short names; after entering the code and looking at the whole page, it occurred to me that I should use the same name that everyone else was using. --mecej4 11:53, 26 June 2009 (CDT)

Fortran-90 code ... pivot choice can cause it to go O(N^2)

If the input numbers have a distribution which plots as a symmetric triangle, the first and last elements will be equal and their mean is a bad choice for pivot. --mecej4 12:21, 26 June 2009 (CDT)

Note that the problem isn't that it's a bad pivot choice. It's that the comments say it's a good pivot choice. Other examples have bad pivot choices (Java just picks the first element), but the task doesn't require a good pivot choice. --Mwn3d 17:25, 26 June 2009 (UTC)

The comments say just it's a good pivot choice for already sorted data or for reverse sorted data; I haven't checked it, but I can believe it, as I can believe it's not a so good choice for "symmetric triangle" distribution. --ShinTakezou 18:44, 26 June 2009 (UTC)

IDL

"IDL has a powerful optimized sort() built-in. The following is thus merely for demonstration."

This is true for most languages represented here, either as a built-in or in included standard libraries.