Quicksort
- is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time andin-place We then recursively sort the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice.
Run-time Complexity Analysis:
this is performed through finding its pivot and sort it.typically unstable and somewhat complex but among the fastest sorting algorithms.
Codes:
function quicksort(array)var list less, greaterif length(array) ≤ 1return arrayselect and remove a pivot value pivot from arrayfor each x in arrayif x ≤ pivot then append x to lesselse append x to greaterreturn concatenate(quicksort(less), pivot, quicksort(greater))
Application:
finding the pivot of a given example and then sort it.
Reference:
http://en.wikipedia.org/wiki/Quicksort