Jump to content

Talk:Quicksort

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Timkaler (talk | contribs) at 23:56, 10 October 2014 (→‎Parallelization description needs work: mention right source to use to cite parallel merge algorithm.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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‎

I put a {{disputed section}} on the section Simple algorithm, because I agree with you. I've seen publications from the FP (Haskell) community where it's claimed that this is quicksort:
-- Off the top of my head
sort []  = []
sort [x] = [x]
sort (p:xs) =  sort left ++ [p] ++ sort right
  where (left:right) = partition p
        partition p xs = ([x | x <- xs, x < p], [x | x <- xs, x >= p])
... and this is what this section is describing, except in "simple", quasi-imperative pseudocode. As for WP:V, it is possible to find sources that describe this kind of "quicksort". However, it is not how CLSR define quicksort:
Quicksort(A, p, r)
 if p < r
  q = Partition(A, p, r)
  Quicksort(A, p, q - 1)
  Quicksort(A, q + 1, r)
To me, this is classic quicksort. It's an imperative, in-place algorithm, with no append or concatenate operations. Just move the pivot around, and then recursively sort the subarrays as completely independent subproblems, with no postprocessing. QVVERTYVS (hm?) 21:21, 28 May 2014 (UTC)[reply]

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.

algorithm is incorrect

the shown partition function has a different signature then the one used in quicksort:

partition(array, left, right, pivotIndex) // 4 arguments — Preceding unsigned comment added by 62.178.185.230 (talk) 09:25, 5 June 2014 (UTC)[reply]

Fixed that. QVVERTYVS (hm?) 11:17, 5 June 2014 (UTC)[reply]


Parallelization description needs work

I'm not happy with the discussion on parallelization.

Consider this text:

If the split is blind, ignoring the values, the merge naïvely costs O(n). If the split partitions based on a succession of pivots, it is tricky to parallelize and naïvely costs O(n). Given O(log n) or more processors, only O(n) time is required overall, whereas an approach with linear speedup would achieve O(log n) time for overall. One advantage of this simple parallel quicksort over other parallel sort algorithms is that no synchronization is required, but the disadvantage is that sorting is still O(n) and only a sublinear speedup of O(log n) is achieved.

Now, as given, the text suggests that writing a scalable quicksort is hard and that we should prefer this sub-optimal parallelization that can achieve at most logarithmic speedup. It isn't that hard to explain (or write in code for that matter) a scalable quicksort, however.

As a quick example, merging two sorted arrays of total size n can be done in O(log^2 n) span and O(n) work --- or put another way: O(n/P + log^2 n) time. See slide 51 of http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-14-analysis-of-multithreaded-algorithms/MIT6_172F10_lec14.pdf for more details on the parallel merge. This would allow you to merge P sorted arrays in O(log(P)log^2(n/p)) span and O(n log P) work by performing merges in a balanced binary tree with the P sorted arrays at the leaves.

I'm not sure the solution to this problem is to add a description or reference to a parallel merge routine to the current text. I don't see why we don't just describe the recursive parallelization of quicksort that performs parallel partitions using extra space (standard parallel packing algorithm). That would give you an O(n log n) work algorithm with O(log^2 n) span. This alternative algorithm is also arguably a lot simpler than one that explicitly partitions among processors.

Any thoughts?

-Tim Kaler 23:07, 19 August 2014 (UTC) — Preceding unsigned comment added by Timkaler (talkcontribs)

I made a revision to the parallelization section a few moments ago. I think that it still needs some work, but it seems a lot better (to me at least) than what was there before. I think it would be good to add a description of how to implement quicksort via explicitly partitioning the array --- as this may be more readily understandable to those unfamiliar with parallel algorithms. We should probably tell them, in such an explanation, that the sorted partitions can be merged in parallel and give them a citation to find that algorithm :) (the slides I linked to earlier have the algorithm, but the right citation is the textbook CLRS Introduction To Algorithms) -Tim Kaler 23:38, 10 October 2014 (UTC) — Preceding unsigned comment added by Timkaler (talkcontribs)

Article needs restructuring

We currently have the following sections after the History:

  • Algorithm. Includes a subsection Implementation issues that describes small practical tricks, but also an alternative pivot algorithm.
  • Formal analysis. Contains what it promises.
  • Relation to other algorithms. This contains a list of Variants that are not really different algorithms, but quicksort variants (formally these are different algorithms, but the algorithms literature does not award all of them a custom name).

I suggest we restructure to get:

  • Basic algorithm (or Overview?)
  • Variants and improvements
  • Formal analysis (put here because we need to describe the main algorithms first)
  • Relation to other algorithms (selection goes here, but what about Generalization?)

Comments? QVVERTYVS (hm?) 09:55, 5 September 2014 (UTC)[reply]