The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
729 views
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.
asked in Algorithms by Veteran (59.6k points)
retagged by | 729 views

1 Answer

+28 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.
answered by Boss (34.1k points)
edited by
0
@Arjun Sir what is the meaning of 1) The array is already sorted in same order.

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

and array is already in asc order.
+1
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.
+1
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 )

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,699 questions
48,662 answers
156,602 comments
63,970 users