Virtual Labs

1. What is the time complexity of the regular, unoptimized Bubble Sort algorithm in the best case, when the input array is already sorted?

a: O(N) Explanation

Explanation

b: O(N^2) Explanation

Explanation

c: O(N log N) Explanation

Explanation

d: O(1) Explanation

Explanation

2. Consider the following array:
A = [-10, 100, 1, 0, 9, 1*]
Here, '*' distinguishes the two occurrences of 1 so that their original order can be tracked. What will be the final output of Bubble Sort for this array, assuming ascending order?

a: [-10, 0, 1, 1*, 9, 100] Explanation

Explanation

b: [-10, 0, 1*, 1, 9, 100] Explanation

Explanation

c: [100, 9, 1, 1*, 0, -10] Explanation

Explanation

d: [100, 9, 1*, 1, 0, -10] Explanation

Explanation

3. What is the time complexity of Bubble Sort in the worst case?

a: O(N) Explanation

Explanation

b: O(N^2) Explanation

Explanation

c: O(N log N) Explanation

Explanation

d: O(N!) Explanation

Explanation

4. What is the auxiliary space complexity of the Bubble Sort algorithm when sorting the array in place?

a: O(N) Explanation

Explanation

b: O(2^N) Explanation

Explanation

c: O(1) Explanation

Explanation

d: O(N^2) Explanation

Explanation

5. Which characteristic of Bubble Sort explains why equal elements can retain their original relative order?

a: It always moves equal elements to the beginning. Explanation

Explanation

b: It swaps equal adjacent elements on every comparison. Explanation

Explanation

c: It removes duplicate elements before sorting. Explanation

Explanation

d: It does not swap adjacent elements when they are equal. Explanation

Explanation

6. Which statement best describes the difference between regular and optimized Bubble Sort?

a: The optimized version can stop early when a complete pass makes no swaps. Explanation

Explanation

b: The optimized version changes Bubble Sort into Merge Sort. Explanation

Explanation

c: The optimized version requires an additional array for every pass. Explanation

Explanation

d: The optimized version never performs swaps. Explanation

Explanation

7. In an ascending Bubble Sort, approximately how many comparisons are performed over all passes in the worst case for an array of N elements?

a: N Explanation

Explanation

b: N(N - 1) / 2 Explanation

Explanation

c: 2N Explanation

Explanation

d: N! Explanation

Explanation

8. Why does Bubble Sort have O(1) auxiliary space complexity when implemented in place?

a: Because it creates a copy of the entire array only once. Explanation

Explanation

b: Because it uses a recursive call for every element. Explanation

Explanation

c: Because it only needs a fixed number of temporary variables for operations such as swapping. Explanation

Explanation

d: Because it stores every intermediate array state. Explanation

Explanation

9. Which input arrangement generally causes the largest number of swaps in standard ascending Bubble Sort?

a: An already sorted array Explanation

Explanation

b: An array with all equal elements Explanation

Explanation

c: An array in reverse-sorted order Explanation

Explanation

d: An array containing a single element Explanation

Explanation