Quicksort and Divide-and-Conquer Analysis Short Notes for GATE DA

Quicksort and Divide-and-Conquer Analysis short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Rules for Swap Counting

Summary

Quick Rules for Swap Counting

Consolidate the rules for counting swaps. Always read the pseudocode carefully to determine if self-swaps are counted as executed statements or ignored as zero data movements.

Identify Scheme: Is it Lomuto (1 pointer, left-to-right) or Hoare (2 pointers, inward)?

Identify Pivot: Is it the first, last, or middle element?

Check Self-Swaps: Does the pseudocode have an if i != j check before swapping?

Lomuto Shortcut: If array is sorted and pivot is max

⟹

0 swaps. If reverse sorted and pivot is min

⟹

1 swap.

Hoare Shortcut: Hoare never does self-swaps. Count inversions crossed by the two pointers.

Final Placement: Remember Lomuto does one final swap to place the pivot. Hoare does not.

Quick Recap: Recurrence Analysis

Summary

Quick Recap: Recurrence Analysis

Randomized Quicksort picks a pivot uniformly at random, giving each rank a

\frac{1}{n}

probability.

The fundamental recurrence is

T (n) = \frac{1}{n} \sum_{i = 1}^{n} [T (i - 1) + T (n - i)] + Θ (n)

Due to symmetry, this simplifies to

T (n) = \frac{2}{n} \sum_{k = 0}^{n - 1} T (k) + Θ (n)

Solving this via substitution or integral bounds yields the expected time complexity of

Θ (n lo g n)

Verification Check: Always verify the subarray sizes are

i - 1

and

n - i

, and that the linear partition cost

Θ (n)

is explicitly present in the equation.

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

Question 1 · Programming, Data Structures and Algorithms MCQ

In the expected time recurrence relation for randomized Quicksort, what does the linear term $O (n)$ represent?

A.
The time to recursively sort the left subarray
B.
The time to recursively sort the right subarray
C.
The time required for the partitioning step itself
D.
The time to randomly select the pivot

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the components of the expected time recurrence relation for Quicksort.

Step 1: Recall the structure of the recurrence relation: $T (n) = \frac{1}{n} \sum [T (k) + T (n - k - 1)] + O (n)$ .

Step 2: The terms $T (k)$ and $T (n - k - 1)$ represent the expected time to recursively sort the left and right subarrays.

Step 3: The $O (n)$ term is added outside the summation. It represents the work done at the current level of recursion before making the recursive calls.

Step 4: This work is the partitioning step, which scans the array and rearranges elements, taking linear time $O (n)$ .

Answer: C

Question 2 · Programming, Data Structures and Algorithms MCQ

What is the primary goal of the partitioning step in the Quicksort algorithm?

A.
To find the minimum element in the current subarray.
B.
To place the pivot element in its correct sorted position, with all smaller elements before it and all larger elements after it.
C.
To divide the array into two subarrays of exactly equal size.
D.
To sort the entire array in a single linear pass without recursion.

Correct Answer:

Step-by-Step Solution

Key idea: This is a definition question, recognizable by the request to identify the fundamental purpose of a specific algorithm step.

Step 1: Recall the definition of Quicksort partitioning. The core intuition is to pick a pivot and rearrange the array.

Step 2: Identify the rearrangement goal. All elements smaller than the pivot must come before it, and all elements larger must come after it.

Step 3: Conclude the result. Once this is done, the pivot is in its final sorted position, and the algorithm can recursively sort the left and right subarrays.

Answer: B

Question 3 · Programming, Data Structures and Algorithms MCQ

If the standard Lomuto partition scheme (using the last element as the pivot) is applied to an array that is already sorted in ascending order, what is the immediate result of the first partition step?

A.
The pivot is placed at the beginning of the array.
B.
The array is divided into two perfectly equal halves.
C.
The pivot remains at the end of the array, which is its correct final sorted position.
D.
The algorithm terminates immediately without performing any comparisons.

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application question testing the behavior of the Lomuto scheme on a specific edge-case input.

Step 1: Identify the input: an array already sorted in ascending order.

Step 2: Identify the pivot: the last element, which is the maximum element in the subarray.

Step 3: Trace the partition logic. Since every element in the array is less than or equal to the maximum element (the pivot), the condition $A [j] \leq pivot$ is always true.

Step 4: Conclude the result. The boundary pointer $i$ will simply track the scanning pointer $j$ , resulting in self-swaps. Finally, the pivot is swapped with itself at the end. The pivot remains at the end, which is its correct final sorted position.

Answer: C

Question 4 · Programming, Data Structures and Algorithms MCQ

In the expected recurrence analysis of randomized Quicksort, what is the probability that any specific element is chosen as the pivot from a subarray of size $n$ ?

A.
$1/2$
B.
$1/ n$
C.
$1/ (n - 1)$
D.
$1/ lo g n$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the fundamental probability distribution used in randomized Quicksort.

Step 1: Recall the definition of randomized Quicksort. The pivot is chosen uniformly at random from the current subarray.

Step 2: "Uniformly at random" means every element in the subarray has an equal chance of being selected.

Step 3: Since there are $n$ elements in the subarray, the probability of selecting any specific element is exactly $1/ n$ .

Answer: B

Question 5 · Programming, Data Structures and Algorithms MCQ

In the standard Lomuto partition scheme, which element is conventionally chosen as the pivot for a given subarray?

A.
The first element of the subarray.
B.
The middle element of the subarray.
C.
The last element of the subarray.
D.
A randomly selected element from the subarray.

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the mechanics of a specific partitioning scheme.

Step 1: Identify the scheme mentioned in the question: Lomuto partition scheme.

