Quicksort and Divide-and-Conquer Analysis Previous Year Questions (PYQs) for GATE DA: 2+ Solved Questions with Step-by-Step Solutions

Solve 2+ Quicksort and Divide-and-Conquer Analysis previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Quicksort and Divide-and-Conquer

Orientation

Chapter Roadmap: Quicksort and Divide-and-Conquer

Welcome to the chapter on Quicksort and Divide-and-Conquer Analysis. We will first master the mechanics of Quicksort partitioning and learn how to precisely count swaps. Then, we will transition into the mathematical analysis of expected recurrence relations.

Step 1: Quicksort Partitioning and Swap Count

Master the Lomuto and Hoare schemes. Trace arrays, count exact swaps, and handle edge cases like sorted or reverse-sorted inputs.

Step 2: Expected Recurrence Analysis

Formulate and solve the recurrence relation for randomized Quicksort to prove the expected $O (n lo g n)$ time complexity.

The Heart of Quicksort: Partitioning

Concept

The Heart of Quicksort: Partitioning

The fundamental principle of Quicksort relies on the Partitioning Step:

Choose a Pivot: Select an element from the array (e.g., the last, first, or a random element).

Partition: Rearrange the array such that:

Every element in the left subarray is $\leq$ pivot.
Every element in the right subarray is $\geq$ pivot.
The pivot is placed in its exact final sorted index.

Recurse: Recursively apply Quicksort to the left and right subarrays.

The partitioning step takes $O (n)$ time. The overall time complexity depends on how balanced the resulting subarrays are, which is dictated by the pivot choice and the specific partitioning scheme used.

Quicksort and Divide-and-Conquer Analysis: Solved Questions with Step-by-Step Explanations (2 Problems)

Question 1 · Programming, Data Structures and Algorithms MCQ

Consider that the quick sort algorithm is used to sort an array of n distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray.
Let

T (n)

denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray.
Which of the following recurrence relations correctly represents

T (n)

in this scenario?

A.
$T (n) = T (1) + T (n - 1) + O (n)$
B.
$T (n) = T (\frac{n}{4}) + T (\frac{3 n}{4}) + O (n)$
C.
$T (n) = 2 T (\frac{n}{2}) + O (n)$
D.
$T (n) = \frac{1}{n} \sum_{k = 0}^{n - 1} [T (k) + T (n - k - 1)] + O (n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is an expected recurrence analysis problem for Quicksort, recognizable by the phrases "expected time", "randomly ordered elements", and a fixed pivot position (first element).

Step 1: Understand the pivot selection dynamics.

Although the pivot is deterministically chosen as the first element of the subarray, the array itself is randomly ordered. This means the first element is equally likely to be the $1$ st, $2$ nd, ..., or $n$ -th smallest element in the subarray.

Step 2: Determine the subproblem sizes.

Let the rank of the chosen pivot be $k + 1$ (where $k$ ranges from $0$ to $n - 1$ ).

The left subarray will contain the $k$ elements smaller than the pivot.
The right subarray will contain the remaining $n - 1 - k$ elements larger than the pivot.

Step 3: Formulate the expected time recurrence.

Since each possible rank $k$ occurs with a uniform probability of $\frac{1}{n}$ , the expected time $T (n)$ is the average of the expected times of all possible splits, plus the $O (n)$ time required for the partitioning step itself.

Mathematically, this is expressed as:

$T (n) = \frac{1}{n} k = 0 \sum n - 1 [T (k) + T (n - k - 1)] + O (n)$

Step 4: Match with the given options.

This derived formula exactly matches the fourth option.

Answer: D

Question 2 · Programming, Data Structures and Algorithms NAT

Consider sorting the following array of integers in ascending order using an in-place
Quicksort algorithm that uses the last element as the pivot.

60708090100

The minimum number of swaps performed during this Quicksort is ______.

Correct Answer:

Step-by-Step Solution

Key idea: This is a Quicksort trace problem, recognizable by the request to count the exact number of swaps for a specific array and pivot choice. We must simulate the standard Lomuto partition scheme.

Step 1: Identify the partition scheme.

The problem specifies an "in-place Quicksort algorithm that uses the last element as the pivot". This corresponds to the standard Lomuto partition scheme.

Step 2: Trace the first partition on the array $[60, 70, 80, 90, 100]$ .

Pivot $x = 100$ .
Initialize $i = p - 1 = - 1$ .
Loop $j$ from $0$ to $3$ :
$j = 0$ : $A [0] = 60 \leq 100$ . Increment $i$ to $0$ . Swap $A [0]$ with $A [0]$ . (1 swap)
$j = 1$ : $A [1] = 70 \leq 100$ . Increment $i$ to $1$ . Swap $A [1]$ with $A [1]$ . (1 swap)
$j = 2$ : $A [2] = 80 \leq 100$ . Increment $i$ to $2$ . Swap $A [2]$ with $A [2]$ . (1 swap)
$j = 3$ : $A [3] = 90 \leq 100$ . Increment $i$ to $3$ . Swap $A [3]$ with $A [3]$ . (1 swap)
End of loop. Swap $A [i + 1]$ with $A [r]$ , which is Swap $A [4]$ with $A [4]$ . (1 swap)

Total swaps in this step = $5$ .

Step 3: Analyze the recursive calls.

The pivot $100$ is now in its correct final position. The left subarray is $[60, 70, 80, 90]$ (size 4), and the right subarray is empty.

Step 4: Repeat the process for the remaining subarrays.

For size 4 ( $[60, 70, 80, 90]$ ), pivot is $90$ . By the same logic, it requires $4$ swaps.
For size 3 ( $[60, 70, 80]$ ), pivot is $80$ . Requires $3$ swaps.
For size 2 ( $[60, 70]$ ), pivot is $70$ . Requires $2$ swaps.
For size 1 ( $[60]$ ), pivot is $60$ . Requires $1$ swap.

Step 5: Calculate the total number of swaps.

Total swaps = $5 + 4 + 3 + 2 + 1 = 15$ .

Answer: 15

A question from this chapter

Question 1

Consider that the quick sort algorithm is used to sort an array of n distinct randomly ordered elements. In every call, the pivot is chosen as the first element of the current subarray. Let T (n) denote the expected time to sort the array. Assume that the time to partition is linear in the size of the current subarray. Which of the following recurrence relations correctly represents T (n) in this scenario?

Question 2

Consider sorting the following array of integers in ascending order using an in-place Quicksort algorithm that uses the last element as the pivot. 60708090100 The minimum number of swaps performed during this Quicksort is ______.

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Quicksort and Divide-and-Conquer Analysis Previous Year Questions (PYQs) for GATE DA: 2+ Solved Questions with Step-by-Step Solutions

Chapter Roadmap: Quicksort and Divide-and-Conquer

Chapter Roadmap: Quicksort and Divide-and-Conquer

Step 1: Quicksort Partitioning and Swap Count

Step 2: Expected Recurrence Analysis

The Heart of Quicksort: Partitioning

The Heart of Quicksort: Partitioning

Quicksort and Divide-and-Conquer Analysis: Solved Questions with Step-by-Step Explanations (2 Problems)

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit

A question from this chapter

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course