in Algorithms retagged by
2,747 views
18 votes
Assume that the last element of the set is used as partition element in Quicksort. If $n$ distinct elements from the set $\left[1\dots n\right]$ are to be sorted, give an input for which Quicksort takes maximum time.
in Algorithms retagged by
2.7k views

Subscribe to GO Classes for GATE CSE 2022

2 Answers

38 votes
 
Best answer

The algorithm will take maximum time when:

  1. The array is already sorted in same order.(Here,ascending order)
  2. The array is already sorted in reverse order.
  3. All elements are same in the array(Here,we have n distinct elements).So, we can say the above points (1) and (2) as answers.
edited by

5 Comments

@Arjun Sir what is the meaning of 1) The array is already sorted in same order.

is it mean elements are in ascending order?
0
@srestha It means if our goal is to sort in asc order.

and array is already in asc order.
3
3rd point in the answer is not a valid case as question says input is distinct elements
1
@rahul sharma
He has said a generic statement, which is not specific to this question.
2
quick sort:

1==>ascending order:o(n^2)

2==>descending order:o(n^2)

3==>quick sort is a unstable algo,so if all elements are same then also it takes o(n^2) time complexity(3rd point is not applicable in this problem as in problem given all the elements are distinct )
2
0 votes
If the elements in the array are sorted(ascending/descending), quick sort takes O(n^2). and as the elements are distinct as mentioned in question, third case being if the elements are same doesn’t apply here. The above mentioned are worst cases for quick sort.

Related questions