IT1230809

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, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return 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