quicksort : Java Glossary

by Roedy Green ©1996-2009 Canadian Mind Products
index page for letter ⇒ punctuation 0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z (all)

quicksort

C.A.R. Hoare’s recursive sorting technique. It works with a pivot element, moving all keys smaller than the pivot to one side and all the keys bigger to the other. Then it recursively sorts each half. QuickSort can be pathologically slow if the data are already ordered. In Java, QuickSort is slower than either HeapSort or RadixSort. Typical QuickSort implementations are unstable since they scramble keys to avoid pathological pre-orderings. Free Java source code is available from Roedy Green at Canadian Mind Products.

Oddly, the Haskell version of Quicksort is probably the easiest to understand:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

The first line reads: “the result of sorting an empty list ([]) is an empty list”.

The second line reads: “to sort a list whose first element is x and the rest of which is called xs, sort the elements of xs that are less than x, sort the elements of xs that are greater than or equal to x, and concatenate (++) the results with x sandwiched in the middle.”

To learn more about quicksort’s behaviour see Eppstein’s paper. QuickSort source code download..

HeapSort
O(n²)
RadixSort
ShellSort
Sort

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.58]
	You are visitor number 29,452.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/jgloss/quicksort.html	J:\mindprod\jgloss\quicksort.html