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(n2)
Where (c*n) =constant time required outside the recursive call
Partition operation on Arr=[2,8,7,1,3,5,6,4]
What do you mean by dynamic programming? Write the algorithm of chain matrix multiplication.
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Find the recurrence relation of binary search and derive the time complexity of binary search.
What is tree traversal?
What is a minimum spanning tree ? Describe Huffman’s Algorithm.
