What is the expected output of the optimized bubble sort algorithm if the array is already sorted?

• A. All items are swapped
• B. It will loop through the array multiple times
• C. It will complete in one pass without swaps
• D. It will throw an error

Answer: (C)

The optimized bubble sort algorithm is designed to improve efficiency when the input array is already sorted. In this case, the key feature of the algorithm comes into play: it includes a flag that indicates whether any swaps have been made during a pass through the array.

When the array is already sorted, the algorithm makes a single pass to compare adjacent elements. Since no swaps are necessary (because all elements are in the correct order), the flag remains unchanged from its initial state, indicating that no swaps were performed. As a result, the algorithm will complete the sorting process in that one pass, confirming that the array is sorted, and it can terminate early without making additional passes.

This efficiency is what distinguishes the optimized version from a standard bubble sort, which would continue looping through the array multiple times even if it is already sorted. Therefore, the expected output for an already sorted array is indeed that it will complete in one pass without any swaps.