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‎

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)