Talk:Quicksort

Wrong algorithm

Several of the statements on this page including the definition of the "simple" algorithm are quite baffling when considered in the context of Hoare's original 1962 paper about quicksort, which explicitly defined quicksort as an in-place algorithm that used in-situ exchanges to partition with the explicitly stated goal of minimizing memory consumption in order to improve performance. These characteristics are what makes the genuine quicksort algorithm quick. The "simple" algorithm described on this page captures none of these characteristics and, consequently, is far from quick. Specifically, it is orders of magnitude slower. Perhaps this "simple" algorithm should be stripped from this page along with the unjustified statements about its relative popularity and a citation to the authoritative primary source be added?
194.74.155.52 (talk) 19:59, 17 February 2011‎

I put a {{disputed section}} on the section Simple algorithm, because I agree with you. I've seen publications from the FP (Haskell) community where it's claimed that this is quicksort:

-- Off the top of my head
sort []  = []
sort [x] = [x]
sort (p:xs) =  sort left ++ [p] ++ sort right
  where (left:right) = partition p
        partition p xs = ([x | x <- xs, x < p], [x | x <- xs, x >= p])

... and this is what this section is describing, except in "simple", quasi-imperative pseudocode. As for WP:V, it is possible to find sources that describe this kind of "quicksort". However, it is not how CLSR define quicksort:

Quicksort(A, p, r)
 if p < r
  q = Partition(A, p, r)
  Quicksort(A, p, q - 1)
  Quicksort(A, q + 1, r)

To me, this is classic quicksort. It's an imperative, in-place algorithm, with no append or concatenate operations. Just move the pivot around, and then recursively sort the subarrays as completely independent subproblems, with no postprocessing. QVVERTYVS (hm?) 21:21, 28 May 2014 (UTC)

qsort

qsort should not redirect to this page, but rather something C-related as it is part of the standard library. Whenever qsort is used, it is always used in reference to the C-implementation which may not necessarily implement the Quicksort algorithm. To any extent; this should at least be mentioned.

Needs reformatting

The image description under section Algorithm overlaps with the simple algorithm. Otherwise a stellar article. OceanicMeerkat (talk) 00:15, 28 January 2014 (UTC)

What does "a.o." mean?

In the "History" section there appears:

"Quicksort gained widespread adoption, appearing a.o. in Unix as the default library sort function" . . .

What does "a.o." mean? I've been a UNIX hacker for long enough to wonder if somebody misspelled "a.out". (No, because "a.out" wouldn't make any sense in such a usage.)

Accordingly I suggest that "a.o." is overly obscure whatever it was intended to mean.

And I am curious about what was intended. — Preceding unsigned comment added by 134.134.137.71 (talk • contribs)

"Among others". Actually the grammar may be a bit off: the intended meaning is that quicksort appeared in Unix and other systems, but it seems to say quicksort and other sorting algorithms appeared in Unix. (Also true because sort(1) was not a quicksort, IIRC, but not intented.) QVVERTYVS (hm?) 10:02, 13 March 2014 (UTC)

Choice of Pivot - Median

The text says:

..., choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick) [ref]

I've added "Clarification needed" because according to the Median article, the median of three elements is the middle element; therefore, according to the text, there would be no difference between such a Median method and the middle index method. Would someone please expand the article to better explain what that means? --pgimeno (talk) 20:40, 6 April 2014 (UTC)

The median of [3, 1, 2] is 2. The middle element is 1. QVVERTYVS (hm?) 21:32, 6 April 2014 (UTC)

Guess I was confusing indexes and values. Thank you, it makes sense now. --pgimeno (talk) 15:50, 7 April 2014 (UTC)

Fat partitioning complexity

Here's an interesting remark:

The standard version of Quicksort requires n log n comparisons, where n is the number of input items; the UNIX version requires at most n log m comparisons, where m is the number of distinct input values. —McMahon, Lee E.; Cherry, Lorinda L.; Morris, Robert (1978). "UNIX Time-Sharing System: Statistical text processing" (PDF). Bell System Technical Journal. 57 (6).

This seems to refer to the use of a "fat" (three-way) partition function, which was implemented in Unix's qsort at a very early stage. QVVERTYVS (hm?) 12:54, 24 April 2014 (UTC)

dual-pivot

The variant described at http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 is apparently missing from the article. — Preceding unsigned comment added by 68.183.92.232 (talk) 23:30, 10 May 2014 (UTC)

