Quick sort algorithm:
The array A[p….r] is divided into two subarrays A[p…….(q-1)] and A[(q+1)…….r] where q is the partitioning element.
Quick_sort(A,p,r) { if (p<r) { q=PARTITION(A,p,r) Quick_sort(A,p,q-1) Quick_sort(A,q+1,r) } } PARTITION(A,p,r) { x=A[r] i=p-1 for j=p to r-1 { if A[j]<=x { i=i+1 Exchange A[i] with A[j] } } Exchange A[i+1] with A[r] Return i+1 }
Time complexity of quick sort algorithm:
The complexity of quicksort depends on the partitioning is balanced or not.
Best case: It occurs when the partitioning is fully balanced i.e it produces two sublists of equal or almost equal length.
T(n)=2T(n/2)+(c*n)
Where (c*n)= constant time required outside the recursive call
T(n)=Θ(nlogn)
Worst case: The worst case occurs when the partitioning routine produces one subproblem with n-1 elements and one with 0 elements.
T(n)=T(n-1)+T(1)+(c*n)
=O(n2)
Where (c*n) =constant time required outside the recursive call
Partition operation on Arr=[2,8,7,1,3,5,6,4]
atOptions = {
'key': 'a900f2dbf175e78754c26c6231a4b673',
'format': 'iframe',
'height': 90,
'width': 728,
'params': {}
};