Elementary Sorting Algorithms Notes for GATE DA

Elementary Sorting Algorithms notes for GATE DA: 22 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

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.

Bubble Sort: Mechanics and Invariants

Bubble Sort: Mechanics & Invariants

Repeatedly step through the list, compare adjacent elements, and swap them if they are in the wrong order.

The Pass Invariant: After pass

k

, the

k

largest elements are in their final sorted positions at the end of the array.

Comparison Count

In the standard implementation (without early termination), the number of comparisons in pass $k$ is strictly deterministic:

Pass 1: $n - 1$ comparisons
Pass 2: $n - 2$ comparisons
Pass $k$ : $n - k$ comparisons

Total comparisons for

k

passes =

\sum_{i = 1}^{k} (n - i) = k n - \frac{k ( k + 1 )}{2}

Insertion Sort: Mechanics and Invariants

Insertion Sort: Mechanics & Invariants

Divide the array into a "sorted" and "unsorted" region. Repeatedly take the first element of the unsorted region and insert it into the correct position in the sorted region by shifting larger elements to the right.

The Pass Invariant: After pass

k

, the first

k + 1

elements of the array are sorted relative to each other.
(Note: Pass 1 processes the 2nd element, so after pass 1, the first 2 elements are sorted).

Comparison Count

The number of comparisons is data-dependent.

In pass $k$ , the algorithm compares the key against elements in the sorted prefix until it finds the correct spot.
Comparisons range from $1$ (best case, already in place) to $k$ (worst case, needs to go to the front).

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

Question 1 · Programming, Data Structures and Algorithms MCQ

Consider the array $P = [1, 3, 5, x, 9, 7]$ . It is given that Insertion Sort takes exactly 3 swaps to sort $P$ . Which of the following statements must be true about $x$ ?

A.
$x$ must be strictly less than 3
B.
$x$ can be greater than or equal to 9
C.
$x$ must be between 3 and 7
D.
$x$ cannot be 10

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question. We use the inversion sum to establish strict bounds on the unknown element $x$ .

Step 1: Split the array into Left, $x$ , and Right.

Left $L = [1, 3, 5]$ has 0 inversions.
Right $R = [9, 7]$ has 1 inversion (since $9 > 7$ ).

Step 2: Use the total inversion formula. "Swaps" means shifts, which equals inversions.

Total = $I_{L} + I_{R} + I (L > x) + I (R < x)$

$3 = 0 + 1 + I (L > x) + I (R < x)$

$I (L > x) + I (R < x) = 2$

Step 3: Analyze the cases for $x$ against the Right part $R = [9, 7]$ .

Case 1: $x \geq 9$ . Then $I (R < x) = 2$ (both 9 and 7 are $< x$ ). This forces $I (L > x) = 0$ . This is consistent because $x \geq 9$ means $x$ is greater than all elements in $L$ . So $x \geq 9$ is a valid solution.
Case 2: $7 \leq x < 9$ . Then $I (R < x) = 1$ (only 7 is $< x$ ). This forces $I (L > x) = 1$ . This means exactly 1 element in $[1, 3, 5]$ is $> x$ , so $3 \leq x < 5$ . This contradicts $7 \leq x < 9$ .
Case 3: $x < 7$ . Then $I (R < x) = 0$ . This forces $I (L > x) = 2$ . This means exactly 2 elements in $[1, 3, 5]$ are $> x$ , so $1 \leq x < 3$ . This is consistent with $x < 7$ .

Step 4: Combine valid ranges: $x < 3$ OR $x \geq 9$ .

Answer: B

Common trap: Ignoring the inversions within the Right part, which leads to the incorrect conclusion that $x$ must be strictly less than 3.

Question 2 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason: Assertion (A): After exactly 2 passes of Bubble Sort on an array of 8 elements, the 2 largest elements are in their final sorted positions at the end of the array. Reason (R): In Bubble Sort, each pass guarantees that the largest unsorted element moves to its correct position at the end.

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is not the correct explanation of A
C.
A is true, but R is false
D.
A is false, but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is an assertion-reason question testing Bubble Sort pass invariant.

Step 1: Evaluate Assertion (A):

Bubble Sort pass invariant: after k passes, the k largest elements are at the end
After 2 passes, the 2 largest elements are at the end
Assertion A is TRUE

Step 2: Evaluate Reason (R):

In each pass, Bubble Sort compares adjacent elements and swaps if needed
The largest unsorted element "bubbles up" to the end
Reason R is TRUE

Step 3: Check if R explains A:

