Bubble Sort Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bubble Sort on a small array

What is the output of the following C++ code after performing bubble sort on the array?

DSA C++

int arr[] = {5, 3, 8, 4, 2};
int n = 5;
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 2 3 4 5 8

B 5 3 8 4 2

C 8 5 4 3 2

D 2 4 3 5 8

💡 Hint

Bubble sort swaps adjacent elements if they are in the wrong order, pushing the largest to the end each pass.

The bubble sort algorithm compares adjacent elements and swaps them if the left is greater than the right. After all passes, the array is sorted in ascending order.

🧠 Conceptual

intermediate

Number of passes in Bubble Sort

For an array of size n, how many passes does the bubble sort algorithm perform in the worst case?

A n passes

B n + 1 passes

C n - 1 passes

D n / 2 passes

💡 Hint

Each pass places the largest unsorted element at its correct position.

Bubble sort performs n-1 passes because after each pass the largest unsorted element is placed at the end, so after n-1 passes the array is sorted.

🔧 Debug

advanced

Identify the error in this Bubble Sort code

What error will this C++ bubble sort code produce when compiled or run?

DSA C++

int arr[] = {4, 2, 7, 1};
int n = 4;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

A Runtime error: out-of-bounds access

B No error, sorts correctly

C Compilation error: missing semicolon

D Logic error: array remains unsorted

💡 Hint

Check the inner loop boundary conditions carefully.

The inner loop runs j from 0 to n - i - 1, so arr[j + 1] accesses valid indices. The original code had j < n - i which caused out-of-bounds access.

❓ Predict Output

advanced

Output after optimized Bubble Sort with early stop

What is the output of this C++ code after sorting the array with an early stop optimization?

DSA C++

int arr[] = {1, 2, 3, 4, 5};
int n = 5;
bool swapped;
for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
            swapped = true;
        }
    }
    if (!swapped) {
        break;
    }
}
for (int i = 0; i < n; i++) {
    std::cout << arr[i] << " ";
}

A 2 1 3 4 5

B 5 4 3 2 1

C 1 3 2 4 5

D 1 2 3 4 5

💡 Hint

The array is already sorted, so the algorithm should stop early.

Since the array is already sorted, no swaps occur and the loop breaks early, leaving the array unchanged.

🧠 Conceptual

expert

Time complexity of Bubble Sort in best and worst cases

What are the time complexities of bubble sort in the best and worst cases respectively?

A Best: O(log n), Worst: O(n^2)

B Best: O(n), Worst: O(n^2)

C Best: O(n^2), Worst: O(n^2)

D Best: O(n), Worst: O(n log n)

💡 Hint

Consider when the array is already sorted versus completely reversed.

In the best case (already sorted), bubble sort only makes one pass with no swaps, so O(n). In the worst case (reverse sorted), it makes n-1 passes with swaps, so O(n^2).