Elementary Sorting Algorithms PYQs for GATE DA

Solve 3+ Elementary Sorting Algorithms previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Elementary Sorting Algorithms

Chapter Roadmap

Elementary Sorting Algorithms

Topic 1: Bubble, Insertion and Selection Sort Pass Analysis

Master the invariants, intermediate states, and exact operation counts for the three elementary sorts. (Current Topic)

Topic 2: Insertion Sort Swaps and Nearly Sorted Arrays

Deep dive into shifts, swaps, and the mathematics of inversions in partially sorted data.

The Core Idea of Pass Analysis

The Concept of a "Pass"

A pass is one complete iteration of the algorithm's primary loop. In exam questions, you are rarely asked to sort the whole array. You are asked to determine the state of the array after exactly $k$ passes.

The Golden Rule

Do not trace the whole algorithm. Identify the invariant: what is mathematically guaranteed to be in its final sorted position after pass $k$ ?

Bubble Sort: Locks elements at the end.
Selection Sort: Locks elements at the beginning.
Insertion Sort: Sorts a prefix of the array.

Elementary Sorting Algorithms: Solved Questions with Step-by-Step Explanations (3 Problems)

Question 1 · Programming, Data Structures and Algorithms · 2026 MSQ

Consider the problem of sorting the given array in ascending order:

P = [1, 2, 3, 5, 4]

Consider two sorting algorithms Bubble Sort (BS) and Insertion Sort (IS).

Let N1 be the total number of comparisons done by BS on the elements of P and N2 be the total number of comparisons done by IS on the elements of P.

Which of the following options is/are correct?

A.
N1 = 10, N2 = 4
B.
N1 > N2
C.
IS on P will perform only one swap
D.
Both BS and IS on P will make at least one unnecessary comparison (i.e., comparing elements that are already in correct order)

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Insight: This is a pass-analysis question recognisable because it asks for exact operation counts on a tiny concrete array. The pivot is that Bubble Sort (standard, no early termination) has a deterministic comparison count while Insertion Sort's count is data-dependent and must be traced element by element.

Exam route:

Compute N1 using the fixed formula: for $n = 5$ , standard Bubble Sort does $(n - 1) + (n - 2) + (n - 3) + (n - 4) = 4 + 3 + 2 + 1 = 10$ ... wait, that is only for a full sort. Let us recompute carefully: pass 1 does $n - 1 = 4$ , pass 2 does $n - 2 = 3$ , pass 3 does $2$ , pass 4 does $1$ . Total $= 4 + 3 + 2 + 1 = 10$ .
Trace Insertion Sort on $P = [1, 2, 3, 5, 4]$ :

key=2: compare with 1 (1 cmp), no shift.
key=3: compare with 2 (1 cmp), no shift.
key=5: compare with 3 (1 cmp), no shift.
key=4: compare with 5 (shift), compare with 3 (stop) → 2 cmp, 1 shift.
Total $N_{2} = 1 + 1 + 1 + 2 = 5$ , shifts $= 1$ .

Evaluate options: $N_{1} = 10, N_{2} = 5$ ; $N_{1} > N_{2}$ holds; IS does exactly 1 swap; BS in passes 2–4 compares already-sorted adjacent pairs (unnecessary), and IS compares 4 with 5 which are out of order but the comparison that stops at 3 (already in correct relative order with 4) is the boundary check — BS clearly makes unnecessary comparisons, so D holds.

Learning route:

Bubble Sort (standard, no flag) always performs exactly $\sum_{i = 1}^{n - 1} (n - i) = \frac{n ( n - 1 )}{2}$ comparisons regardless of input. For $n = 5$ , $N_{1} = 10$ .

Insertion Sort comparisons depend on how far each key travels. Tracing $P = [1, 2, 3, 5, 4]$ :

key=2 vs {1}: 1 comparison, 0 shifts.
key=3 vs {1,2}: 1 comparison, 0 shifts.
key=5 vs {1,2,3}: 1 comparison, 0 shifts.
key=4 vs {1,2,3,5}: compares with 5 (shift), then with 3 (stop) → 2 comparisons, 1 shift.

Total $N_{2} = 5$ , shifts = 1.

Option A claims $N_{1} = 10, N_{2} = 4$ — wrong because $N_{2} = 5$ , not 4.

Option B: $10 > 5$ — true.

Option C: IS performs exactly 1 swap/shift — true.

Option D: BS in passes 2, 3, 4 compares pairs already in correct order (e.g. 1 and 2 in pass 2); IS compares 4 with 5 which are out of order but the stop-comparison with 3 is against an element already in correct relative position — both algorithms make at least one such comparison. True.

Verification: re-running both algorithms on $P$ confirms $N_{1} = 10, N_{2} = 5$ , 1 IS shift, and unnecessary comparisons in both.

Answer: B, C, D.

Question 2 · Programming, Data Structures and Algorithms · 2025 MSQ

Suppose that insertion sort is applied to the array $[1, 3, 5, 7, 9, 11, x, 15, 13]$ and it takes exactly two swaps to sort the array. Select all possible values of $x$ .

A.
$10$
B.
$12$
C.
$14$
D.
$16$

Correct Answer:

["C"]

Step-by-Step Solution

Insight: This is the classic 'unknown element in a nearly sorted array' pattern recognisable because a sorted or nearly sorted array contains one unknown $x$ and the total number of swaps (inversions) is given. The pivot is the split method: partition the array around $x$ and count inversions in each piece.

Exam route:

