Jump to content

Talk:Quicksort: Difference between revisions

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
m Removed deprecated parameters in {{Talk header}} that are now handled automatically (Task 30)
 
(21 intermediate revisions by 12 users not shown)
Line 1: Line 1:
{{Talk header|archive_age=120|archive_bot=Lowercase sigmabot III}}
{{Talk header}}
{{WikiProject banner shell|class=B|vital=yes|1=
{{WikiProjectBannerShell|
{{WikiProject Computing|class=B|importance=top}}
{{WikiProject Computing|importance=top}}
{{WikiProject Computer science|class=B|importance=top}}
{{WikiProject Computer science|importance=top}}
{{Vital article|class=B|topic=Mathematics|level=5}}
}}
}}
{{archive box| auto=long |
{{archive box| auto=long |
Line 12: Line 11:
|archiveheader = {{Talkarchivenav}}
|archiveheader = {{Talkarchivenav}}
|maxarchivesize = 150K
|maxarchivesize = 150K
|counter = 2
|counter = 3
|minthreadsleft = 5
|minthreadsleft = 5
|algo = old(120d)
|algo = old(120d)
|archive = Talk:Quicksort/Archive %(counter)d
|archive = Talk:Quicksort/Archive %(counter)d
}}
}}
{{Broken anchors|links=

* <nowiki>{{Section link||Analysis of randomized quicksort}}</nowiki> The anchor (,,) is no longer available because it was [[Special:Diff/704104957,|deleted by a user]] before. <!-- {"title":"Analysis of randomized quicksort","appear":{"revid":594480580,"parentid":591700405,"timestamp":"2014-02-08T06:58:42Z","replaced_anchors":{"Analysis of Randomized quicksort":"Analysis of randomized quicksort"},"removed_section_titles":["Analysis of Randomized quicksort"],"added_section_titles":["Analysis of randomized quicksort"]},"disappear":{"revid":704104957,"parentid":703118144,"timestamp":"2016-02-09T15:52:25Z","removed_section_titles":["Average-case analysis using discrete probability","Average-case analysis using recurrences","Analysis of randomized quicksort"],"added_section_titles":["Worst-case analysis","Best-case analysis","Average-case analysis","Using percentiles","Using recurrences","Using a binary search tree"]}} -->
}}
== Blog interview ==
== 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. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small>
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. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small>

