Question

Consider the following numList: 

8

7

13

1

-9

4

Sequence the following output obtained after each pass of comparison using bubble sort. 

(A) \(7\quad 8\quad 1\quad -9\quad 4\quad 13\) 
(B) \(7\quad 1\quad -9\quad 4\quad 8\quad 13\) 
(C) \(-9\quad 1\quad 4\quad 7\quad 8\quad 13\) 
(D) \(1\quad -9\quad 4\quad 7\quad 8\quad 13\) 

Choose the correct answer from the options given below: 
 

• A. (B), (D), (C), (A)
• B. (A), (B), (C), (D)
• C. (A), (B), (D), (C)
• D. (C), (B), (D), (A)

Hint:

To trace Bubble Sort quickly, notice which element settles at the end after each pass:
Pass 1 fixes 13 at the end.
Pass 2 fixes 8 at the second-to-last position.
Pass 3 fixes 7 at its spot, and so on.

Answer 1

The Correct Option is C

Concept:
Bubble sort iteratively compares adjacent elements and swaps them if the left element exceeds the right element.
In each successive pass, the largest remaining unsorted value bubbles up to its final position at the end of the array.

Step 1: Tracing Pass 1:
Initial list: \([8, 7, 13, 1, -9, 4]\)
- Compare 8 and 7 \(\rightarrow 8 > 7\), swap: \([7, 8, 13, 1, -9, 4]\)
- Compare 8 and 13 \(\rightarrow 8 \le 13\), no swap: \([7, 8, 13, 1, -9, 4]\)
- Compare 13 and 1 \(\rightarrow 13 > 1\), swap: \([7, 8, 1, 13, -9, 4]\)
- Compare 13 and \(-9 \rightarrow 13 > -9\), swap: \([7, 8, 1, -9, 13, 4]\)
- Compare 13 and 4 \(\rightarrow 13 > 4\), swap: \([7, 8, 1, -9, 4, 13]\)
Result of Pass 1: \([7, 8, 1, -9, 4, 13]\), which matches (A).

Step 2: Tracing Pass 2:
Current list: \([7, 8, 1, -9, 4, 13]\)
- Compare 7 and 8 \(\rightarrow\) no swap
- Compare 8 and 1 \(\rightarrow\) swap: \([7, 1, 8, -9, 4, 13]\)
- Compare 8 and \(-9 \rightarrow\) swap: \([7, 1, -9, 8, 4, 13]\)
- Compare 8 and 4 \(\rightarrow\) swap: \([7, 1, -9, 4, 8, 13]\)
Result of Pass 2: \([7, 1, -9, 4, 8, 13]\), which matches (B).

Step 3: Tracing Pass 3:
Current list: \([7, 1, -9, 4, 8, 13]\)
- Compare 7 and 1 \(\rightarrow\) swap: \([1, 7, -9, 4, 8, 13]\)
- Compare 7 and \(-9 \rightarrow\) swap: \([1, -9, 7, 4, 8, 13]\)
- Compare 7 and 4 \(\rightarrow\) swap: \([1, -9, 4, 7, 8, 13]\)
Result of Pass 3: \([1, -9, 4, 7, 8, 13]\), which matches (D).

Step 4: Tracing Pass 4:
Current list: \([1, -9, 4, 7, 8, 13]\)
- Compare 1 and \(-9 \rightarrow\) swap: \([-9, 1, 4, 7, 8, 13]\)
Result of Pass 4: \([-9, 1, 4, 7, 8, 13]\), which matches (C).
Final Answer:
The chronological order of passes is (A), (B), (D), (C). Therefore, option (C) is correct.