764 views

2 Answers

Best answer
5 votes
5 votes

For already sorted, quick sort performance degrades to O(N2) . Here, all the elements are equal, means array is already sorted . So, it should degrade to O(N2) . 

But, quick sort is more improved now and it can be implemented by 2 partition methods - Hoare's and Lomuto's partition method .

A rigourous and detailed implementation is shown here =>

http://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto

There is no such situation in which Lomuto can perform better than Hoare. 

Hoare always gives optimal partitioning and gives O(N log N) whereas  Lomuto observes the worst case partitioning, making the overall performance still degrading to O(N2) .

Option B is correct .

selected by
Answer:

Related questions

2 votes
2 votes
4 answers
1
Bikram asked Oct 4, 2016
595 views
Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates
3 votes
3 votes
1 answer
3
Bikram asked Oct 4, 2016
829 views
You are given a 1 billion numbers. The time require in seconds to sort them provided sorting thousand numbers takes 100 microseconds will be _______10,00051230065536