Step 2: Recall the standard implementation of the Lomuto scheme. It conventionally selects the last element of the current subarray (at index $r$ ) as the pivot.

Step 3: Match this fact with the given options.

Answer: C

Question 6 · Programming, Data Structures and Algorithms MCQ

During the Lomuto partition process, a swap between A[i] and A[j] is triggered when which condition is satisfied?

A.
A[j] is strictly greater than the pivot.
B.
A[j] is less than or equal to the pivot.
C.
A[i] is less than the pivot.
D.
A[i] is greater than A[j].

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question about the specific conditional logic inside the Lomuto partition loop.

Step 1: Recall the Lomuto partition pseudocode. The loop iterates with a pointer $j$ from the start of the subarray to the second-to-last element.

Step 2: Identify the condition for swapping. The algorithm checks if the current element $A [j]$ is less than or equal to the pivot.

Step 3: If the condition $A [j] \leq pivot$ is true, the boundary pointer $i$ is incremented, and $A [i]$ is swapped with $A [j]$ .

Answer: B

Question 7 · Programming, Data Structures and Algorithms MCQ

According to the standard rules for counting swaps in the Lomuto partition scheme, if self-swaps are ignored (not counted as data movements), how many swaps are performed during a single partition step on an already sorted array where the pivot is the maximum element?

A.
0
B.
1
C.
$n$
D.
$n - 1$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of the quick rules for swap counting in a specific edge-case scenario.

Step 1: Identify the scenario: already sorted array, pivot is the maximum element (last element).

Step 2: Recall the swap condition. Every element $A [j]$ is $\leq$ the pivot, so the algorithm increments $i$ and swaps $A [i]$ with $A [j]$ .

Step 3: Analyze the indices. Because every element is $\leq$ the pivot, $i$ will always exactly equal $j$ during the loop. Thus, every swap is a self-swap ( $A [j]$ with $A [j]$ ).

Step 4: Apply the rule. The final step swaps $A [i + 1]$ with the pivot $A [r]$ . Since $i$ ended at $r - 1$ , $i + 1$ equals $r$ , resulting in another self-swap.

Step 5: Conclude. If self-swaps are ignored, the number of actual data movement swaps is 0.

Answer: A

Question 8 · Programming, Data Structures and Algorithms NAT

Consider an array sorted in strictly descending order. If the standard Lomuto partition scheme is applied with the last element as the pivot, how many actual data-movement swaps (excluding self-swaps) are performed during this single partition step?

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of Lomuto partition mechanics on a specific edge-case input (reverse sorted array).

Step 1: Understand the input. The array is strictly descending, e.g., $[5, 4, 3, 2, 1]$ . The pivot $x$ is the last element, which is the minimum element (e.g., $1$ ).

Step 2: Trace the Lomuto partition loop. The index $i$ is initialized to $p - 1$ . The loop variable $j$ goes from $p$ to $r - 1$ .

Step 3: For each $j$ , we check if $A [j] \leq x$ . Since $x$ is the minimum element, $A [j] \leq x$ is false for all $j$ in the loop.

Step 4: Therefore, $i$ is never incremented inside the loop, and no swaps occur during the loop.

Step 5: After the loop, the algorithm performs exactly one swap: <code>swap(A[i + 1], A[r])</code>. Since $i = p - 1$ , $i + 1 = p$ . This swaps the first element with the last element (the pivot).

Step 6: This is exactly 1 actual data-movement swap. Self-swaps are excluded by the problem statement, and there are none here anyway.

Answer: 1

Question 9 · Programming, Data Structures and Algorithms MCQ

Consider an array of $n$ distinct elements sorted in strictly descending order. If the standard Lomuto partition scheme is applied using the last element as the pivot, what will be the size of the left subarray for the next recursive call?

A.
$n - 1$
B.
$0$
C.
$⌊ n /2 f l oor$
D.
$1$

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct application of Lomuto partition mechanics on a specific edge-case input (reverse sorted array).

Step 1: Understand the input. The array is strictly descending, so the last element (the pivot) is the minimum element of the array.

Step 2: Trace the Lomuto partition loop. The loop checks if $A [j] \leq$ pivot. Since the pivot is the minimum, no element in the loop (from $p$ to $r - 1$ ) will satisfy this condition.

Step 3: Therefore, the boundary pointer $i$ is never incremented and remains at $p - 1$ .

Step 4: After the loop, the final swap places the pivot at $i + 1$ , which is $p$ . The pivot is now at the very first index.

Step 5: The left subarray is defined as the elements before the pivot. Since the pivot is at index $p$ , the left subarray is empty. Its size is 0.

Answer: B

Question 10 · Programming, Data Structures and Algorithms MCQ

According to the quick rules for swap counting, if an array is already sorted in ascending order and the pivot is the maximum element, how many actual data-movement swaps (ignoring self-swaps) are performed in a single Lomuto partition step?

A.
0
B.
1
C.
n - 1
D.
n

Correct Answer:

Step-by-Step Solution

Key idea: This is a direct recall question applying the quick rules for swap counting on a specific edge case.

Step 1: Recall the Lomuto partition mechanics. The loop scans elements and swaps them to the left side if they are $\leq$ the pivot.

Step 2: If the array is already sorted in ascending order, every element scanned is $\leq$ the pivot (which is the maximum element).

Step 3: This means the boundary pointer $i$ increments for every element, perfectly matching the scanning pointer $j$ .

Step 4: Consequently, every swap inside the loop is a self-swap ( $i = j$ ).

Step 5: The final pivot placement swap is also a self-swap, as the pivot is already at the correct position.

Step 6: Since all swaps are self-swaps and the rule specifies ignoring them, the number of actual data-movement swaps is exactly 0.

Answer: A