first time through loop in "In Place" code

    storeIndex := left
    for i from left to right - 1
        if array[i] ≤ pivotValue
            swap array[i] and array[storeIndex]
            storeIndex := storeIndex + 1

---

On the first time through, i is "left" (why not just say 0 for a zero-based array?) and storeIndex is also "left"

if array[left] is actually less than pivotValue then: swap array[left] and array[left]

What?

68.183.92.16 (talk) 00:10, 13 May 2014 (UTC)

This special case of "swap" is commonplace as it simplifies many algorithms. It just means "do nothing". McKay (talk) 00:46, 13 May 2014 (UTC)

Two answers for two questions.

1. 'Why left, not 0?'
   Because the same routine is called in a recursion for many different parts of the array, and it is usually described with three parameters: array, leftmost index of the part being handled and rightmost index of the part being handled. If you program e.g. in a C language then of course you can pass a reference to the leftmost item and the part's length. However, some languages do not offer such flexibility in transforming array item's address into array, so describing the algorithm this way would make it 'impossible' for those languages. Anyway this kind of optimization does not speed things up significantly – the asymptotic complexity remains the same.
2. 'Why swap item with itself?'
   Because it's simpler. Such swaps do not hurt (they don't destroy data) nor they slow down the program significantly, whilst dropping the test makes the algorithm more readable. You can easily check inside the swapping routine whether the two objects are actually the same and then skip swapping and return. You can also add the test in the caller routine, if you care of additional jump into the subroutine.

--CiaPan (talk) 20:24, 14 May 2014 (UTC)

Re: impossible in other languages, that doesn't matter because this is pseudocode. I've actually been pondering a pointer-based pseudocode for some time, but I haven't found a syntax that is obvious enough. Pointer-based quicksort can be written more compactly and is IMHO easier to verify than the version using indices. QVVERTYVS (hm?) 22:07, 14 May 2014 (UTC)

I disagree. That does matter, especially in pseudocode, because pseudocode is for outlining the general algorithm structure for those who can't read a specific programming language. That also means non-programmers. And for many readers it is easy to consider 'sorting THIS PART of a GIVEN ARRAY' and rather strange to accept 'sorting some (NEW? ANOTHER?!) array, overlapping (?) a part of the given array'. The latter is common in C, but the pseudocode should translate easily to as many languages as possible. We explain the algorithm here, so we need notation simple and general, with no tricks and shortcuts. We do not introduce any optimizations specific to some language or environment – that is an implementor's role.
BTW, I'm a bit curious about 'Pointer-based quicksort can be written more compactly' – have you tried to write a 'pointer-based quicksort' in Delphi/Pascal? in Fortran? or in Java? Do they support such flexible pointer arithmetics as C does, allowing to use 'dereference(pointer + number)' as 'n-th item of the array'? --CiaPan (talk) 22:41, 16 May 2014 (UTC)

I beg to differ. I prefer my pseudocode consistent, short and readable, and that means I'll invent any language feature that I need to get rid of irrelevant details. Easy translation is not the goal, understanding is. Hence, I don't care how well an algorithm description maps to Pascal, Fortran, Java, or the languages that I use (which include C and languages without pointer arithmetic). I want it to be written in an easily understood pseudo-language. QVVERTYVS (hm?) 11:00, 18 May 2014 (UTC)

I side with CiaPan here. Pointers are not needed for the algorithm and if it is in place then it should be possible for exposition purposes to say quickly exactly where in place the subarray is. However as far as swapping with itself is concerned I think there should at least be a comment saying that is possible on the line. In pointer terminology it is important to note if pointers are restricted or not. Dmcq (talk) 11:51, 18 May 2014 (UTC)

I won't change the algorithm to use pointers. But I don't see the point in explicating the possibility of a self-swap. It should be pretty obvious that swap(a, i, i) is a no-op. QVVERTYVS (hm?) 13:50, 18 May 2014 (UTC)

I agree about swap, but it is good way to catch smarty-pants C programmers who define SWAP(a,b) as a ^= b; b ^= a; a ^= b so that they don't need a temporary variable. (If a and b have the same location, this just sets it to 0.) McKay (talk) 06:25, 21 May 2014 (UTC)

== algorithm is incorrect the shown partition function has a different signature then the one used in quicksort:

partition(array, left, right, pivotIndex) // 4 arguments — Preceding unsigned comment added by 62.178.185.230 (talk) 09:25, 5 June 2014 (UTC)

== algorithm is incorrect the shown partition function has a different signature then the one used in quicksort:

partition(array, left, right, pivotIndex) // 4 arguments