Question

After two complete passes of Bubble Sort on the array [7, 2, 9, 4], what will the new order be?
A. 7
B. 2
C. 4
D. 9
Choose the correct answer from the options given below:

• A. B, C, A, D
• B. A, B, C, D
• C. B, A, D, C
• D. B, A, C, D

Hint:

At the end of the $k$-th pass of Bubble Sort, the $k$ largest elements are guaranteed to be in their final sorted positions at the end of the array!
Here, after 2 passes, the last two elements must be 7 and 9 (represented by A and D).

Answer 1

The Correct Option is A

Step 1: Understanding the Question:
The question asks to find the order of the array elements [7, 2, 9, 4] after executing exactly two complete passes of the Bubble Sort algorithm in ascending order.

Step 2: Bubble Sort Algorithm:
- Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order.
- In each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.

Step 3: Step-by-Step Trace of the Passes:
- Initial Array: [7, 2, 9, 4]
- Pass 1:
- Compare indices 0 and 1 (7 and 2): $7 > 2$ is True. Swap them.
Array becomes: [2, 7, 9, 4]
- Compare indices 1 and 2 (7 and 9): $7 > 9$ is False. No swap.
Array remains: [2, 7, 9, 4]
- Compare indices 2 and 3 (9 and 4): $9 > 4$ is True. Swap them.
Array becomes: [2, 7, 4, 9]
- End of Pass 1: The largest element 9 is placed at the final index. It is now in its sorted position.
- Pass 2:
- We only need to sort the remaining unsorted elements [2, 7, 4].
- Compare indices 0 and 1 (2 and 7): $2 > 7$ is False. No swap.
Array remains: [2, 7, 4, 9]
- Compare indices 1 and 2 (7 and 4): $7 > 4$ is True. Swap them.
Array becomes: [2, 4, 7, 9]
- End of Pass 2: The second largest element 7 is placed in its correct position.
- The array order after two passes is: [2, 4, 7, 9].
- Mapping elements to the given variable labels:
- 2 is labeled as B.
- 4 is labeled as C.
- 7 is labeled as A.
- 9 is labeled as D.
- This gives the sequence: B, C, A, D.

Step 4: Final Answer:
The state of the array after two passes of Bubble Sort is represented by B, C, A, D.
Hence, option (A) is the correct choice.