5,851 views
0 votes
0 votes

A desirable choice for the partitioning element in quick sort is
(A) First element of the list
(B) Last element of the list
(C) Randomly chosen element of the list
(D) Median of the list

 

1 Answer

5 votes
5 votes

Answer : Median of List

Every time if we take median as the pivot element  using partition algorithm it takes O(n) time .then replace the median with last element(it is a/c to your algorithm means what you have chosen as pivot here I assumed last element as pivot .) it will take O(1) constant time to replace last element with median, and every time it divides the problem into 2 half 

T(n) = O(n) + T(n/2) solve using master theorem and get complexity as O(nlogn)

In the above  equation O(n) is in case of Partition algorithm.

Related questions

4 votes
4 votes
2 answers
1
worst_engineer asked Oct 7, 2015
5,921 views
In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity?it is $\Theta (...
3 votes
3 votes
2 answers
3
8 votes
8 votes
2 answers
4