Write quick sort algorithm. Analyze the best case and worst case time complexities of your algorithm. Perform the PARTITION operation once(one time) on the following array as per the requirement of the quicksort algorithm, assuming the last element of the array to be the pivot element. Clearly mention the steps. Arr=[2,8,7,1,3,5,6,4].

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]