Quick Sort

Quick Sort is a sorting algorithm invented by CarHoare in 1960 and published in 1961; it's really simple, and probably it's the most efficient sorting algorithm. Not a StableSort.

Quicksort works by "partitioning" the array to be sorted, then recursively sorting each partition. Here is the pseudocode.

 procedure QuickSort (array A, int L, int N)
if L < N
M := Partition (A, L, N)
QuickSort (A, L, M - 1)
QuickSort (A, M + 1, N)
endif
 endprocedure

 Int function Partition (array A, int L, int N)
select M, where L <= M <= N
reorder A(L) ... A(N) so that I < M implies A(I) <= A(M), and I > M implies A(I) >= A(M) 
return M
 endfunction

Note that how M is selected is omitted as an implementation detail! To improve efficiency, use a more efficient procedure when N - L is small.

Here you'll find some quicksort code in C and C++: http://theory.stanford.edu/~amitp/rants/c++-vs-c/.

Also see QuickSortInHaskell,QuickSortInPython, QuickSortInRuby for sample implementations of the algorithm.

See SortingAlgorithms

---

Moved here from SortingAlgorithms (RefactorMe):

QuickSort: pick an element at random (or in some other more or less sophisticated way), rearrange your array so that the smaller elements all come at the start, all the equal elements come in the middle, and the larger elements all come at the end (surprisingly difficult to get this both efficient and right) and then recurse on the smaller and larger elements. Expected time-complexity is O(n log n) with little overhead, but if you choose bad pivots either by luck or design then you can get n^2 time. If you always recurse on the smaller sub-array and iterate (i.e., eliminate a tail call) for the larger one, then you only need O(log n) space however bad the pivots are. It's also worth stopping early and using one of the simple-minded sorts when your pieces are small (about 10 or 16 elements). Alternatively, stop early and do a final pass of InsertionSort at the end; this imposes less overhead in cycles than doing lots of separate little insertion sorts, but may interact less well with cache (for moderate datasets) or VM (for immoderate ones). Considerable care required to ensure it's stable.

I don't see how switching from QuickSort to InsertionSort would ever be faster than switching from QuickSort to SelectionSort at the same point. Am I missing something ? -- DavidCary -- AnswerMe Simple answer: insertion sort sorts sorted data in linear time (best case), selection sort comparisons are quadratic in all cases. -- shellreef

SampleSort?: a generalization of QuickSort. Choose a substantial sample from the dataset (the original paper suggests about n/10 items for n up to 50000; probably the sample size should in fact grow more slowly than O(n)). Sort it into order. Partition the dataset into blocks "between" the elements of the sample, and recurse. The sample can be chosen at random (giving expected time O(n log n) and some very low-probability O(n^2) cases) or deterministically (so that some datasets will reliably cause O(n^2) time). As with quicksort (but even more so), you want to stop "early" and switch to a simpler, lower-overhead algorithm once the pieces are small. QuickSort is SampleSort? limited to 1 sample.

---

Essentially everyone is astonished to learn the moderately recent results of RobertSedgewick? JonBentley (two incredibly bright and famous CS guys, not random people): "QUICKSORT IS OPTIMAL" (given their new, very simple and extremely elegant improvement - in a certain sense, naturally). See e.g. http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf (relates to a "recent talk" of January 2002).

(Better references should be inserted here once Citeseer comes back to life again.)

This is really, really brilliant work. Astonishing, even. And yet simple. Elegant. To find such a thing in such a basic area of algorithms when no one else had after decades almost speaks for itself. Words fail me.

It's easy to implement, too (I've done so).

Everyone should know who JonBentley is; RobertSedgewick? was a grad student of DonKnuth's, did his PhD thesis on QuickSort, wrote a highly readable algorithms textbook, and I should probably know more than that about him. Smart guy. -- DougMerritt

---

CategoryAlgorithm