Arrange the following items in ascending order using Bubble Sort. What is the intermediate sequence of 37, 54, 21, 85, 68, 12, 9, and 57 after the second pass?

A. 21, 37, 12, 9, 54, 57, 68, 85
B. 37, 21, 54, 68, 12, 9, 57, 85
C. 21, 12, 9, 37, 54, 57, 68, 85
D. 21, 37, 54, 12, 9, 57, 68, 85

Answer :

Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

To determine the intermediate sequence after the second pass, we'll implement the Bubble Sort algorithm step-by-step on the given list: 37, 54, 21, 85, 68, 12, 9, 57.

Initial List:

  1. 37
  2. 54
  3. 21
  4. 85
  5. 68
  6. 12
  7. 9
  8. 57

First Pass:

  • Compare 37 and 54: No swap needed.
  • Compare 54 and 21: Swap.
    • List becomes: 37, 21, 54, 85, 68, 12, 9, 57
  • Compare 54 and 85: No swap needed.
  • Compare 85 and 68: Swap.
    • List becomes: 37, 21, 54, 68, 85, 12, 9, 57
  • Compare 85 and 12: Swap.
    • List becomes: 37, 21, 54, 68, 12, 85, 9, 57
  • Compare 85 and 9: Swap.
    • List becomes: 37, 21, 54, 68, 12, 9, 85, 57
  • Compare 85 and 57: Swap.
    • List becomes: 37, 21, 54, 68, 12, 9, 57, 85

Second Pass:

  • Compare 37 and 21: Swap.
    • List becomes: 21, 37, 54, 68, 12, 9, 57, 85
  • Compare 37 and 54: No swap needed.
  • Compare 54 and 68: No swap needed.
  • Compare 68 and 12: Swap.
    • List becomes: 21, 37, 54, 12, 68, 9, 57, 85
  • Compare 68 and 9: Swap.
    • List becomes: 21, 37, 54, 12, 9, 68, 57, 85
  • Compare 68 and 57: Swap.
    • List becomes: 21, 37, 54, 12, 9, 57, 68, 85
  • Compare 68 and 85: No swap needed.

After the second pass, the intermediate sequence is: 21, 37, 54, 12, 9, 57, 68, 85.

Therefore, the correct multiple-choice option is D. 21, 37, 54, 12, 9, 57, 68, 85.