The Gateway to Computer Science Excellence
+9 votes
3.1k views
An array of $25$ distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to $2$ decimal places) is ________
in Algorithms by Veteran (423k points)
edited by | 3.1k views

3 Answers

+19 votes
Best answer
Worst case of quicksort, if pivot element is Minimum or Maximum.

Total elements $= 25$
For worst case number of candidates $= 2$

$P = \frac{2}{25} = 0.08 $
by Veteran (60.4k points)
selected by
0
Say if we take  middle element as pivot and array be like this 4  2.  1   3   5, then will not pivot placed in worst possible location?
0
Yup, if you choose 1 and 5 only then
+1
It will be 4/25 as minimum 2ndminimum maximum and 2nd maximum


2nd minimum and maximum becoz only one element at left or right side
+2
Why aren't we considering second min and max. Say if we considered second max, the list will break into n-2 and 1 which is still the worst choice to be pivot. Right?
+2
@Z1311 No, then you have to deal with one less element which is saving the time to sort that particular element which in the other case would have needed to be sorted among a big list of numbers
0

This case will also give worst case

0

@Digvijay Pandey

@Shaik_Masthan

@Rishi yadav

Plz chk it. 

Why am I getting some more cases? Are those cases not correct?

0

@srestha Please read the answer once more. 

0

is this case can we not consider as worst case?

https://gateoverflow.in/2048/gate2014-3-14

0

@srestha This case is different here 

the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location

Whereas the question which u have mentioned 

implement quicksort by always choosing the central element of the array as the pivot​​​​​​​ 

So both are different 

0

Plz tell more, where is the difference?

See

the pivot element is chosen uniformly at random.

we can take take central element as pivot

Now 

The probability that the pivot element gets placed in the worst possible location

According to our array it is worst location

isnot it? 

0

@Arjun Sir

if I ask this question for review

Can I get some extra marks?

here question asked for

the pivot element is chosen uniformly at random

+1

 

Probability of random Quick sort depends on how close they are in sorted array , if they are far then low probability, if they are close then high probability

 

Unsorted:

5 1 8 9 2 4 7 3 6

Sorted :

1 2 3 4 5 6 7 8 9


CASE -1

5 1 8 2 4 7 3 6
9

CASE -2

1
5 8 2 4 7 3 6 9

In 1 and 9 we have to compare pivot with all the elements and running time depends on the number of comparisons 

0

@srestha

In the above array, if we select 3 as pivot then 1 and 9 will go in different subarrays this happens with all the elements other than 1,9 (2,3,4,5,6,7,8). In this case, 1 and 9 never compared but if we choose 1 as a pivot then it will compare with all $n-1$ numbers similarly for 9 as a pivot

so these are only worst possible locations 

0

@Rishi yadav

what is meaning of worst possible location?

Though there is no definition for it, still we can say  a worst possible location of pivot, when worst case occur in corresponds to that location of pivot

Generally furthest location, we say as worst case behavior.

Even 2,2,2,2,2 this also gives worst case behavior for quick sort.

So, 

Worst possible location of n numbers are either 1 or n 

this line is not correct

and

if we select 3 as pivot then 1 and 9 will go in different subarrays

 what u mean by this? I couldnot understand

0
0

@Rishi yadav

here pivot choosen uniformly and randomly

So, it behaves like randomized quicksort

And, in randomized quicksort, we are more likely to find pivot as central element

Now, contrast this with randomized quicksort. In randomized quicksort, you truly choose a random element as your pivot at each step. This means that while you technically could choose the same pivots as in the deterministic case, it's very unlikely (the probability would be roughly 22 - n, which is quite low) that this will happen and trigger the worst-case behavior. You're more likely to choose pivots closer to the center of the array, and when that happens the recursion branches more evenly and thus terminates a lot faster.

https://stackoverflow.com/questions/41513856/can-someone-clarify-the-difference-between-quicksort-and-randomized-quicksort

 

  • No specific input elicits the worst-case behavior.

• The worst case is determined only by the sequence s of random numbers

 

http://www.cs.tulane.edu/~carola/teaching/cmps2200/fall14/slides/Lecture-randomizedAlgos.pdf

So, we no need to take sorted array in randomized quicksort

0

@Rishi yadav

I heard full lecture, but that never told other worst cases not possible. He just gave an example

Moreover, it is a unique question, u cannot find total answer in any lecture or notes

@Digvijay Pandey

plz clarify ur answer

question asked

 The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is 

 So, it is telling about location , not only the element

right?

Can it not be 1st position, last position, and also center position

0

You are right it can be 1st , last and center as well but before 1st partitioning  

In randomized quicksort, you truly choose a random element as your pivot at each step.

https://stackoverflow.com/questions/41513856/can-someone-clarify-the-difference-between-quicksort-and-randomized-quicksort

.We don't need to worry about each step because it is given

The probability that the pivot element gets placed in the worst possible location in the first round of partitioning

so we have to choose some random value only one time because of the first round of partitioning.

Let's say we have an unsorted array and we select some random value, let's say x for this value to place at the worst possible location when x placed at 0th place or n-1'th place

then $T(n)=n+T(n-1)$  not center 

$Note:$ We can choose center value also before the 1st round of partitioning but for worst possible location this value too, have to place either 0th index or n-1th index

 

0

And for this 

 You're more likely to choose pivots closer to the center of the array, and when that happens the recursion branches more evenly and thus terminates a lot faster. 

please read this once more its not for the worst case 

0

@Rishi yadav

Great explanation. The position containing the lowest or the highest value is the worst case for choosing the pivot.

+6 votes
I think 2/25
by Active (1.6k points)
0
2/25
0
not 1/25 :(
0
Even I am not sure but if pivot element is first or last element then it can be worst case let's wait for answer key!!
0
the paper seemed easy
but so many silly things :( :/
+1 vote
Quick sort puts the pivot element in its correct place after 1st iteration. The worst place the pivot element can be placed at is extreme left or extreme right because in that case the array is divided in the ratio 1:n-1 giving complexity of O(n Square). The pivot element will come to extreme left or right after 1st iteration if it's minimum or maximum.So pivot can be either minimum or maximum.

So 2 out of 25 elements can be selected for pivot thus giving a probability of 2/25 equal to 0.08.
by (431 points)

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
50,650 questions
56,236 answers
194,264 comments
95,871 users