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(n²)

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': {} };