GATE Overflow | Algorithms | Test 1 | Question: 23

Question

About how many compares will Quicksort() make when sorting an array of N items that are all equal?

• A. $\Theta(\lg N)$
• B. $\Theta(N\lg N)$
• C. $\Theta(\lg \lg N)$
• D. $\Theta(N/\lg N)$

Answer 1

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

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(N²) .

Option B is correct .

Comments

and if elements are already sorted then also no. of comaprison is upper bounded by O(n^2)..?

O(nlogn) comparison will be required when our input is other than sorted input or identical elements...which cause worst case of quick sort

---

Time complexity is always decided by how partitioning takes place for quick sort.

Even if the input is sorted, if the last element is selected as the partitioning element, stiil it would go O(n²).

If partitioning happens at the middle, then its O(n.logn)

---

Lomuto partition scheme on sorted input	Hoare partition scheme on sorted input
Pivot is first element: $O(n^2)$	Pivot is first element: $O(n^2)$
Pivot is last element: $O(n^2)$	Pivot is last element: $O(n^2)$
Pivot is an intermediate element: $O(n^2)$	Pivot is an intermediate element: $O(nlogn)$

 

Answer 2

Θ(nlogn)