Quicksort




A sorting algorithm with O(n log n) average time complexity.

One element, x of the list to be sorted is chosen and the other elements are split into those elements less than x and those greater than or equal to x.

These two lists are then sorted recursively using the same algorithm until there is only one element in each list, at which point the sublists are recursively recombined in order yielding the sorted list.

This can be written in Haskell:

qsort













:: Ord a => [a] -> [a] qsort []











= [] qsort (x:xs)







= qsort [ u | u<-xs, u<x ] ++ [ x ] ++ qsort [ u | u<-xs, u>=x ]

[Mark Jones, Gofer prelude.]





< Previous Terms Terms Containing Quicksort Next Terms >
Queued Sequential Access Method
QUICK
quick-and-dirty
QuickDraw
Quicksilver
sort
Quicktime
quiesce
quiesce time
QUIKSCRIPT
QUIKTRAN