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

Solution:

 

Case (A): x = 10

Array: [1, 3, 5, 7, 9, 11, 10, 15, 13]

Step-by-step:

  1. Inserting 10:

    • Compared to 11 → swap → [1, 3, 5, 7, 9, 10, 11, 15, 13] → 1 swap

  2. Inserting 15:

    • Already > 11 → no swap

  3. Inserting 13:

    • Compared to 15 → swap → [1, 3, 5, 7, 9, 10, 11, 13, 15] → 1 swap

🔁 Total swaps = 2 ✅
✅ (A) is correct

Case (B): x = 12

Array: [1, 3, 5, 7, 9, 11, 12, 15, 13]

  1. Inserting 12:

    • 12 > 11 → no swap

  2. Inserting 15:

    • Already > 12 → no swap

  3. Inserting 13:

    • Compared to 15 → swap → [1, 3, 5, 7, 9, 11, 12, 13, 15] → 1 swap

🔁 Total swaps = 1 ❌
❌ (B) is incorrect

Case (C): x = 14

Array: [1, 3, 5, 7, 9, 11, 14, 15, 13]

  1. Inserting 14:

    • 14 > 11 → no swap

  2. Inserting 15:

    • Already > 14 → no swap

  3. Inserting 13:

    • Compared to 15 → swap → [1, 3, 5, 7, 9, 11, 14, 13, 15]

    • Compared to 14 → swap → [1, 3, 5, 7, 9, 11, 13, 14, 15] → 2 swaps

🔁 Total swaps = 2 ✅
✅ (C) is correct

Case (D): x = 16

Array: [1, 3, 5, 7, 9, 11, 16, 15, 13]

  1. Inserting 16:

    • 16 > 11 → no swap

  2. Inserting 15:

    • Compared to 16 → swap → [1, 3, 5, 7, 9, 11, 15, 16, 13] → 1 swap

  3. Inserting 13:

    • Compared to 16 → swap

    • Compared to 15 → swap

    • Compared to 11 → no more swaps

    • Final: [1, 3, 5, 7, 9, 11, 13, 15, 16] → 2 swaps

🔁 Total swaps = 3 ❌
❌ (D) is incorrect