Quicksort

Quicksort is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items. It is also known as partition-exchange sort. In the worst case, it makes O(n2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms. Additionally, quicksort's sequential and localized memory references work well with a cache. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.

Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Read more about QuicksortHistory, Algorithm, Selection-based Pivoting, Variants, Comparison With Other Sorting Algorithms

Other articles related to "quicksort":

Probabilistic Complexity Theory - Applications - Quicksort
... Quicksort is a familiar, commonly used algorithm in which randomness can be useful ... Any deterministic version of this algorithm requires O(n2) time to sort n numbers for some well-defined class of degenerate inputs (such as an already sorted array), with the specific class of inputs that generate this behavior defined by the protocol for pivot selection ...
Quicksort - Comparison With Other Sorting Algorithms
... Quicksort is a space-optimized version of the binary tree sort ... items sequentially into an explicit tree, quicksort organizes them concurrently into a tree that is implied by the recursive calls ... This property is hard to maintain for in situ (or in place) quicksort (that uses only constant additional space for pointers and buffers, and logN additional space for the management of explicit or ...
Introsort
... It begins with quicksort and switches to Heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted ... a worst-case O(n log n) runtime and practical performance comparable to quicksort on typical data sets ... In quicksort, one of the critical operations is choosing the pivot the element around which the list is partitioned ...
Quark Framework - CAL - 1. Quicksort
... /** * Here is a simple implementation of the quicksort algorithm for lists in * CAL ... * * The type of quicksort is constrained by the {@link Ord@} type class ... This * means that quicksort can sort list of any orderable type ...
MVEL - Quicksort Example
... Here is an example of the Quicksort algorithm implemented in MVEL 2.0, demonstrating the scripting capabilities of the language ... import java.util.* // the main quicksort algorithm def quicksort(list) { if (list.size pivot))) } } // define method to concatenate lists ... concatList.addAll(list2) concatList } // create a list to sort list = // sort it! quicksort(list) ...