QuickSort
Quick Sort is a Divide and Conquer algorithm. It picks an
element as pivot and partitions the given array around the
picked pivot. There are many different versions of quick Sort
that pick pivot in different ways.
[Link] pick first element as pivot.
[Link] pick last element as pivot.
[Link] a random element as pivot.
[Link] median as pivot.
The key process in quick Sort is partition(). Target of partitions
is, given an array and an element x of array as pivot, put x at
its correct position in sorted array and put all smaller elements
(smaller than x) before x, and put all greater elements (greater
than x) after x. All this should be done in linear time.
Application of QuickSort
=>Quick sort generally run fast.
=>No additional memory.
Algorithm
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Code
Quicksort(A,p,r) {
if (p < r) {
q <- Partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x <- A[p]
i <- p-1
j <- r+1
while (True)
{ repeat
j <- j-1
until (A[j] <= x)
repeat
i <- i+1
until (A[i] >= x)
if (i<-=""> A[j]
Else
return(j)
}
}
Complexity
Best Case Worst Case
Ω(n log(n)) O(n^2)
=>If the array is unsorted ,
complexity of quicksort will be Best
Case.
=>If the array is sorted , complexity of
quichsort will be Worst Case