The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
517 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 (68.9k points)
retagged by | 517 views

1 Answer

+23 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 Veteran (35.9k 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 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

32,693 questions
39,293 answers
110,109 comments
36,701 users