Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

1. What is Bubble Sort?

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Largest element “bubbles” to the end after every pass.

2. Dry Run Bubble Sort.

Input: 96 43 74 72 46
Output: 43 46 72 74 96

arr[0] = 96
arr[1] = 43
arr[2] = 74
arr[3] = 72
arr[4] = 46

Pass 1:

• Comparing 96 > 43, If TRUE Swaps 96 & 43, Result: 43 96 74 72 46

• Comparing 96 > 74, If TRUE Swaps 96 & 74, Result: 43 74 96 72 46

• Comparing 96 > 72, If TRUE Swaps 96 & 72, Result: 43 74 72 96 46

• Comparing 96 > 46, If TRUE Swaps 96 & 46, Result: 43 74 72 46 96

Pass 2:

• Comparing 43 > 74, If FALSE No Swaps, Result: 43 74 72 46 96

• Comparing 74 > 72, If TRUE Swaps 74 & 72, Result: 43 72 74 46 96

• Comparing 74 > 46, If TRUE Swaps 74 & 46, Result: 43 72 46 74 96

Pass 3:

• Comparing 43 > 72, If FALSE No Swaps, Result: 43 72 46 74 96

• Comparing 72 > 46, If TRUE Swaps 72 & 46, Result: 43 46 72 74 96

Pass 4:

• Comparing 43 > 46, If FALSE No Swaps, Result: 43 46 72 74 96

3. Code Implementation

Example:

#include <iostream>
 
using namespace std;
 
void bubbleSortAscWorst(int arr[], int n)
{
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j <= i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}
 
void bubbleSortAscBest(int arr[], int n)
{
    for (int i = n - 2; i >= 0; i--)
    {
        bool swapped = false;
        for (int j = 0; j <= i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
 
        if (!swapped)
            break;
    }
}
 
void printArray(int arr[], int n, string msg = "")
{
    cout << msg << endl;
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main()
{
 
    int arr[] = {5, 16, 4, 71, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    printArray(arr, n, "Original array:");
 
    bubbleSortAscWorst(arr, n);
    printArray(arr, n, "Sorted array(asc) worst case:");
 
    bubbleSortAscBest(arr, n);
    printArray(arr, n, "Sorted array(asc) best case:");
 
    return 0;
}  

Output:

Original array:
5 16 4 71 2 11
Sorted array(asc) worst case:
2 4 5 11 16 71
Sorted array(asc) best case:
2 4 5 11 16 71

4. What is the time complexity of Bubble Sort?

• Best Case: O(n)
• Worst Case: O(n2)
• Average Case: O(n2)

5. What is the space complexity?

6. Is Bubble Sort stable?

Yes, Equal elements maintain their relative order.

Example:

2a 2b 1
 
After sorting:
1 2a 2b

7. Is Bubble Sort adaptive?

Yes (optimized version).

If no swaps occur in a pass:

• array is already sorted,
• algorithm stops early.

8. Why is Bubble Sort called Bubble Sort?

Because larger elements “bubble up” to the end after each pass.

9. How many passes are required in Bubble Sort?

Maximum: n - 1

10. How many comparisons occur in Bubble Sort?

Total comparisons: n(n - 1) / 2 in worst case.

11. Can Bubble Sort be implemented recursively?

Yes, Bubble Sort can be implemented recursively.

• largest element moves to end,
• recursively sort remaining array.

12. Difference between Bubble Sort and Selection Sort?

| Feature  | Bubble Sort       | Selection Sort |
| -------- | ----------------- | -------------- |
| Swaps    | Many              | Few            |
| Stable   | Yes               | No             |
| Adaptive | Yes               | No             |
| Method   | Adjacent swapping | Select minimum |