== Lomuto partition scheme ==
In Lomuto partition scheme implementation there is a mistake.
In the worst case scenario j grows as i, giving a memory out of bounds error on the last swap.
I correct it, see the history.
<!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Dante DDM|Dante DDM]] ([[User talk:Dante DDM#top|talk]] • [[Special:Contributions/Dante DDM|contribs]]) 23:16, 5 August 2020 (UTC)</small> <!--Autosigned by SineBot-->

: {{re|Dante DDM}} No mistake there. The i variable will not be incremented in the last iteration of the loop, so we have 'i is less or equal hi' after the loop termination. No risk of out-of-bounds swap (unless you make a mistake in translating the algorithm into the code). --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 23:59, 5 August 2020 (UTC)

:: {{reply to|CiaPan}} I've checked out and misunderstood the code. I apologize for bothering. [[User:Dante DDM|Dante DDM]] ([[User talk:Dante DDM|talk]]) 11:49, 8 September 2020 (UTC)

::: {{re|Dante DDM}} That's okay. {{smiley}} We all learn from our mistakes. Don't let it to discourage you – [https://www.google.com/search?q=it%27s+not+the+mistake+that+matters It's not the mistake that matters]. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 12:35, 11 September 2020 (UTC)

I think the Lomuto partition pseudocode is still wrong. If you partition([2,1],0,1) it will set pivot = 1, i = -1, then on the first loop iteration j=0 and it evaluates A[j] <= pivot or A[0] = 2 <= 1, then in the else it will error trying to swap A[-1] and A[0]. If lo > 0 to start then it will change a value outside of the range. <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:75.10.161.2|75.10.161.2]] ([[User talk:75.10.161.2#top|talk]] • [[Special:Contributions/75.10.161.2|contribs]]) </span>
: Nope. There is no 'else' there, so after the {{code|1=A[j] <= pivot}} comparison which results in {{code|false}} there is no 'else' but just another loop iteration. That one ends immediately, because {{code|1=j = hi - 1}} already. So, the control goes to the last three lines, where {{code|i}} gets incremented from –1 to 0, then {{code|A[0]}} gets swapped with {{code|A[1]}} and finally the value 1 is returned. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 11:05, 27 July 2022 (UTC)


== Wrongly placed reference? & text attribution ==
== Wrongly placed reference? & text attribution ==
Line 49: Line 34:
<!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Geke|Geke]] ([[User talk:Geke#top|talk]] • [[Special:Contributions/Geke|contribs]]) 25 August 2020 (UTC)</small>
<!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Geke|Geke]] ([[User talk:Geke#top|talk]] • [[Special:Contributions/Geke|contribs]]) 25 August 2020 (UTC)</small>


== More examples of Quick Sort in practice ==
== The quicksort algorithm is wrong ==

The quicksort algorithm on this page doesn't work. The algorithm given under Hoare partition scheme gives incorrect results for some carefully chosen inputs.

For example, it will incorrectly sort these integers: [10 0 5 2 4 7 1 6 3 8 9] (the result will be [0 3 4 2 5 6 1 7 9 8 10]).

It's hard to point to exactly one thing that's wrong with the algorithm, but the basic issue is that a carefully chosen input can "hide" an incorrectly sorted value in between [lo, p-1] and [p+1, hi]. The partitioning function must detect and correct.

A correct version of this algorithm can be found, e.g., in Sedgewick & Wayne: Algorithms 4th Edition. I can reproduce it here, if copyright permits (does it permit?) <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/212.51.146.228|212.51.146.228]] ([[User talk:212.51.146.228#top|talk]]) 09:34, 2 January 2021 (UTC)</small> <!--Autosigned by SineBot-->

: Not true. I have just implemented the algorithm in C and run it at https://www.onlinegdb.com/online_c_compiler. The result was:
<pre>
Input: 10 0 5 2 4 7 1 6 3 8 9
Result: 0 1 2 3 4 5 6 7 8 9 10
</pre>
: Probably you've made some mistake in translating the algorithm from pseudocode to your favourite programming language.
: Below is my code, feel free to test it at OnlineGDB or elsewhere. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 12:10, 2 January 2021 (UTC)
{{hidden
|Source in C by CiaPan
|<pre>
#include <stdio.h>

int partition(int array[], int lo, int hi)
{
int pivot = array[(hi + lo) / 2];
int i = lo - 1;
int j = hi + 1;
while(1)
{
do
i = i + 1;
while(array[i] < pivot);
do
j = j - 1;
while(array[j] > pivot);
if(i >= j)
return j;
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}

void quicksort(int array[], int lo, int hi)
{
if(lo < hi)
{
int p = partition(array, lo, hi);
quicksort(array, lo, p);
quicksort(array, p + 1, hi);
}
}

void printArray(int array[], int len, const char* title)
{
printf("%s", title);

for(int i = 0; i < len; i++)
printf("%3d", array[i]);

printf("\n");
}

int main()
{
int array[] = {10, 0, 5, 2, 4, 7, 1, 6, 3, 8, 9};
printArray(array, 11, "Input: "); // 11 = length of the array
quicksort(array, 0, 10); // 10 = last index
printArray(array, 11, "Result:");

return 0;
}
</pre>
|headerstyle=background:#ccccff
|style=text-align:center;
}}

: After a closer look at the result presented I think you confused ''sorting'' with ''partitioning''. What you present as a 'result':
:: [0 3 4 2 5 6 1 7 9 8 10]
: is a result of partitioning – the central element '''7''' has been chosen from the input array, then the array has been reordered into a lower partition with items 0 through 6 and the higher partition with values 8 through 10. Partitions are separated by the pivot value 7:
:: [0 3 4 2 5 6 1 {{bgcolor|lightgreen|&nbsp;7&nbsp;}} 9 8 10]
: That, however, does not complete ''sorting''! Now both partitions: [0 3 4 2 5 6 1] and [9 8 10] need to be independently sorted by recursive calls, so that the whole array gets ordered. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 12:47, 2 January 2021 (UTC)

== Shouldn't we change the big-O notation to Theta? ==


I am thinking about adding the section on Quick Sort's uses in various fields. While the Quick Sort article provides a comprehensive explanation of the algorithm, it could benefit from more real-world examples of how Quick Sort is used in different domains. For instance, the article could discuss how Quick Sort is used in data processing, image processing , or network analysis, and how it compares to other sorting algorithms in these contexts. This could help readers gain a better understanding of the practical applications of Quick Sort and strengthen it and weaknesses in different settings. [[User:Wpengda|Wpengda]] ([[User talk:Wpengda|talk]]) 23:34, 12 March 2023 (UTC)
In the right box we say that best, worst and average performances are a big-O of something, but can be proven that they're actually Thetas of "something".
For example, the average case performance is a <math>O(n\log_2 n)</math> but actually it is a <math>\Theta(n\log_2 n)</math> which is a better analysis.<!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/62.98.214.57|62.98.214.57]] ([[User talk:62.98.214.57#top|talk]]) </small>
: The article [[Big O notation]] has some context on that, specifically [[Big O notation#Use in computer science|#Use in computer science]]: ''"So while all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above)"''. Does this help? -- [[User:Evilninja|Evilninja]] ([[User talk:Evilninja|talk]]) 10:39, 11 August 2021 (UTC)
:: {{ping|Evilninja}} I've replaced an URL with a wikilink. --[[User:CiaPan|CiaPan]] ([[User talk:CiaPan|talk]]) 20:49, 11 August 2021 (UTC)


:Please don't. Applications sections generally turn into spam magnets - long lists of unhelpful trivia. [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 23:41, 12 March 2023 (UTC)
== Hoare partition scheme does not preserve randomness ==
::Got you. [[User:Wpengda|Wpengda]] ([[User talk:Wpengda|talk]]) 02:09, 15 March 2023 (UTC)


== More recent research on Quick Sort ==
The Hoare partition scheme given here is elegant and similar to the one in Hoare's original paper. This algorithm does ''not'' swap the pivot element into the "middle" and fix it into its final place. As a result, when sorting a uniformly random permutation, it does not maintain the randomness in the resulting subarrays. As indicated on p. 35 of [https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf Sedgewick's PhD thesis] "This bias not only makes analysis of the method virtually impossible, it also slows down the sorting process considerably." For example, the average-case analysis given in this article does not apply to this version of quicksort.


Hello, I am thinking about adding the section on Quick Sort's recent research. While the Quick Sort article gives people the view of the quick sort algorithm, we can update some new findings to it to make it stay up to the new research. For example, when changing the pick of pivots will improve the worst case of time complexity from O(N^2) to O(NlogN). [[User:MiaoQiQi|MiaoQiQi]] ([[User talk:MiaoQiQi|talk]]) 20:55, 14 March 2023 (UTC)
If the goal is to show the preferred way to implement a 2-way partition (e.g., fewer exchanges than Lomuto, doesn't go quadratic with all equal keys, provably ~ 2n ln n compares for random permutations), replace Hoare partition scheme with the Sedgewick-Hoare partition scheme, which does swap the pivot element into its final place (and preserve randomness). Alternatively, add a warning in the analysis section that it is not applicable to quicksort with the Hoare partition scheme.


:Given the formulaic nature of these talk page sections, I assume that you folks are participating in some sort of class. Please direct your instructor to [[Wikipedia:Education program]] for best practices for this kind of activity. [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 20:59, 14 March 2023 (UTC)
[[User:Algorithms4|Algorithms4]] ([[User talk:Algorithms4|talk]]) 18:20, 7 March 2022 (UTC)
:The cited article '''does not provide any proof about the worst case complexity''' of the proposed algorithm. By looking at the algorithm it is hard to believe that the worst case is n lg n. The algorithm simply avoids taking the lowest or highest value as pivot. [[User:Gilles Falquet|Gilles Falquet]] ([[User talk:Gilles Falquet|talk]]) 23:38, 20 March 2023 (UTC)
::I agree, this is just a conference paper and covering it here is likely [[WP:UNDUE]]. I'll remove it. [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 16:44, 23 March 2023 (UTC)


== Is there a mismatch between the animated demo and the pseudocode of Hoare's partition scheme? ==
== "Quicksort" vs "quicksort" ==


The animated demonstration of Quicksort using Hoare's partition scheme seems to have one element sorted to its correct position after each partition routine and then omit it in the following recursions. Yet the pseudocode below claims that after one partition the pivot is then included in the next recursive call, which means no element should be omitted. Also the content below the pseudocode writes <i>"In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion."</i> My question is that is there a mismatch between the code and the animated demonstration (i.e. the demo is another scheme of quicksort)? (There is also a great chance that I have overlooked some details and misunderstood the material.) [[User:Student118|Student118]] ([[User talk:Student118|talk]]) 06:27, 11 September 2023 (UTC)
The article seems to be inconsistent about whether its subject should be capitalised in general usage or not. E.g. currently in the introduction we see the following two usages (my italics): "Efficient implementations of ''Quicksort'' are not a stable sort […]", and "Mathematical analysis of ''quicksort'' shows that […]". It would be preferable to consistently use one style in the article.

Latest revision as of 10:27, 8 October 2024

Blog interview

[edit]

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?)

Wrongly placed reference? & text attribution

[edit]

1. Reference 16 (at time of writing) is about the Yaroslavskiy algorithm, but it’s placed in the section about the Lomuto implementation. Shouldn’t it be removed there and inserted elsewhere, maybe in the History section?

The reference text (for reference :) Wild, Sebastian (2012). "Java 7's Dual Pivot Quicksort". Technische Universität Kaiserslautern.

2. The algorithm given in the Algorithm section seems to be taken almost verbatim from Yaroslavskiy (Reference 10). Would it be good to attribute it to that paper?

The reference text again: Yaroslavskiy, Vladimir (2009). "Dual-Pivot Quicksort" (PDF). Archived from the original (PDF) on 2 October 2015.

— Preceding unsigned comment added by Geke (talk • contribs) 25 August 2020 (UTC)

More examples of Quick Sort in practice

[edit]

I am thinking about adding the section on Quick Sort's uses in various fields. While the Quick Sort article provides a comprehensive explanation of the algorithm, it could benefit from more real-world examples of how Quick Sort is used in different domains. For instance, the article could discuss how Quick Sort is used in data processing, image processing , or network analysis, and how it compares to other sorting algorithms in these contexts. This could help readers gain a better understanding of the practical applications of Quick Sort and strengthen it and weaknesses in different settings. Wpengda (talk) 23:34, 12 March 2023 (UTC)[reply]

Please don't. Applications sections generally turn into spam magnets - long lists of unhelpful trivia. MrOllie (talk) 23:41, 12 March 2023 (UTC)[reply]
Got you. Wpengda (talk) 02:09, 15 March 2023 (UTC)[reply]

More recent research on Quick Sort

[edit]

Hello, I am thinking about adding the section on Quick Sort's recent research. While the Quick Sort article gives people the view of the quick sort algorithm, we can update some new findings to it to make it stay up to the new research. For example, when changing the pick of pivots will improve the worst case of time complexity from O(N^2) to O(NlogN). MiaoQiQi (talk) 20:55, 14 March 2023 (UTC)[reply]

Given the formulaic nature of these talk page sections, I assume that you folks are participating in some sort of class. Please direct your instructor to Wikipedia:Education program for best practices for this kind of activity. MrOllie (talk) 20:59, 14 March 2023 (UTC)[reply]
The cited article does not provide any proof about the worst case complexity of the proposed algorithm. By looking at the algorithm it is hard to believe that the worst case is n lg n. The algorithm simply avoids taking the lowest or highest value as pivot. Gilles Falquet (talk) 23:38, 20 March 2023 (UTC)[reply]
I agree, this is just a conference paper and covering it here is likely WP:UNDUE. I'll remove it. MrOllie (talk) 16:44, 23 March 2023 (UTC)[reply]

Is there a mismatch between the animated demo and the pseudocode of Hoare's partition scheme?

[edit]

The animated demonstration of Quicksort using Hoare's partition scheme seems to have one element sorted to its correct position after each partition routine and then omit it in the following recursions. Yet the pseudocode below claims that after one partition the pivot is then included in the next recursive call, which means no element should be omitted. Also the content below the pseudocode writes "In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step, and may not be sorted until the base case of a partition with a single element is reached via recursion." My question is that is there a mismatch between the code and the animated demonstration (i.e. the demo is another scheme of quicksort)? (There is also a great chance that I have overlooked some details and misunderstood the material.) Student118 (talk) 06:27, 11 September 2023 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Talk:Quicksort&oldid=1250076568"