Split $[1, 3, 5, 7, 9, 11, x, 15, 13]$ into Left $= [1, 3, 5, 7, 9, 11]$ , $x$ , Right $= [15, 13]$ .
Count inversions within Left: 0 (perfectly sorted).
Count inversions within Right: 1 (pair (15,13)).
Count inversions involving $x$ :

With Left: since all Left elements $\leq 11$ , if $x \geq 11$ then 0 inversions with Left; if $x < 11$ , then inversions with Left $= ∣ {l \in Left : l > x} ∣$ .
With Right $= [15, 13]$ :
If $x \geq 15$ : 0 inversions with Right.
If $13 \leq x < 15$ : 1 inversion (15 > x).
If $11 < x < 13$ : 2 inversions (15 > x and 13 > x).
If $x \leq 11$ : 2 inversions with Right, plus inversions with Left.

Total inversions $= 0 + 1 + I_{Left > x} + I_{x > Right} = 2$ .

So $I_{Left > x} + I_{x > Right} = 1$ .

Case analysis:

$x \geq 15$ : $I_{x > Right} = 0$ , $I_{Left > x} = 0$ (since all Left $\leq 11 < 15$ ). Sum = 0. No.
$13 \leq x < 15$ : $I_{x > Right} = 1$ , $I_{Left > x} = 0$ (since all Left $\leq 11 < 13$ ). Sum = 1. ✓
$11 < x < 13$ (i.e. $x = 12$ ): $I_{x > Right} = 2$ , $I_{Left > x} = 0$ . Sum = 2. No.
$x \leq 11$ : $I_{x > Right} = 2$ , $I_{Left > x} \geq 1$ . Sum $\geq 3$ . No.

So $x \in [13, 14]$ . Among the options ${10, 12, 14, 16}$ , only 14 is valid.

Learning route:

The split method works because inversions decompose additively:

$I_{total} = I_{Left} + I_{Right} + I_{Left > x} + I_{x > Right} .$

Here $I_{Left} = 0$ and $I_{Right} = 1$ , so we need $I_{Left > x} + I_{x > Right} = 1$ .

Since all Left elements are $\leq 11$ , any $x \geq 13$ gives $I_{Left > x} = 0$ . Then we need $I_{x > Right} = 1$ , which means exactly one of ${15, 13}$ is greater than $x$ . This happens iff $13 \leq x < 15$ , i.e. $x \in {13, 14}$ .

Verification: for $x = 14$ , inversions are (15,13) and (15,14) — total 2 ✓. For $x = 10$ , inversions are (15,13), (11,10), (15,10), (13,10) — total 4 ✗.

Answer: C (only 14).

Question 3 · Programming, Data Structures and Algorithms · 2024 MCQ

Consider the following sorting algorithms:

i

Bubble sort

ii

Insertion sort

iii

Selection sort
Which ONE among the following choices of sorting algorithms sorts the numbers
in the array [4, 3, 2, 1, 5] in increasing order after exactly two passes over the array?

A.
$i$ only
B.
$iii$ only
C.
$i$ and $iii$ only
D.
$ii$ and $iii$ only

Correct Answer:

Step-by-Step Solution

Insight: This is a pass-state question recognisable because it asks which algorithm(s) fully sort a specific array in exactly two passes. The pivot is the invariant each algorithm guarantees after $k$ passes: Bubble locks the $k$ largest at the right, Selection locks the $k$ smallest at the left, Insertion sorts the first $k + 1$ elements.

Exam route:

Apply each algorithm for 2 passes on $[4, 3, 2, 1, 5]$ .
Bubble pass 1: $(4, 3) \to$ swap, $(3, 2) \to$ swap, $(2, 1) \to$ swap, $(1, 5) \to$ no swap → $[3, 2, 1, 4, 5]$ .

Bubble pass 2: $(3, 2) \to$ swap, $(2, 1) \to$ swap, $(1, 4) \to$ no, $(4, 5) \to$ no → $[2, 1, 3, 4, 5]$ . Not sorted.

Insertion pass 1 (key=3): shift 4 → $[3, 4, 2, 1, 5]$ .

Insertion pass 2 (key=2): shift 4, shift 3 → $[2, 3, 4, 1, 5]$ . Not sorted.

Selection pass 1: min of $[4, 3, 2, 1, 5]$ is 1, swap with index 0 → $[1, 3, 2, 4, 5]$ .

Selection pass 2: min of $[3, 2, 4, 5]$ is 2, swap with index 1 → $[1, 2, 3, 4, 5]$ . Sorted!

Only Selection (iii) sorts in exactly 2 passes. Answer: B.

Learning route:

The array $[4, 3, 2, 1, 5]$ has a special structure: the first four elements are reverse-sorted and the last is already the maximum.

Bubble Sort bubbles the largest element to the end in pass 1, but the remaining four elements are still reverse-sorted and need 3 more passes. After 2 passes, the array is $[2, 1, 3, 4, 5]$ — not sorted.
Insertion Sort sorts a growing prefix. After 2 passes, only the first 3 elements are sorted; the 1 at index 3 is still out of place.
Selection Sort places the smallest element at the front each pass. Pass 1 places 1, pass 2 places 2. Since the remaining elements $[3, 4, 5]$ are already sorted, the array is fully sorted after 2 passes.

Verification: re-tracing confirms only Selection produces $[1, 2, 3, 4, 5]$ after exactly 2 passes.

Answer: B.

Try a question

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

Elementary Sorting Algorithms PYQs for GATE DA

Chapter Roadmap: Elementary Sorting Algorithms

Chapter Roadmap

The Core Idea of Pass Analysis

The Core Idea of Pass Analysis

The Concept of a "Pass"

The Golden Rule

Elementary Sorting Algorithms: Solved Questions with Step-by-Step Explanations (3 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit