Question 2 of 6intermediate🔍 AnalyzeShort Answer3 marks

Identify the number of swaps required for sorting the following list using selection sort and bubble sort and identify which is the better sorting technique with respect to the number of comparisons. List 1: 63 42 21 9

Correct Answer

Selection Sort Swaps: 2 swaps

Bubble Sort Swaps: 6 swaps

Better Technique: Both techniques require the same number of comparisons (6 comparisons each) for this list. However, Selection Sort is considered better overall as it requires significantly fewer swaps (2) compared to Bubble Sort (6).

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

Explanation

The textbook explains that Bubble sort works by repeatedly comparing adjacent elements and swapping them if unordered, making n-1 passes for n elements. For Selection sort, the minimum element is identified and placed at the correct position. For the given list [63, 42, 21, 9], Bubble sort requires 3+2+1=6 swaps across all passes, while Selection sort only requires 2 swaps (swapping 63 with 9, then 42 with 21). Both require 6 comparisons total, but Selection sort is more efficient in terms of swap operations.

Solution Steps

  1. Step 1: Bubble Sort Analysis - Pass 1: Compare (63,42)→swap, (63,21)→swap, (63,9)→swap = 3 swaps. Pass 2: Compare (42,21)→swap, (42,9)→swap = 2 swaps. Pass 3: Compare (21,9)→swap = 1 swap. Total = 6 swaps.

  2. Step 2: Selection Sort Analysis - Pass 1: Find minimum (9), swap with 63 → [9,42,21,63] = 1 swap. Pass 2: Find minimum in remaining (21), swap with 42 → [9,21,42,63] = 1 swap. Pass 3: Minimum already in place = 0 swaps. Total = 2 swaps.

  3. Step 3: Comparison Count - Both require 3+2+1=6 comparisons. Selection sort is better due to fewer swaps.

PreviousNext