The Gateway to Computer Science Excellence

+9 votes

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 ________

+19 votes

Best answer

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?

+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

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

@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

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

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

@sresthaI think this video will clear your doubt

https://www.coursera.org/lecture/algorithmic-toolbox/running-time-analysis-optional-hB4em

0

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

couldchoose 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.

- 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

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

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.

.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

+6 votes

+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.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,236 answers

194,264 comments

95,871 users