Question

If a list contains ’n’ number of elements and all the elements are by default sorted in ascending order, how many comparisons will be required during 1^st pass of bubble sort to arrange the list in ascending order?

• A. 0
• B. 1
• C. n - 1
• D. n

Answer 1

The Correct Option is C

The number of comparisons required during the first pass of bubble sort on an already sorted list is n - 1.

Additional Context:

• Bubble Sort Mechanics:
  • Always performs n-1 comparisons in first pass
  • Compares adjacent elements (i vs i+1)
  • No swaps occur in already sorted list
• Optimization Potential:
  • Can terminate early if no swaps occur
  • Still requires full first pass verification
• Example with n=4:
  • Comparisons: [0:1], [1:2], [2:3] → 3 total
  • No swaps needed for [1,2,3,4]
• Time Complexity:
  • Best case (sorted): O(n) comparisons total
  • First pass always requires n-1 comparisons

Correct Answer: (3) n - 1.