Talk:Quicksort

Contents

1 (Older discussions) 2 Capitalization 3 My recent drastic changes 3.1 changing Θ() to O() ? 4 C implementation 5 C++ Code 6 That partition algorithm seems wrong 7 updated the C code 8 Partitioning statement seems wrong 9 in-place sort 10 Capitalization 11 Average complexity 12 Could anyone write this addition on the article? 13 Introductory pseudocode change 14 omega?

(Older discussions)

Quicksort can actually be done in O(n log n) time worst case, by carefully choosing the pivot - the algorithm to do so is a bit complex though. See http://www.comp.mq.edu.au/courses/comp333/Lecture/divide-and-conquer_4.pdf for details. -- SJK

Just choose the true median as the pivot. You can find the true median in Θ(n) time, and since partitioning takes Θ(n) time too, you are not increasing the complexity. Since the median guarantees perfect halving, you have O(n log n). You definitely increase the constant factor, though. Also, finding the median in Θ(n) time is quite complicated. -- Hari

For the record, this is mentioned in the Relationship to selection section. Derrick Coetzee 17:11, 17 Sep 2004 (UTC)

---

The article uses list to mean sequence of elements. But the terminology is confusing because quicksort does not work on linked lists. I think list should be changed to array everywhere in the article. -- Arvindn

Er, QuickSort works just fine on linked lists, as long as you write your implementation using linked lists and not arrays... Or so I'd think Chinju

Yep. The key operation is "partition", which is essentially an operation to split a queue/stack/bag into two queues/stacks/bags. You can define a nice partition function for linked lists. -- Hari

Quicksort actually is particularly suitable for doubly linked lists, because it only accesses elements sequentially (although in both orders). It doesn't even require any extra storage. For singly linked lists though mergesort is probably the way to go. Heapsort doesn't work on linked lists at all. Perhaps this is worth adding to some comparison sections. Derrick Coetzee 17:11, 17 Sep 2004 (UTC)

This so-called "realistic data" in which one needs to use a random number generator to ensure proper performance... What kind of data would that be? Data that's already been pre-sorted to make things hard for you? It seems to me this is business about using a random number generator is the result of inaccurate thinking about probability rather than a realistic concern (except, of course, in the case mentioned in the article where the data is fed to the algorithm by an adversary). Does anyone mind if I remove most of the discussion about random number generator usage?

Also, the article mentions that Quicksort can be optimized since every element needs only to be compared against the (mostly unchanging) pivot element ("The inner loop which performs the partition is often very amenable to optimization as all comparisons are being done with a single pivot element"). What exactly is meant by this? How exactly can one take advantage of that situation for optimization? Just wondering...Chinju 21:53 Mar 6, 2003 (UTC)

I adjusted the random pivot wording based on real-world knowledge that lists are often partially sorted and random isn't the best for that situation. Random is fine if the data isn't partially sorted but humans don't have to be purists when optimizing algorithms.:) The seldom changing pivot element may let it be held in a register or improve the locality of memory references. JamesDay 15:46, 22 Oct 2003 (UTC)~

---

"This works well in practice but chance can still place the lowest element in the middle and cause worst case performance."

Unclear. Putting the list's lowest element in the middle would not cause worst case performance, or even make it worse than O(n log (n)). If it kept happening at every level of the recursion, that would cause worst case performance all right, but that's very unlikely, and is a possibility for any quick and simple way of choosing a pivot.

I agree. I've reworded that and added a bit to the one I described as "best", since that does have higher overhead and can't always be best. In the rewriting I did I was trying to get away from the over-emphasis of the performance with attack data and left in a criticism which middle element choice didn't deserve so much in the general case. JamesDay 12:47, 28 Oct 2003 (UTC)

---

Sorry about the unnecessary alphabetizing. I must be going blind since I completely overlooked the intro to the section that the explained ordering of algorithms. Richss 03:17, Sep 8, 2004 (UTC)