R states that each pass moves the largest unsorted element to the end
After pass 1: largest element is at the end
After pass 2: second largest element is at position n-1 (since largest is already at n)
So after 2 passes, the 2 largest are at the end
R correctly explains why A is true

Answer: A

Question 3 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason: Assertion (A): After exactly 3 passes of Selection Sort on an array of 10 elements, the 3 smallest elements are in their final sorted positions at the beginning of the array. Reason (R): In each pass, Selection Sort finds the maximum element in the unsorted portion and swaps it to the end of the array.

A.
Both A and R are true, and R is the correct explanation of A
B.
Both A and R are true, but R is not the correct explanation of A
C.
A is true, but R is false
D.
A is false, but R is true

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question evaluating the pass invariants and mechanics of Selection Sort.

Step 1: Evaluate Assertion (A). Selection Sort's pass invariant states that after $k$ passes, the $k$ smallest elements are in their final sorted positions at the beginning of the array. For $k = 3$ , the 3 smallest elements are at the beginning. Assertion A is TRUE.

Step 2: Evaluate Reason (R). Selection Sort works by finding the MINIMUM element in the unsorted portion and swapping it to the BEGINNING of the unsorted portion. Reason R describes finding the MAXIMUM and swapping to the END, which is the mechanics of Bubble Sort (or a variant of Selection Sort that sorts from the end, but standard Selection Sort finds the min). Reason R is FALSE.

Step 3: Since A is true and R is false, the correct option is C.

Answer: C

Question 4 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason: Assertion (A): After exactly 3 passes of Insertion Sort on an array of 10 elements, the first 4 elements are sorted relative to each other. Reason (R): In each pass, the algorithm compares adjacent elements and swaps them if they are in the wrong order, causing the largest unsorted element to bubble to the end.

A.
Both A and R are true, and R is the correct explanation of A
B.
A is true, but R is false
C.
A is false, but R is true
D.
Both A and R are true, but R is not the correct explanation of A

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question evaluating the pass invariants and mechanics of different sorting algorithms.

Step 1: Evaluate Assertion (A). Insertion Sort's pass invariant states that after pass $k$ , the first $k + 1$ elements are sorted relative to each other. For $k = 3$ , the first $3 + 1 = 4$ elements are sorted. Assertion A is TRUE.

Step 2: Evaluate Reason (R). The reason describes comparing adjacent elements and swapping to bubble the largest to the end. This is the exact mechanics of Bubble Sort, not Insertion Sort. Insertion Sort takes a key and inserts it into the sorted prefix by shifting elements. Reason R is FALSE.

Step 3: Since A is true and R is false, the correct option is B.

Answer: B

Question 5 · Programming, Data Structures and Algorithms MCQ

Consider the following assertion and reason: Assertion (A): After exactly 3 passes of Insertion Sort, the first 4 elements of the array are guaranteed to be sorted relative to each other. Reason (R): Insertion Sort achieves this by finding the minimum element in the unsorted suffix and swapping it with the first unsorted element.

A.
A is true, but R is false
B.
Both A and R are true, and R is the correct explanation of A
C.
A is false, but R is true
D.
Both A and R are true, but R is not the correct explanation of A

Correct Answer:

Step-by-Step Solution

Key idea: This is a construction question evaluating the pass invariants and mechanics of different sorting algorithms.

Step 1: Evaluate Assertion (A). Insertion Sort's pass invariant states that after pass $k$ , the first $k + 1$ elements are sorted. For $k = 3$ , the first 4 elements are sorted. Assertion A is TRUE.

Step 2: Evaluate Reason (R). The reason describes finding the minimum in the unsorted suffix and swapping it to the front. This is the exact mechanics of Selection Sort, not Insertion Sort. Reason R is FALSE.

Step 3: Since A is true and R is false, the correct option is A.

Answer: A

Question 6 · Programming, Data Structures and Algorithms MCQ

Which of the following statements about Selection Sort is ALWAYS true, regardless of the initial order of elements?

A.
The number of comparisons depends on the initial arrangement of elements
B.
After k passes, the k largest elements are in their final positions at the end of the array
C.
The total number of comparisons for a full sort is always n(n - 1) / 2
D.
The algorithm terminates early if no swaps occur in a pass

Correct Answer:

Step-by-Step Solution

Key idea: This is a statement evaluation question about Selection Sort invariants.

Step 1: Recall that Selection Sort always scans the entire unsorted portion to find the minimum, regardless of data order.

Step 2: Evaluate each option:

