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

8

1

-9

4

13

(B)

7

1

-9

4

8

13

(C)

-9

1

4

7

8

13

(D)

1

-9

4

7

8

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:

Do each pass left to right, swapping neighbours when the left one is bigger, and write the list after each pass.

Answer 1

The Correct Option is C

Step 1: Understanding the Concept:
Bubble sort compares each pair of neighbouring elements from left to right. If the left one is bigger, it swaps them. After one full pass the largest element of the unsorted part has moved to its place at the right end. We repeat passes until the list is sorted.

Step 2: Key Formula or Approach:
For 6 elements we make at most 5 passes. We write the list after each pass and then match it with the given lists (A) to (D).

Step 3: Pass 1:
Start with 8, 7, 13, 1, -9, 4. Compare 8 and 7: swap, giving 7, 8, 13, 1, -9, 4. Compare 8 and 13: no swap. Compare 13 and 1: swap, giving 7, 8, 1, 13, -9, 4. Compare 13 and -9: swap, giving 7, 8, 1, -9, 13, 4. Compare 13 and 4: swap, giving 7, 8, 1, -9, 4, 13. This list is (A).

Step 4: Pass 2:
Start with 7, 8, 1, -9, 4, 13. Compare 7 and 8: no swap. Compare 8 and 1: swap, giving 7, 1, 8, -9, 4, 13. Compare 8 and -9: swap, giving 7, 1, -9, 8, 4, 13. Compare 8 and 4: swap, giving 7, 1, -9, 4, 8, 13. This list is (B).

Step 5: Pass 3:
Start with 7, 1, -9, 4, 8, 13. Compare 7 and 1: swap, giving 1, 7, -9, 4, 8, 13. Compare 7 and -9: swap, giving 1, -9, 7, 4, 8, 13. Compare 7 and 4: swap, giving 1, -9, 4, 7, 8, 13. Later pairs are in order. This list is (D).

Step 6: Pass 4:
Start with 1, -9, 4, 7, 8, 13. Compare 1 and -9: swap, giving -9, 1, 4, 7, 8, 13. All other pairs are in order. This list is (C), and the list is now sorted.

Step 7: Match the sequence:
The order of the outputs is (A), (B), (D), (C). This is option 3.

Step 8: Why the other options are wrong:
Option 1 starts with (B), but the first pass gives (A). Option 2 puts (C) last-but-one wrongly, as (C) is the sorted list and (D) must come before it. Option 4 starts with (C), the fully sorted list, which cannot be the first pass.

Final Answer:
The passes of bubble sort give (A), (B), (D), (C), which is option 3. \[ \boxed{3} \]