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

1 Answer

+25 votes
Best answer

The algorithm will take maximum time when:

  1. The array is already sorted in same order.
  2. The array is already sorted in reverse order.
  3. All elements are same in the array.
answered by Boss (34.1k points)
edited by
@Arjun Sir what is the meaning of 1) The array is already sorted in same order.

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

and array is already in asc order.
3rd point in the answer is not a valid case as question says input is distinct elements
@rahul sharma
He has said a generic statement, which is not specific to this question.
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 )

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

37,072 questions
44,643 answers
43,699 users