Option A: FALSE. Selection Sort comparisons are invariant to data.
Option B: FALSE. Selection Sort locks the k smallest at the beginning, not k largest at the end (that's Bubble Sort).
Option C: TRUE. Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2, always.
Option D: FALSE. Standard Selection Sort doesn't have early termination.

Step 3: The correct answer is C.

Answer: C

Question 7 · Programming, Data Structures and Algorithms MCQ

Consider the standard implementation of Selection Sort (which always performs a swap, even if the minimum is already in place). Which of the following statements about the number of swaps is true?

A.
The total number of swaps depends on the initial order of the array.
B.
The algorithm performs exactly 1 swap per pass, resulting in $n - 1$ swaps for an array of size $n$ .
C.
The algorithm performs 0 swaps if the array is already sorted.
D.
The number of swaps per pass varies between 0 and $n - k$ .

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question evaluating the invariant properties of Selection Sort's swap count.

Step 1: Recall the mechanics of standard Selection Sort. In each pass, it finds the minimum element in the unsorted portion and swaps it with the first element of the unsorted portion.

Step 2: The problem specifies the "standard implementation" which "always performs a swap, even if the minimum is already in place".

Step 3: This means every pass executes exactly 1 swap operation.

Step 4: Since there are $n - 1$ passes (to sort $n$ elements), the total number of swaps is exactly $n - 1$ , regardless of the input data.

Answer: B

Question 8 · Programming, Data Structures and Algorithms MCQ

Which of the following correctly describes the exact total number of comparisons and total number of swaps in standard Selection Sort for an array of size $n$ ?

A.
Comparisons: depends on input, Swaps: $n - 1$
B.
Comparisons: $r a c n (n - 1) 2$ , Swaps: depends on input
C.
Comparisons: $r a c n (n - 1) 2$ , Swaps: $n - 1$
D.
Comparisons: $n^{2}$ , Swaps: $n$

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question evaluating the invariant properties of Selection Sort's operation counts.

Step 1: Recall the mechanics of standard Selection Sort. In each pass $k$ , it scans the entire unsorted suffix to find the minimum, requiring exactly $n - k$ comparisons.

Step 2: Summing comparisons over all $n - 1$ passes gives $\sum_{k = 1}^{n - 1} (n - k) = \frac{n ( n - 1 )}{2}$ . This is fixed and independent of the input data.

Step 3: In each pass, it performs exactly 1 swap (even if swapping an element with itself). Over $n - 1$ passes, this results in exactly $n - 1$ swaps.

Step 4: Both counts are strictly deterministic for standard Selection Sort.

Answer: C

Question 9 · Programming, Data Structures and Algorithms MCQ

Which of the following correctly describes the number of comparisons performed in the $k$ -th pass of Selection Sort on an array of $n$ elements?

A.
It depends on the initial order of elements, ranging from $1$ to $n - k$ .
B.
It is exactly $k$ , regardless of the initial order of elements.
C.
It is exactly $n - k$ , regardless of the initial order of elements.
D.
It is exactly $n - 1$ , regardless of the initial order of elements.

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question evaluating the invariant properties of Selection Sort's comparison count.

Step 1: Recall the mechanics of Selection Sort. In each pass $k$ , it scans the entire unsorted suffix to find the minimum.

Step 2: The unsorted suffix has size $n - k + 1$ . Finding the minimum requires exactly $(n - k + 1) - 1 = n - k$ comparisons.

Step 3: This count is strictly deterministic and does not depend on the initial order of the elements.

Answer: C

Question 10 · Programming, Data Structures and Algorithms MCQ

Suppose Insertion Sort is applied to an array of 5 distinct elements. Let $I$ be the total number of inversions and $C$ be the total number of comparisons. Which of the following combinations of $I$ and $C$ is impossible?

A.
$I = 0, C = 4$
B.
$I = 10, C = 10$
C.
$I = 5, C = 6$
D.
$I = 3, C = 2$

Correct Answer:

Step-by-Step Solution

Key idea: For Insertion Sort, $C = I + (n - 1) - B$ , where $0 \leq B \leq n - 1$ . This implies $I \leq C \leq I + n - 1$ .

Step 1: For $n = 5$ , the formula is $C = I + 4 - B$ , where $0 \leq B \leq 4$ .

Step 2: This means $I \leq C \leq I + 4$ .

Step 3: Check each option:

A: $I = 0, C = 4$ . $0 \leq 4 \leq 4$ . Possible (already sorted array).
B: $I = 10, C = 10$ . $10 \leq 10 \leq 14$ . Possible (reverse sorted array).
C: $I = 5, C = 6$ . $5 \leq 6 \leq 9$ . Possible.
D: $I = 3, C = 2$ . $3 \leq 2$ is false. Impossible.

Answer: D

Common trap: Students may overcount the number of elements that can hit the boundary, or forget that $C \geq I$ .