GATE CS 2019 Q.30 (CS Q.20): Searching and Sorting Algorithms

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

Your answer

Official answer and solution

Official answer: 0.08
From: Official GATE 2019 answer key

Solution

Identify the worst-case pivot positions in quicksort partitioning and compute their selection probability.

In quicksort, the partitioning step splits an array of $n$ distinct elements around a selected pivot element.

The worst possible partition occurs when the pivot creates the most unbalanced split possible:

The pivot is the minimum element, resulting in subproblems of size $0$ and $n - 1 = 24$ .
The pivot is the maximum element, resulting in subproblems of size $n - 1 = 24$ and $0$ .

Both the minimum and maximum elements place the pivot in the worst possible location (an extreme location that maximizes subsequent recursion depth).

There are $2$ such worst-case elements out of $n = 25$ distinct elements. Since the pivot is chosen uniformly at random:

P = \frac{2}{25} = 0.08

Final answer

0.08

Common trap

Considering only the minimum element (1/25 = 0.04) and forgetting the maximum element.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 30 of 65, printed as CS Q.20
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source