QUESTION 24 Which of the below given statement(s) is/are correct about Bubble sort?

Statement (I) is correct: bubble sort can detect if a list is already sorted by using a flag that tracks whether any swaps occurred in a pass—if no swaps occur, the list is sorted. Statement (III) is correct: with an optimization flag, best-case complexity is O(n) when the input is already sorted. Statement (II) is incorrect: bubble sort can generate either ascending or descending order depending on the comparison operator used; it is not restricted to ascending order only.

Step-by-step Derivation:
Analyze each statement:

Statement I: Bubble sort can detect if input is already sorted

• TRUE. Optimized bubble sort uses a flag (e.g., swapped) initialized to false at the start of each pass.
• If no elements are swapped during a complete pass, the flag remains false, indicating the list is already sorted.
• Example: For already-sorted list [1,2,3,4], the first pass completes with no swaps → algorithm terminates.

Statement II: Bubble sort always generates ascending order

• FALSE. Bubble sort generates whatever order the comparison specifies.
• If we use if (arr[i] > arr[i+1]) we get ascending order.
• If we use if (arr[i] < arr[i+1]) we get descending order.
• The algorithm itself is agnostic to direction; the programmer chooses via the comparison.

Statement III: Best case O(n) with extra flag

• TRUE. With the flag optimization:
  • Best case (already sorted): Single pass through n elements, O(n) comparisons, no swaps, flag stays false → exit.
  • Without flag: Still O(n²) even if sorted (no early termination).
  • So the flag enables O(n) best case.

Conclusion: Statements (I) and (III) are correct → Answer is A.