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

Wrongly placed reference? & text attribution

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

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)

Please don't. Applications sections generally turn into spam magnets - long lists of unhelpful trivia. MrOllie (talk) 23:41, 12 March 2023 (UTC)

Got you. Wpengda (talk) 02:09, 15 March 2023 (UTC)

More recent research on Quick Sort

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)

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)

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)

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)

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

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)