Frankly, I found the ordering by length of code peculiar, considering most of the shorter examples are in non-mainstream languages and aren't efficient in practice. In particular, 5 different functional language examples may be overkill. Perhaps alphabetical would be less biased. Derrick Coetzee 03:49, 8 Sep 2004 (UTC)

• 5 different functional language examples may be overkill —actually, the first eight samples are written in functional languages... nevertheless, the first four are all fundamentally different from each other (even the Miranda and NGL entries, which look somewhat alike, are really different: the former is value-level, the latter function-level). The Erlang, Haskell, and Miranda entries are indeed completely analogous, though (however, which to leave out and how to justify the choice? for then we should also choose between the Java and C# implementations) The OCaml and CL entries are closely analogous in spirit to those three, but expressed very differently. Regarding efficiency, some of those first eight implementations are not only clear, but very fast. If speed were the only concern, then the right example would be in assembler.

Anyway, the article is about the algorithm not about popular or mainstream prog langs, and this provides some support to having the shortest implementations come first. Alphabetical order is best when political correctness or the like are in order. IMO, this is not the case: it is not a matter of giving preference to one or another prog lang, it is a matter of keeping the interests of the reader of the article above everything else. This is, in fact, one reason for moving the samples section to the end of the article, right past the External Links, See Also, and References section. With some of the longest samples among the first, an alphabetical ordering makes it very hard for the article reader to realize that there are vastly different ways of expressing the quicksort algorithm in different prog langs. It becomes Just imagine if someone comes with an assembler implementation that takes 200 lines... Furthermore, the shortest-first arrangement is more informative than the alphabetical one in the sense that with the latter it is very hard for the user to find out several things that can be readily glanced with the former: which implementations are alike, wich is the shortest one, etc. If there were dozens of implementations, then the alphabetical listing would indeed come in handy in order to locate a particular one, but this doesn't apply for small numbers. — danakil 05:06, Sep 8, 2004 (UTC)

My thought had not been about somebody reading the article for pleasure (whom you wish to keep interested). Rather, I was thinking about what someone like myself would be doing, which is using it as a reference (encyclopedia) to see an example in whatever language I am using.Richss 12:04, Sep 8, 2004 (UTC)

• I'm sorry, Richss. I hadn't intended to convey the idea of reading for pleasure (although now that you mention it, it doesn't seem to be a goal to strive to keep the reader entertained). By keeping the interests of the reader [above all] I certainly meant to tender to the interests of those who use Wikipedia as a reference tool.—danakil 16:24, Sep 8, 2004 (UTC)

It's true that efficiency is not the main concern, and I concede that the functional examples are sufficiently different, but can you really call a sort which isn't O(n log n) at all quicksort, even if it makes the same exchanges in the same order? (referring here to the example using list comprehensions - I'm not sure how the others work out) I agree that the number of examples is so far small enough that it's easy enough to spot your favourite language in the listing. Derrick Coetzee 14:25, 8 Sep 2004 (UTC)

• I agree with you: it seems reasonable to require that a sort be actually O(n log n) in order for it to be called quicksort. Nevertheless, I'm sure there would be quite a few moors entrenched in that coast. Furthermore, there are quite a few different Haskell implementations, I wonder if all of them suffer from the same problem (I've heard several people claim that Miranda is much faster than the common Haskell implementations—Miranda is a commercial product while Haskell's use is mainly academic). On the other hand, the J,NGL,OCaml entries are, IME, certainly O(n log n), though. And I would be surprised if the Erlang and CL ones weren't. One final remark about performance: if someone was implementing production quicksort using Java, C, C++ or C#, he/she would likely go the non-recursive route. It would be nice to have an example of that. — danakil 16:15, Sep 8, 2004 (UTC)

Just out of curiosity, can somebody provide an explanation (possibly just a link to an explanation) of why the list comprehensions make the Haskell implementation of quicksort have an average case complexity of Theta(n^2) instead of Theta(n log n)? Thanks. Chinju 05:28, 26 Sep 2004 (UTC)

Doesn't seem Theta(n^2) to me. It is inefficient since partitioning that way means traversing the list twice, but it's still a Theta(n) operation, as well as the performed list concatenation (which could also be avoided). So the final complexity just depends on the number of times you'll perform those operations (which depends on how the partitions turn out). --jadrian 00:35, 29 Sep 2004 (UTC)

Yeah, it seems Theta(n log n) in the average case to me, despite the inefficiencies you pointed out, which is why I was curious as to how the quadratic complexity was derived. If I can't find any explanations soon, I think I'll remove the notice about being "O(n^2) on average". --Chinju 19:38, 30 Sep 2004 (UTC)

I don't oppose this change. The original statement probably had to do with excessive delay of computation in Haskell implementations without memoization, in that if you fully expand out the quicksort expression for a given Haskell list before evaluating it, you end up with a very large expression. Just a guess though. Derrick Coetzee 20:32, 6 Oct 2004 (UTC)

---

"Note that the partition procedure only requires the ability to traverse the list sequentially in both directions; therefore, quicksort is not confined to operating on arrays (it can be used, for example, on doubly-linked lists)."

No, it does not require that. Doing it with singly linked lists is trivial. --jadrian 23:34, 16 Oct 2004 (UTC)

You're right, this isn't hard, since the order of elements in the resulting sublists is unimportant, allowing you to build them both backwards. I'll update the comment. Derrick Coetzee 04:40, 17 Oct 2004 (UTC)

Capitalization

Perhaps this is a stupid question, but is quicksort capitalized (Quicksort) or not (quicksort)? What does the original paper do? What's common practice? Derrick Coetzee 04:48, 17 Oct 2004 (UTC)

A well-implemented quicksort requires at most lg(N) partition boundaries on the stack. Instead of recursing for both left and right partitions, recurse for the *smaller* partition, then "adjust" the partition boundaries at the current call level and loop. For N, say, one billion, the depth of recursion will not exceed 30 (as at each level of recursion the number of elements is at most half what it was at the preceding level). One-sided recursion is an *old* idea.

Pseudo-C Pseudo-code to illustrate the point:

quicksort(array, left, right) //say right-left+1 = Z, then... {

 while (left-right>threshold)
 {
   pivotPosition = partition ( array, left, right);
   if (pivotPosition-left < right-pivotPosition)
   {
     quicksort(array, left, pivotPosition-1); //at most Z/2;
     left = pivotPosition+1;
   }
   else
   {
     quicksort(array, pivotPosition+1, right); //at most Z/2
     right = pivotPosition-1;
   }
 }
 insertionSort(array, left, right);

}

-- james_barbetti@yahoo.com

If you read a little further in the article you'll find a description of partially tail-recursive quicksort (which is what you describe) including pseudocode. Deco 23:59, 20 Nov 2004 (UTC)

My recent drastic changes

I moved almost all of the examples from this article to quicksort implementations; I think they were getting far too numerous, exceeding the rest of the article in size by multiple times. I attempted to leave behind a small set such that no two were too similar, the popular languages were mostly covered, and most of the basic implementation techniques were covered. I also extracted some of the introsort discussion to an article on introsort, not because it was too long but because I'd like to see introsort expanded in the future and it wasn't poised to do that as a section in this article. I've probably upset some people whose favourite language was moved out, and I removed some I rather like myself, but I think it benefits our readers to keep the focus on the quicksort algorithm itself. Deco 00:54, 21 Nov 2004 (UTC)

changing Θ() to O() ?

I see someone changed a bunch of Θ() to O(). Is this correct, or a misunderstanding of the debate at Talk:Big_O_notation ? --DavidCary 07:15, 15 Dec 2004 (UTC)

C implementation

Has anyone tested the C implementation? There seems to be a bug in the algorithm, and the swap function won't work, as C uses call by value.

Swap could be implemented as a macro — it's really acting as pseudocode there. I'll have a look at the rest of it later. Deco 17:52, 28 Dec 2004 (UTC)

C++ Code

The C++ code was taken from http://tinylink.com/?rSqs5OMuCj without notification of the original author. That's very bad style and shouldn't happen on wikipedia. I removed it for now, hoping someone comes up with another version.

That partition algorithm seems wrong

The partition algorithm given seems wrong to me. If the first item is larger than the pivot, for example, it swaps it with itself and then moves on. Am I missing something, or is this just a mistake? RSpeer 20:57, Feb 21, 2005 (UTC)

I added some statements to try to help address your confusion. The swap is only done if the pivot is less than or equal to the pivot (not greater), but it might so happen that an element larger than the pivot is swapped into a position preceding the pivot's final position. The trick is that an element may be moved multiple times before reaching its final place, so this is okay. I hope that makes some sense. Deco 02:24, 24 Feb 2005 (UTC)

It seems that other people are confused by the partitioning algorithm as well. (I guess the frustrated anon defacing the page would be one example.) What is the advantage to this algorithm, and why don't we use the one from CLRS? RSpeer 03:07, Mar 21, 2005 (UTC)

updated the C code

i added a little more code to the C example.

i felt that the original example provided on the wiki was elegant and good for explanatory purposes, however, i felt it would be prudent to include a C example that could be copy-pasted into a source file.

i added an optimization to the original code's partitioning logic because i noticed it copied a ton of elements unnecessarily.

i also pulled a variable out of the if() block and made it static to save some memory.

using the first element as the pivot is a clever, elegant solution to the pivot selection problem; however, i wanted demonstrate that this solution could be adapted to an arbitrarily selected pivot very easily. hence, i used a bit of 'forbidden' preprocessor magic to keep the code usable while still conveying this point.

hope my edits are okay with everyone and thank you all for this page, it's very informative!

i cleaned up the C++ code (made the pivot more clear) and added an optimization from the C code.

Partitioning statement seems wrong

This statement looks wrong to me:

Because the above pseudocode procedure will sometimes swap elements which are equal, it is slightly unstable.

To my knowledge, there is no known in-place stable partitioning algorithm (and I've looked). The issue is not merely that it sometimes swaps equal elements (which is easy to fix), but that it can swap an element over an element which is equal to it. Consider this list:

7, 7, 3, 1, 4

The very first exchange would exchange the 4 with the first 7. Now, the first 7 is following the second 7, where before it was preceding it. This is an unstable exchange.

Of course, if you partition not-in-place, by building a list of those less-or-equal and those greater, each preserving the original list order, then the sort is stable.

In short, I'm deleting it, because it's wrong. :-) Deco 06:11, 4 Mar 2005 (UTC)

in-place sort

For the edit that was just made (deleting "it's an in-place sort"): the definition of in-place sort was wrong. Whoever wrote it said that it meant that elements already in their proper place would not be moved. That is completely false: in-place sort means that the algorithm has O(1) (constant) memory requirement. That's on the page now; everything is now as it should be regarding that. Decrypt3 18:56 EDT, 4 April 2004

When Deco claims "there is no known in-place stable partitioning algorithm", I'm pretty sure that *includes* Quicksort. If Wikipedia is going to standardize on a definition of the term In-place algorithm that excludes Quicksort, we need some other term to describe algorithms like Quicksort and Tree traversal. What term would you suggest? What do you call algorithms that are not in-place" ? --DavidCary 05:03, 13 Mar 2005 (UTC)

The partitioning step of quicksort is in-place. It's the recursive step that isn't. RSpeer 06:56, Mar 13, 2005 (UTC)

Yes, my comment was meant to emphasize that most in-place partitioning algorithms are unstable, and most stable ones are not in place. Most variants of quicksort, however, are not in-place because they use a stack of depth at least log n (in fact, if the values being sorted may be arbitrarily large, it requires log²n space, where n is the total number of bits). The distinction between additional storage on the call stack and explicit additional storage is really a purely artificial one created by hardware and programming languges. You can easily write a version of quicksort that makes no recursive calls but manages an explicit stack of O(log n) size.

The closest thing I can think of for describing the class of algorithms you refer to is DSPACE(log² n), which is the class of problems that can be solved in space log² n, where n is the total number of bits in the input. Any algorithm that has log n recursive depth and log n bits in each stack frame lies in it, including quicksort and recursive tree traversal. Tree traversal has a number of simple in-place versions, though. Deco 07:59, 13 Mar 2005 (UTC)

To clarify, I refer here to the partially tail-recursive variant of quicksort, and to tree traversal of a complete binary tree. Other cases can require more space. Deco 08:10, 13 Mar 2005 (UTC)

Some additional comments: quicksort is not a partitioning algorithm. It is a sorting algorithm. It uses partitioning as a subroutine. Algorithms that aren't in-place are sometimes called not-in-place, and I don't know of any briefer name. Deco 20:35, 13 Mar 2005 (UTC)

Capitalization

This article uses both "Quicksort" and "quicksort", in a hideously inconsistent way. Which way should it be? - Fredrik | talk 09:47, 21 Mar 2005 (UTC)

I've asked before — no one can seem to decide. I would vote we do it however Hoare did it, but unfortunately I have no access to his paper. Mathworld seems to use lowercase quicksort however, and this seems nicer to me and more consistent with other sort names. I'm leaning towards quicksort if there is some consent. Deco 04:54, 29 Mar 2005 (UTC)

Average complexity

The average complexity given can't be right. Quicksort is O(n log n), which makes Θ(1.39 log n) impossible. --P3d0 15:27, May 12, 2005 (UTC)

Could anyone write this addition on the article?

[This information has been removed]

I'm afraid this violates our Wikipedia: No original research policy. Deco 19:27, 20 May 2005 (UTC)

You could have informed me before. It took me two hours writing that explanation in english. Oh, well. I thought this would be the perfect page to release the optimization for everyone. I'm going to remove the C source code, too. Thank you, anyways.

Who could have informed you before? --P3d0 23:51, May 20, 2005 (UTC)

Hey people, isn't a kind of harsh to delete the post and just tell a newbie that wikipedia is not a place for original research? While this cannot be put to the article, we can suggest that he (or possibly she) post it to Usenet or something else. Also, I don't think we have to remove the post. We tend to keep this kind of somehow irrelevant posts at the talkpage. See Japanese war crimes for example. Finally, I think P3do, your comment is a little too unhelpful or unfriendly; apparently, this guy is upset. I mean aren't we allowed to have little more fun and friendly yet irrelevant conversations in the talkpage?

Since his method appears to be neat, I restored it to my user page. See User:TakuyaMurata/Barcelo's method. I am very curious if this really results in actual improvement. -- Taku 00:27, May 21, 2005 (UTC)

He removed the information himself after being told that it violates the NOR policy. Fredrik | talk 07:13, 21 May 2005 (UTC)

I don't get where he stores his 'blank' space. Furthermore, I don't see how it's any improvement over swapping. -- AllyUnion (talk) 07:09, 21 May 2005 (UTC)

I'll try to explain it a bit better. As you have to take one element from the list - the pivot - to store it in a variable/register in order to make the comparisons, you can use the position it occupied as a 'blank space'. The pivot is already stored in a variable, so you only have to return the pivot to the 'blank' space at the end of the algorithm, and use it meanwhile.

This is very helpful if the 'blank' space is at the start (or end) of the list, because then you can search the list from the other side, and when you find an element which is lower than the pivot, copy it to the 'blank space' directly, overwriting it. After you copy an element, it becomes the new 'blank space', so you can start searching from the other side.

It's important to note that the 'blank space' stores old info until it's overwritten, so this might cause that an index moves too far, even outside the limits of the array. However, this problem can be fixed without losing efficiency.

This requires much less reading/writing than the swapping function, which must preserve the values of both elements, and thus needs to store one of them in a 'temp' variable. This improvement should be more noticeable as the size of the elements increases.

Hmm... my version of understanding of quicksort was that the pivot was stored in the list... and that the only temporary variables you had was the index positions which were passed recursively. -- AllyUnion (talk) 07:52, 25 May 2005 (UTC)

Sorry if it looks confusing, but it's already confusing to explain it in my own language. -- DrJones 10:28, 21 May 2005 (UTC)

Could you please change the name to Hoyos' method? Barcelo is my second surname, which works much like the middle initial in english. -- DrJones 10:28, 21 May 2005 (UTC)

I already put an encouraging comment and suggested he post it to Usenet at Talk: Quicksort implementations. I have nothing against the guy, but of course we're not putting original research in the article. It's still cool that he wrote it up though and I'd encourage him to pursue these ideas and show them to people. If it does end up in a paper somewhere, we really could add it then. Deco 23:33, 21 May 2005 (UTC)

My bad :) As Fredrik pointed out, that was all my misunderstanding. Deco, I should have known what kind of person you are by now. Also I missed Talk:Quicksort implementations. I was unaware of that article. -- Taku 23:49, May 21, 2005 (UTC)

Introductory pseudocode change

I tried to rewrite the first pseudocode to be easier to understand, per Fredrik's comments at Wikipedia:Featured article candidates/Quicksort. I based this version on the Haskell version, but I avoided using list comprehensions or funny things like that, expressing it using more familiar imperative constructs and some English. I moved the other version into a new section and added explanation for the in-place partition algorithm, which is really rather subtle. Deco 03:09, 25 May 2005 (UTC)

I have to say, i don't find the pseudocode any easier to read than the C version - in particular it seems extremely verbose for what is really a very simple algorithm. Further, i would imagine that most people have more experience with a C-like language. Is the pseudocode merely designed to mimic that found in Cormen + Rivest (which benefits from much nicer formatting than here) or is there some other reason for having it? --Shashmik11 12:52, 13 Jun 2005 (UTC)

The idea of pseudocode is that you can understand it without knowing what language-specific symbols like & mean. Sure, it's perfectly natural to you, because you know C. But actually, lots of people are now learning to program in languages other that C. RSpeer 13:28, Jun 13, 2005 (UTC)

I accept that some people might not know C, but the idea that the pseudo-code shown is free from language-specific details is wrong - it seems to be some odd variant of algol. I still contend that code written in this way isn't actually any more readable, especially things like select a pivot value which should really be typeset differently from the rest of the code. All in all i think the pseudocode would be much better if it wasn't typeset using a fixed width font, but maybe that's just me. Shashmik11 14:45, 13 Jun 2005 (UTC)

I agree it should ideally not be typeset in this way. However, typesetting it properly makes it impossible to edit, which I think would be against the wiki spirit. The point of the change was not to make it easier to read but easier to understand - the typical C version uses an in-place partition algorithm that is, while simple, not as obvious as the out-of-place partition algorithm used in some functional implementaions and the first pseudocode example. The language/syntax is largely irrelevent, as long as it doesn't rely on symbols that are unfamiliar to a large portion of programmers (like the typical functional language example). Incidentally, I've heard people compare my pseudocode to Pascal, ML, C, Python, and now Algol — I really wish they'd make up their mind which language I ripped off. Deco 04:18, 14 Jun 2005 (UTC)

Point taken. Maybe wikipedia should get some sort of pseudo-code renderer in a similar manner to the way equations are rendered. How would one campaign for something like this?--Shashmik11 11:41, 18 Jun 2005 (UTC)

That'd be cool. I'd start with Wikipedia: Village pump (technical), since this would be a feature request. You might want to talk somewhere on meta (http://meta.wikipedia.org/) about it, since it affects all Wikimedia projects. Somehow I imagine, though, that you might have trouble garnering support for something with an "easy workaround" (doing it how we do it now). Deco 00:33, 19 Jun 2005 (UTC)

omega?

What is Ω(n)? (In the section "Version with in-place partition") -- Tarquin 07:51, 17 Jun 2005 (UTC)

It's asymptotically bounded from below by n, not from above. Ω(n) means it takes time at least on the order of n, where O(n) would mean at most on the order of n.