Talk:Quicksort

Blog interview

The new blog post that purported holds an interview with Tony Hoare isn't needed — most of the history contained in it has already been divulged by Hoare in other places. I'll try to find out where so we can get rid of the blog. QVVERTYVS (hm?)

New external links

I would like to offer my page of animated illustrations about Quicksort (http://www.chrislaux.com/quicksort.html) for the external links section. I believe the animations explain Quicksort nicely visually to go with the text-focussed explanations here.

Ctlaux (talk) 19:00, 3 September 2019 (UTC)

@Ctlaux: Please see WP:External links and WP:Directory. Adding where you have a conflict of interest was not the best approach. — billinghurst sDrewth 23:52, 22 September 2019 (UTC)

Hoare Partition Scheme - reverted psuedocode back to the prior scheme in the article

I reverted the pseudocode back to a prior version (one that had been in the wiki article for years), since that variation corresponds to most references for Hoare partition scheme (apparently Hoare's original algorithm?) and it has also been confirmed to work (while the version I reverted appeared to be off a bit from known working variations, and went through a couple of updates, and I don't know which variation of those updates is a known working implementation. Rcgldr (talk) 14:04, 22 September 2019 (UTC)

We work to cited versions, so please cite a version, and that version should be supported by references. Just saying that I am going back (something) is just problematic. Especially when you have left in other problematic edits, which were part of the undoing. — billinghurst sDrewth 23:50, 22 September 2019 (UTC)

@Billinghurst:My edit reverted the psuedocode back to what it was from 11:24, 3 August 2015‎ made by Sytelus, when the Hoare partition scheme pseudocode was first added to the article, through 05:20, 21 June 2019‎. I did not research the references for the pseudcode that was added back in August 2015, but it's been there for almost 4 years with no changes. The change from |do while| to |while| was made on 00:03, 28 June 2019‎ by Cosmic Cloud, with no cited references for that change. My feeling is that the psuedocode should be reverted back to its original version, before the unreferenced change made by Cosmic Cloud. Rcgldr (talk) 05:53, 23 September 2019 (UTC)

@Rajgopalbh4:Please read prior comment. The revision you made undoes the pseudocode that originates back to when Hoare partition scheme was first added to the article in August 3, 2015 to a change that was made almost 4 years later in June 28, 2019, by Cosmic Cloud with no cited references for that change. Rcgldr (talk) 06:29, 23 September 2019 (UTC)

• The time and date should be 01:37, 7 August 2015 also made by‎ Sytelus, as that was the first version with a cited source: Introduction to Algorithms. Rcgldr (talk) 20:37, 23 September 2019 (UTC) Rcgldr (talk) 12:36, 24 September 2019 (UTC)
  • @Rcgldr: Timestamps of specific edits can be sometimes difficult to use if a page was edited multiple times within a day, because users may have different timezones defined in their preferences and see different (local) times at the same edits. It may be most confusing if the edit in question was made early or very late, close to midnight, as not only an hour but also a date may appear different. The safest, and the unique, ID of an edit is its serial number. You can use it either as a link to a specific version of the page: Special:PermanentLink/674924601 or as a link to changes made in that version: Special:Diff/674924601. --CiaPan (talk) 09:35, 4 February 2020 (UTC)

@CiaPan: I wasn't aware that the timestamps could be changed from UTC or how to reference an edit by serial number. However in this case, I did wan't to establish a date as part of the timeline of changes (Hoare Partition scheme added, updated with cited reference, 4 year later change (not cited)). If I do this again, I'll mention it was a UTC time stamp and include the edit id. Rcgldr (talk) 14:57, 4 February 2020 (UTC)

• The current version of the algorithm doesn't work. The pivot element will end up randomly on either side of the partition. It has to be "put aside" and swapped back in at the end, just like with the Lomuto partition scheme (see https://algs4.cs.princeton.edu/23quicksort/) --212.51.137.13 (talk) 14:34, 2 February 2020 (UTC)

It's not an issue, and it's already explained in that article's section: "In this scheme, the pivot's final location is not necessarily at the index that was returned, and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme. However, the partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion." The pivot and/or elements = pivot may not be placed into their final sorted position until partition size is reduced to 1, but the algorithm works. Rcgldr (talk) 17:52, 2 February 2020 (UTC)

(ec) If you say ‘the current version of the algorithm doesn't work’, please show an array which is not properly handled by the algorithm.
The point is we simply do not care where the pivot element lands at the end of the partitioning routine. By the algorithm principle, for the algorithm to be correct it's enough that both partitions are not empty and each item in the left partition is not greater than each element of the right partition. The partitioning routine fulfills both requirements, hence the algorithm is correct. If you say otherwise, please support your claim with appropriate counterexample. --CiaPan (talk) 18:05, 2 February 2020 (UTC)

References

Hoare's 1962 paper - mentions some things credited to Sedgewick

A link to a web page with a link to a pdf file of one of Hoare's 1962 papers can be found here (you don't have to pay or join a group to download this one).

https://academic.oup.com/comjnl/article/5/1/10/395338

The computers Hoare was working with didn't have a stack, so he essentially invented one which he called a "nest". Hoare mentions in order to limit "nest" (stack) size, only the smaller partition parameters would be pushed onto the "nest" while iteration would be used on the larger partition. The Wiki article currently credits this idea to Sedgewick in two places (optimizations, space complexity).Rcgldr (talk) 14:06, 23 September 2019 (UTC)

@Rcgldr: This description in your comment is wrong:

Hoare mentions in order to limit "nest" (stack) size, only the smaller partition parameters would be pushed onto the "nest" while iteration would be used on the larger partition

Such routine could lead to a stack holding O(N) single-item partitions in the worst case.

It's exactly the other way in the Hoare's text:

In order to ensure the number of segments postponed at any one time never exceeds the logarithm (base 2) of the number of items to be sorted it is sufficient to adopt the rule of always postponing the processing of the larger of the two segments.

– at each step the larger partition gets pushed to the stack and postponed, while the partitioning is iterated on the shorter one. As a result, at each recursion level we get at most half of the previous level's data, hence it's up to log(N) recursion levels (and used stack levels) possible before the partition size drops to 1. --CiaPan (talk) 20:51, 22 October 2019 (UTC), expanded 10:00, 23 October 2019 (UTC)

Hoare also mentions that pivot values need to be reasonably random (implies that choice of pivot may need to be randomized) in order to avoid O(n^2) time complexity. I don't see where the Wiki article credits Hoare for this idea.Rcgldr (talk) 14:06, 23 September 2019 (UTC)

Hoare's paper is missing some details. It mentions the scanning stops when the pointers cross, but the scanning also has to stop if the pointers meet (equal). It doesn't mention which pointer should be used to split the partitions, other than to guarantee that a split reduces partition size by at least 1 element (to prevent infinite loop). Rcgldr (talk) 14:06, 23 September 2019 (UTC)

Hoare mentions using sentinel values for keys (the comparison values) to stop the scans rather than bounds checking on pointers, but if the pivot is chosen from the middle, or at least not from either end of a sub-array, this isn't an issue, as either the pivot or a swapped value will stop either scan.Rcgldr (talk) 14:06, 23 September 2019 (UTC)

Addition of Content on Quicksort for Linked List

Information to be added to the end of the Variants section:

Linked List Quicksort

The Quicksort is typically taught using a bidirectional partition method appropriate for in-place exchange of array elements. However, the Quicksort algorithm allows partitioning to be performed in any manner. In this variant, the partitioning method is performed by a unidirectional iteration in which nodes with a lesser key than the pivot node's key are unlinked from their current list location and then inserted into the sublist before the pivot node, which can be implemented in a way that makes the Quicksort stable for linked lists. This variant was compared empirically with linked list merge sort, and it performed more slowly due to non-optimal list dividing, which resulted in more key comparisons.

A bottom up linked list merge sort is faster still than a top down merge sort, and doesn't involve any halving of lists. A bottom up merge sort considers a list of n nodes as n sub-lists of size 1, merging one node at a time into a small (26 to 32) array of lists where array_of_list[i] has 2^i nodes. Merge_sort#Bottom-up_implementation_using_lists Rcgldr (talk) 21:17, 1 January 2020 (UTC)

Hi @Rcgldr:, I agree that what you say is true here, but it seems like it is most relevant where it already is. In this quicksort page, existence of linked list quicksort is missing along with the point that it is empirically slower than merge sort. That linked list quicksort might therefore be even slower than a bottom up merge sort is likely true but draws a conclusion that crosses the line into originality (no direct source to back up the direct comparison). So, it seemed better to reword to talk about the quicksort's suboptimal dividing (which increased key comparisons) and sidestep talking specifically about the exact operation of the merge sort that was actually used. The quicksort would need more comparisons in any case. Thanks for commenting, JohnBoyerPhd (talk) 00:30, 4 January 2020 (UTC)

@JohnBoyerPhd: I'll have to see if I can find web site sources for this. I had correspondence about this issue with P._J._Plauger - one of the authors of the Dinkumware template library used by Microsoft for Visual Studio and other compiler makers, noted that the scanning of lists to split them added significant overhead to merge sort that bottom up merge sort avoids. This is probably mentioned in one of his published works. I've also seen this mentioned in some old textbooks (an analysis showed something like a 40% overhead), but I don't recall the name of the textbook names, so finding a reference there would be difficult. Rcgldr (talk) 16:27, 9 January 2020 (UTC)

Explanation of issue:

The quicksort is most typically taught as a partition _exchange_ sort (see Knuth and many others). The exchange design was evidently due to Quicksort being developed originally for an array, and this design precluded its use on singly linked lists (which have no backward pointer). Via web search, one can easily find implementations of linked list quick sort that have appeared on many knowledge sharing platforms in the last 10 years (For example, see [cboard post]). As the content in this edit request shows, linked list quicksort has been available since the 1990s. Since it is easily found on other knowledge sharing platforms, the proposed content fills an omission from Wikipedia as a knowledge sharing platform.

References supporting change:

• Donald Knuth The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging.

• Hoare, C. A. R. (1961). "Algorithm 64: Quicksort". Comm. ACM. 4 (7): 321. doi:10.1145/366622.366644.

• Boyer, John M. (May 1998). "Sorting and Searching Linked Lists in Java". Dr. Dobb's Journal (285): 126–129, 137–138. Retrieved November 23, 2019.

• Robert Sedgewick Algorithms in C++, Part 3: Sorting, Third Edition, p. 321. Addison-Wesley, 1998. ISBN 0-201-35088-2.

References

Reply 24-NOV-2019

  Edit request declined  

• The policies against using only self-published sources as references for these particular claims, as well as those advising against using original research, prevent these changes from being made. The COI editor is urged to provide references from reliable, independent, WP:SECONDARY sources in order to verify the claims proposed here.

Regards,  Spintendo  23:56, 24 November 2019 (UTC)

Response 15-DEC-2019

The matter has been discussed extensively on the @Spintendo:'s talk page. The discussion has resulted in the above substantially revised proposed text. Based on the discussion, the sources were not self-published sources. The one article authored (not published) by this author in the revised proposed content is permitted by Wikipedia policy here as it is a single citation published by a reliable source. The revised proposed content also does not violate the no original research policy because the revised proposed content follows the policy requirements for citing a primary source. Specifically, the revised proposed text does not "analyze, evaluate, interpret, or synthesize material found in a primary source," it changes less than 1% of the Quicksort article and so does not "base an entire article on primary sources," and the revised proposed content makes only two "straightforward, descriptive statements of facts that can be verified by any educated person with access to the primary source but without further, specialized knowledge" and so does not "add unsourced material from [my] personal experience, because that would make Wikipedia a primary source of that material." It's clear that the no original research policy exists to prevent Wikipedia from becoming a primary source, not to prevent it from citing primary sources. Therefore, please reconsider this revised edit request. JohnBoyerPhd (talk) 22:35, 15 December 2019 (UTC)

I still don't see any independent sourcing for the variant. Without that, this seems like undue weight. - MrOllie (talk) 23:07, 15 December 2019 (UTC)

There is an error in grammar in the newer request: It states the Quicksort algorithm allows partitioning to be performed in any manner. (referenced by the Hoare source). The very next sentence begins with In this variant, the partitioning method is performed by a unidirectional iteration.. (referenced by the Boyer source). My question is, which of Hoare's "any manners" does this variant in the second sentence refer to? My guess is it's the variant that Boyer has proposed in their research. If that's the case, then considering the Hoare source was written 38 years before Boyer's was published, how does that source verify Boyer's claims? Please advise. I would also add that the changes you've made to your request did not follow the guidelines for changing previous posts at WP:REDACTED, thus there is no simple way to see what you've changed as opposed to what you previously submitted, which is unfortunate. Would you please repost the references that you removed (and place them below this post).  Spintendo  23:51, 15 December 2019 (UTC)

Hi @Spintendo:, If you click through to Hoare's paper to see what it says, you see that Algorithm 64 is really a short piece of text that presents only the algorithm Partition, Quicksort, Quicksort. It is and is intended to be the most broadly applicable algorithm that covers any method that partitions first in any way then recursively sorts the two partitions. This is exactly how broadly stated algorithms can apply to other papers written later. Hoare's algorithm applies to all other papers cited in the Quicksort page as well as the DDJ source. In the variant that is discussed in the proposed subsection, the any manner is given in the cited source as a unidirectional iteration, which is what the sentence says. Regarding the WP:REDACTED, noted for the future, as nothing on the edit request page describes this process. In the meantime, the design of Wikipedia platform is such that the source appear on the [history page]. Thanks, JohnBoyerPhd (talk) 06:03, 16 December 2019 (UTC)

Hi @MrOllie:, The undue weight characterization is not at all applicable to this type of content in general, nor this specific content. This content proposes 2 sentences that provide one point of view among the plethora appearing in the rest of the 5000+ word article. Thanks, JohnBoyerPhd (talk) 06:03, 16 December 2019 (UTC)

Hi @Spintendo:, I'm just checking in to see if you have been able to decide if you want still want to decline the revised comment for a revised reason, or if you see that the compromises made in revising the content along with the answers to your questions above and the discussion of the applicable policies are now sufficient for you to accept the content? Thank you, JohnBoyerPhd (talk) 03:34, 20 December 2019 (UTC)

The intro to the Boyer paper states "This paper presents a novel approach for a generalized comparison by transforming the problem into comparing executed code size of a benchmark imperative algorithm with a partially declarative variant of the same algorithm." The key words here are a novel approach for a generalized comparison. Please indicate what it is, about this novel approach, which negates its novelty simply because the generalized comparison it is performing is upon a broadly-stated algorithm. Regards,  Spintendo  21:37, 30 December 2019 (UTC)

Notes

Hi @Spintendo:, The paper that you are quoting from is not cited in and not a part of the linked list quicksort content proposal that we are discussing. At the very beginning of this, you merged two separate and distinct content requests that I made (variants of quicksort: Linked List Quicksort and Partially Declarative Quicksort). Since then, you've expressed such an amount of concern about the second of those requests, based on the article you continue to object to, that I removed the whole content and citation related to that second request (partially declarative quicksort). Please see the actual revised content request above. The article you object to just simply is not there. The only thing that we are discussing is my first content addition request about Linked List Quicksort-- not partially declarative quicksort and so not the article you have been objecting to. Can you please review the content currently proposed? Also, to reflect the current state of the discussion, please remove your prior objection for the cause of SPS since we got past that on your talk page a long time ago. Thank you, JohnBoyerPhd (talk) 22:25, 2 January 2020 (UTC)

Hi @Spintendo:, I've now added a secondary reference to substantiate the variant, per your request. The secondary source support comes from none other than Robert Sedgewick, so hopefully that will be satisfactory to both you and @MrOllie:. Thanks, JohnBoyerPhd (talk) 00:30, 4 January 2020 (UTC)

@JohnBoyerPhd: First of all, the changes that you've made on this talk page to your older posts were not made according to the guidelines at WP:REDACTED. Those guidelines state that you must use underlined font for additions and strikeout font for subtractions. Nothing is supposed to be deleted. The fact that you've gone back and deleted content that we've been talking about here is not at all helpful. How are editors supposed to evaluate your "newer" request when you've deleted the older request, so much so that there is now no longer a starting point to compare the newer material to. Editors are no longer able to easily see how and in what way a problematic reference that you removed applies to the evolution of your request, and your recommendation that editors simply "check the history" is hardly constructive to the overall request in general. In order to proceed with full transparency, I would ask that you restore the deleted content in a post below, and that you then explain how it differs from what you're requesting now. I think you'll find that editors are better able to follow your explanations when you don't delete content they've already read. Regards,  Spintendo  09:41, 5 January 2020 (UTC)

Notes

Hi @Spintendo:, I did not delete the so-called problematic reference from my request. You merged two different requests I made, a fact that I have mentioned to you many times. I removed the text of the second request to undo the content merge that you performed. The linked list quicksort variant never cited that reference.

Furthermore, there is no lack of full transparency. It's four sentences. And, it's very much aligned with what I proposed during our discussion on your talk page a long time ago. This was a discussion that I assumed was following a cooperative Wikipedia:Negotiation process, so yes the content is different now-- that's what compromise looks like.

And... it's four sentences now. So, no, I will not restore the deleted content because 1) it would restore your damaging merge of my two requests, 2) it is easy enough to see in the history anyway, and 3) the revised content represents sufficient compromise that it is much easier to simply consider it as if it were a new request... to review four sentences.

Since it is the same as withdrawing my request and just submitting a new one with the four sentences, I'd suggest it be handled as if that happened. Because I'm not really going to be jumping through any more hoops. This is simple undergraduate material at or below the level of the rest of the content in the Quicksort article-- not something "scientists" might dispute, as you asserted during our discussion on your talk page and not undue emphasis on some flat-earth-like fringe viewpoint as @MrOllie: seems to believe. It's important for a content editor to have command of the content in order to appropriately apply policies to the content rather than just partial pattern matching on policies out of the context of the content. Frankly, this edit request isn't even necessary anymore. Even the incorrectly labelled "problematic" source is not problematic. Wikipedia policy supports the addition without an edit request of neutrally worded content with a single self-cite from a reliable primary source if the content added to the article performs no analysis or synthesis and just states facts reported in the reliable primary source. Despite your insistence, it does not add original research to a wikipedia article to add a fact to the article that was original research in the primary source. The source and the article are two different things. I've already pointed this out, including occurrences in the Quicksort page itself, but ultimately I grew tired of explaining the policy language, so I simply withdrew the second request containing that so-called problematic reference. You know, this page asks those who can improve the content to do so, but it's too difficult to do so in the face of having more important things to do than continue arguing about this level of content, so the astringency of this process needs to be substantially reduced. Please process my request as it is now (four sentences) or simply indicate that you refuse. JohnBoyerPhd (talk) 04:19, 7 January 2020 (UTC)

It's not the same as submitting a new request, because you've left behind a bunch of discussion that appears to be about your new request, but is really about an old request. It should be obvious by now what problems this leads to. Please just start a new section with your new request. Also, I don't believe this is 'some flat-earth-like fringe viewpoint', I think it is probably correct, but also something that hasn't been impactful enough on the field that it should be discussed in the article. - MrOllie (talk) 12:11, 7 January 2020 (UTC)

You can see from this diff that the only items I changed were in how your request was presented. I didn't change any of the content:

Reformatted request
Before: Edit request {{request edit}} Proposal text A Reasons Signature {{reflist}} Edit request {{request edit}} Proposal text B Reasons Signature {{reflist}} After: Edit request {{request edit}} Proposal text A Reasons Proposal text B Reasons Signature {{reflist}}

The changes to the content were of your own making, they were not mine, and I respectfully ask that you retract your accusation that I altered the substance of your request. In contrast to the formatting changes I made, your changes were far more extensive, they were not redacted, and they made the process of understanding what you wanted here much more difficult.

@Spintendo: Thanks for clearly showing that the two requests became one, which was not my intent. That is the damage I was talking about because you complained repeatedly about a source in proposal 2 that you merged into the request for proposal 1 but which didn't have to do with proposal 1. In order to try to unblock your rejection of the edit request I removed the proposal 2 content that you merged into the edit request. Really need to stop arguing about this, so I'll do as you and MrOllie suggest and do it as a separate request. Still going to need you to revise and update your understanding of the Wikipedia policy on ability to use a primary source to support a content addition, as is done throughout wikipedia, including in the page we are talking about. JohnBoyerPhd (talk) 08:52, 9 January 2020 (UTC)

Here in Wikipedia the WP:BURDEN is on the person wishing to add content to an article to persuade others, first by providing the necessary sources, and then by providing a coherent rationale. If you find others unwilling to join you after making that argument then it's time to reexamine your reasoning. I agree with Ollie that you should start all over from square one with a new approach to your request. Regards,  Spintendo  04:55, 8 January 2020 (UTC)

Hi @MrOllie:, OK, sure, let’s try it as a new request to review the four sentences. If you do consider the new request, I’d ask that you use the Wikipedia policy on weighing impact based on the content being supported by a reliable source, rather than using your own evaluative policy. The problem is that the stating that the material is “probably correct” (rather than knowing that it is) demonstrates movement toward the Comprehension level of Bloom’s taxonomy, which is 4 levels below the evaluative level required to make that call on the impact. Therefore, please instead decide on the sufficiency of impact based on the facts that 1) it is only a few sentences added as a variant, 2) that it is supported by a citation of a publication in a reliable source (DDJ, software developer journal for 38 years with 160K circulation), and 3) that the explanation provided with the edit request includes that this variant appears in programmer-focused knowledge sharing platforms. If I were anyone but the author of #2, I would expect to add this material without it being reverted by anyone. Since my adding the content while also being the author of #2 is supported by Wikipedia policy, there should be no obstacle to what would otherwise be permissible content. Also, I don’t really understand why a simple web search wasn’t used to assuage your concerns. While getting no results doesn’t prove a negative, a plethora of results can provide the extra support you desire. In this case, rather than rejecting so quickly, one could just search for something reasonable like “how to do a linked list quicksort in java”. Many knowledge sharing platforms for programmers come up in the results, including stack overflow, geeks for geeks, tutorial points dev, code speedy, and compute patterns. Because I really don’t want to argue this anymore, I’ll put links to half a dozen or so of these into the explanation section of the new request (despite not being required by Wikipedia sourcing policies). JohnBoyerPhd (talk) 08:52, 9 January 2020 (UTC)

Hoare partition scheme is incorrect

The while tests like (while A[i] < pivot) should be (while A[i] <= pivot).

• It will never return with an array like: [1,3,2,4,5]
• It will access invalid elements with an array like: [1,2,3,4,5]

— Preceding unsigned comment added by 179.186.127.46 (talk) 02:37, 10 February 2020 (UTC)

I'm afraid I can't see it. Can you, please, describe – step by step – the partitioning routine execution leading to accessing invalid element? --CiaPan (talk) 07:25, 10 February 2020 (UTC)

The usage of < or >= actually depends on how the do/while is written, so double checking it's actually correct, but the tests on Cormen's book code are exit expressions (>=), and in the Wikipedia version they are continue expressions (<).