in Algorithms
394 views
2 votes
2 votes

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

  1. $\Theta(\lg N)$
  2. $\Theta(N\lg N)$
  3. $\Theta(\lg \lg N)$
  4. $\Theta(N/\lg N)$
in Algorithms
by
394 views

1 Answer

4 votes
4 votes
Best answer

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
by

4 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
0
0

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(n2).

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

2
2

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)$

 

1
1