Important word '**central element'. **It may not be median. Hehe

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+27 votes

You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

- $O(n^2)$
- $O(n \log n)$
- $\Theta(n\log n)$
- $O(n^3)$

+2

Yes right**. **For a **sorted** array only median lies in the central position. For unsorted array median may not be there in the middle.

0

What is the difference between the above question and this https://gateoverflow.in/25209/tifr2012-b-14 ?

+53 votes

Best answer

(**A**) $O(n^2)$ is the answer. When we choose the first element as the pivot, the worst case of quick sort comes if the input is sorted- either in ascending or descending order. Now, when we choose the middle element as pivot, sorted input no longer gives worst case behavior. But, there will be some permutation of the input numbers which will be giving the same worst case behavior. For example,

$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7$

This array gives worst case behavior for quick sort when the first element is pivot.

$6 \ 4 \ 2 \ 1 \ 3 \ 5 \ 7$

This array gives the worst case behavior of $O(n^2) $ if we take middle element as the pivot- each split will be $1$ element on one side and $n-1$ elements on other side. Similarly, for any input, we can have a permutation where the behavior is like this. So, whichever element we take as pivot it gives worst case complexity of $O(n^2)$ as long as pivot is from a fixed position (not random position as in randomized quick sort).

0

**sir can u please tell me how this order works ....(i.e) 6 4 2 1 3 5 7... ???....**

**if the input is...... 5 5 5 5 5 5 5 ....then i think it will be O(n^2)....**

0

Sir I didn't understand the explanation What I have got is that If array is sorted and if we choose first or last element as pivot then complexity will be O(n^2) and if we chose central element as pivot then we'll get complexity as O(n log n) .But if array is unsorted and then we pick central element as pivot then complexity will be O(n^2) How?????

please explain me this??

Also what is the difference between median pivot or central element as pivot?

please explain me this??

Also what is the difference between median pivot or central element as pivot?

+10

What I have got is that If array is sorted and if we choose first or last element as pivot then complexity will be O(n^2)

Yes.

if we chose central element as pivot then we'll get complexity as O(n log n)

By central element if you mean in the sorted array then this is correct. In a random array even if we select the central element as pivot, it can cause worst case of $O(n^2).$

0

Sir, did not understand 2nd part- here how we are always choosing middle element as pivote. ??

If we have to sort this list using quick, then we need to proceed as -

6 4 2 1 3 5 7 // here pivote index = 5 (starting with 1)

5 4 2 1 3 6 7 // pivote index = 4

3 4 2 1 5 6 7

3 1 2 4 5 6 7 // pivote = 3

2 1 3 4 5 6 7 // pivote = 2

1 2 3 4 5 6 7

here in all case - quick sort divides the list in two parts where left side list has n-1 elements and right side part has 1 element, so time complexity is O(n^{2}) .

Is this correct sir ??

But I did not understand here that how we will take middle element as pivote..

please clear my doubt sir.

0

@Anirudh , thanks , but now lets talk about this question. Can you please explain the example given by arjun sir in the 2nd part ??

I mean A = 6 4 2 1 3 5 7.

How do we always get middle element as pivote here while doing quick sort ??

I mean A = 6 4 2 1 3 5 7.

How do we always get middle element as pivote here while doing quick sort ??

+3

it is not working of given example , since mid is 1 so partition will be ,

1 (426357)

here midd is 6

1 (2435) , 6 (7)

like this

but u take example 66666666

or think like this every think u pic midd element which partition array into n-1 left or right element .

1 (426357)

here midd is 6

1 (2435) , 6 (7)

like this

but u take example 66666666

or think like this every think u pic midd element which partition array into n-1 left or right element .

+2

Pivot means a element in which all the left portion of this pivot will be less than this and all the right portion of this pivot will be greater than this so here if the array is not in increasing or decrasing order if we take median element as a pivot it can happen that it is the smallest element of the whole array that we are taking as pivot so therefore taking this as the middle element all the rest elements are in the RHS portion and no elemens in LHS so partion in 1 and (n-1) portins so complexity O(n^2).

0

then what will be the best case ?as we know choosing the central element gives best case of the quick sort .will it depends upon the permutation of the element ??

0

So, whichever element we take as pivot it gives worst case complexity of O(n2) as long as pivot is from a fixed position

https://gateoverflow.in/1325/gate2009-39

This question also asks for worst time complexity. How is the answer different then? Please explain.

+6 votes

^{2}) when all elements are same.

Simply, check for all these cases first.

So, in ascending/descending order, choosing mid element as pivot gives O(nlogn) but choosing all elements same such as [2 2 2 2 2] still gives **O(n ^{2}).**

+1 vote

A.

The Worst case time complexity of quick sort is O (n^2). This will happen when the elements

of the input array are already in order (ascending or descending), irrespective of position of

pivot element in array.

The Worst case time complexity of quick sort is O (n^2). This will happen when the elements

of the input array are already in order (ascending or descending), irrespective of position of

pivot element in array.

+1 vote

when we select the central element as pivot element then the worst case time complexity will be O(nlogn).You may get doubt why not always choose mid element as pivot,this is because although this produceses O(nlogn) time complexity when we compute the constant time also then this will be more than selecting other elements as pivot.

0

@admin when we choose central element as pivot then T.c will be O(nlogn) assumed that array is sorted in ascending or descending order but if the array is unsorted then every time in worst case that central element can go into extreme position (left or right) & cause T.C O(n^2).

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 590
- Exam Queries 575
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,397 questions

53,564 answers

185,723 comments

70,837 users