The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
580 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.4k points)
retagged by | 580 views

1 Answer

+24 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.2k 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?
+2
@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.


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

34,780 questions
41,756 answers
118,923 comments
41,399 users