Question 3 of 6advanced🔍 AnalyzeLong Answer4 marks

Consider the following lists: List 1: 2 3 5 7 11 List 2: 11 7 5 3 2. If the lists are sorted using Insertion sort then which of the lists List1 or List 2 will make the minimum number of comparisons? Justify using diagrammatic representation.

Correct Answer

List 1 will make the minimum number of comparisons when sorted using Insertion sort.

Justification with Diagrammatic Representation:

List 1: 2 3 5 7 11 (Already sorted in ascending order)

Pass 1: Element 3 is compared with 2. Since 3 > 2, no shifting needed. Comparisons = 1

Pass 2: Element 5 is compared with 3. Since 5 > 3, no shifting needed. Comparisons = 1

Pass 3: Element 7 is compared with 5. Since 7 > 5, no shifting needed. Comparisons = 1

Pass 4: Element 11 is compared with 7. Since 11 > 7, no shifting needed. Comparisons = 1

Total comparisons for List 1 = 1 + 1 + 1 + 1 = 4

List 2: 11 7 5 3 2 (Sorted in descending order)

Pass 1: Element 7 is compared with 11. Since 7 < 11, shifting required. Comparisons = 1

Pass 2: Element 5 is compared with 11, then with 7. Shifting required. Comparisons = 2

Pass 3: Element 3 is compared with 11, 7, then 5. Shifting required. Comparisons = 3

Pass 4: Element 2 is compared with 11, 7, 5, then 3. Shifting required. Comparisons = 4

Total comparisons for List 2 = 1 + 2 + 3 + 4 = 10

Conclusion: List 1 requires only 4 comparisons whereas List 2 requires 10 comparisons. Hence, List 1 makes minimum comparisons because it is already sorted in ascending order, so each element finds its correct position with just one comparison.

Exercise: EXERCISE | Q: 3 | (Page Page 13)
For More Understanding

Explanation

In Insertion sort, elements from the unsorted portion are inserted into the sorted portion at their appropriate position. When a list is already sorted (like List 1), each new element only needs one comparison with the last element of the sorted portion to confirm it's in the correct position. However, when a list is in reverse order (like List 2), each element must be compared with all previous elements and shifted to the beginning, resulting in maximum comparisons.

Solution Steps

  1. Step 1: Analyze List 1 (already sorted ascending) - each element requires only 1 comparison

  2. Step 2: Calculate total comparisons for List 1: 1+1+1+1 = 4

  3. Step 3: Analyze List 2 (sorted descending) - each element requires comparisons with all previous elements

  4. Step 4: Calculate total comparisons for List 2: 1+2+3+4 = 10

  5. Step 5: Conclude that List 1 makes minimum comparisons (4 < 10)

PreviousNext