Bubble Sort Algorithm in DSA C++

Mental Model

Bubble sort repeatedly swaps adjacent items if they are in the wrong order, pushing the largest unsorted item to the end each pass.

Analogy: Imagine bubbles rising in water: the biggest bubble moves up to the surface by swapping places with smaller bubbles below it.

Index: 0   1   2   3   4
Array: [5]->[3]->[8]->[4]->[2]
          ↑
        compare adjacent pairs

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Sort the array in ascending order using bubble sort

Step 1: Compare 5 and 3, swap because 5 > 3

[3] -> [5] -> [8] -> [4] -> [2]

Why: We want smaller numbers to move left, so swap if left is bigger

Step 2: Compare 5 and 8, no swap because 5 < 8

[3] -> [5] -> [8] -> [4] -> [2]

Why: No swap needed if left is smaller

Step 3: Compare 8 and 4, swap because 8 > 4

[3] -> [5] -> [4] -> [8] -> [2]

Why: Push bigger number right

Step 4: Compare 8 and 2, swap because 8 > 2

[3] -> [5] -> [4] -> [2] -> [8]

Why: Largest number bubbles to the end

Step 5: Start second pass: compare 3 and 5, no swap

[3] -> [5] -> [4] -> [2] -> [8]

Why: Check next pair

Step 6: Compare 5 and 4, swap because 5 > 4

[3] -> [4] -> [5] -> [2] -> [8]

Why: Smaller number moves left

Step 7: Compare 5 and 2, swap because 5 > 2

[3] -> [4] -> [2] -> [5] -> [8]

Why: Push bigger number right

Step 8: Start third pass: compare 3 and 4, no swap

[3] -> [4] -> [2] -> [5] -> [8]

Why: Check next pair

Step 9: Compare 4 and 2, swap because 4 > 2

[3] -> [2] -> [4] -> [5] -> [8]

Why: Smaller number moves left

Step 10: Start fourth pass: compare 3 and 2, swap because 3 > 2

[2] -> [3] -> [4] -> [5] -> [8]

Why: Final swap to order smallest numbers

Result:

[2] -> [3] -> [4] -> [5] -> [8]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        // Each pass pushes the largest unsorted element to the end
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap if left element is bigger
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {5, 3, 8, 4, 2};
    bubbleSort(arr);
    printArray(arr);
    return 0;
}

for (int i = 0; i < n - 1; i++) {

repeat passes to bubble largest unsorted element to the end

for (int j = 0; j < n - i - 1; j++) {

compare adjacent pairs up to last sorted element

if (arr[j] > arr[j + 1]) {

check if left element is bigger to decide swap

swap arr[j] and arr[j + 1]

swap to move bigger element right

Output

2 3 4 5 8 

Complexity Analysis

Time: O(n^2) because in worst case we compare and swap pairs for each element in nested loops

Space: O(1) because sorting is done in place without extra storage

vs Alternative: Compared to more advanced sorts like quicksort (O(n log n)), bubble sort is slower but simpler to understand and implement

Edge Cases

empty array

function completes immediately without errors

DSA C++

for (int i = 0; i < n - 1; i++) {

array with one element

no swaps needed, array remains same

DSA C++

for (int i = 0; i < n - 1; i++) {

array already sorted

no swaps occur, but algorithm still runs all passes

DSA C++

if (arr[j] > arr[j + 1]) {

When to Use This Pattern

When you see a problem asking to sort by repeatedly swapping neighbors, think bubble sort because it pushes largest elements to the end step by step.

Common Mistakes

Mistake: Not reducing inner loop range by i, causing unnecessary comparisons
Fix: Use 'n - i - 1' as inner loop limit to avoid checking already sorted elements

Mistake: Swapping elements even when they are in correct order
Fix: Only swap when left element is greater than right element

Summary

Bubble sort sorts an array by repeatedly swapping adjacent elements if they are in the wrong order.

Use bubble sort for small or nearly sorted arrays when simplicity is more important than speed.

The key insight is that each pass moves the largest unsorted element to its correct position at the end.

Practice

1. What is the main idea behind the Bubble Sort algorithm?

easy

A. Divide the array into halves and sort each half separately

B. Repeatedly swap adjacent elements if they are in the wrong order

C. Select the smallest element and move it to the beginning

D. Insert each element into its correct position in a sorted part

Solution

1. Step 1: Understand Bubble Sort process

   Bubble Sort compares adjacent elements and swaps them if they are out of order.

2. Step 2: Identify the correct description

   This swapping of neighbors repeats until the whole list is sorted.

3. Final Answer:

   Repeatedly swap adjacent elements if they are in the wrong order -> Option B

4. Quick Check:

   Bubble Sort = Swap neighbors repeatedly [OK]

Hint: Bubble Sort swaps neighbors repeatedly until sorted [OK]

Common Mistakes:

• Confusing Bubble Sort with Selection Sort
• Thinking it divides the array like Merge Sort
• Assuming it inserts elements like Insertion Sort

2. Which of the following is the correct syntax for the inner loop of Bubble Sort in C++ to compare adjacent elements in an array arr of size n?

easy

A. for (int j = 0; j < n - i - 1; j++)

B. for (int j = 0; j < n; j++)

C. for (int j = 1; j < n - i; j++)

D. for (int j = 0; j <= n - i; j++)

Solution

1. Step 1: Understand inner loop range

   The inner loop runs from 0 to n - i - 1 because after each pass, the last i elements are sorted.

2. Step 2: Check each option

   for (int j = 0; j < n - i - 1; j++) correctly uses j < n - i - 1 to avoid out-of-bound and unnecessary comparisons.

3. Final Answer:

   for (int j = 0; j < n - i - 1; j++) -> Option A

4. Quick Check:

   Inner loop limit = n - i - 1 [OK]

Hint: Inner loop stops before sorted elements at end [OK]

Common Mistakes:

• Using j < n instead of j < n - i - 1
• Starting j from 1 instead of 0
• Using <= instead of < causing out-of-bound

3. What will be the output of the following C++ code snippet?

int arr[] = {5, 3, 8, 4};
int n = 4;
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] << " ";
}

medium

A. 3 5 4 8

B. 5 3 4 8

C. 8 5 4 3

D. 3 4 5 8

Solution

1. Step 1: Trace first pass of Bubble Sort

   Compare pairs: (5,3) swap -> {3,5,8,4}, (5,8) no swap, (8,4) swap -> {3,5,4,8}

2. Step 2: Trace second pass and final array

   Next pass: (3,5) no swap, (5,4) swap -> {3,4,5,8}, last pass no swaps needed.

3. Final Answer:

   3 4 5 8 -> Option D

4. Quick Check:

   Sorted array = 3 4 5 8 [OK]

Hint: Bubble Sort pushes largest to end each pass [OK]

Common Mistakes:

• Not swapping correctly on first pass
• Confusing order of swaps
• Printing unsorted array

4. Identify the error in the following Bubble Sort code snippet and select the correct fix:

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

medium

A. Add a swap flag to optimize and stop early if sorted

B. Change outer loop to i < n - 1 to reduce unnecessary passes

C. Change inner loop to j < n - i - 1 to avoid out-of-bound access

D. No error, code is correct

Solution

1. Step 1: Analyze inner loop condition

   Inner loop uses j < n - i, but accesses arr[j + 1], which causes out-of-bound when j = n - i - 1.

2. Step 2: Correct inner loop limit

   Changing to j < n - i - 1 prevents accessing arr[n], fixing runtime error.

3. Final Answer:

   Change inner loop to j < n - i - 1 to avoid out-of-bound access -> Option C

4. Quick Check:

   Inner loop limit fixes out-of-bound [OK]

Hint: Inner loop must stop before last compared index [OK]

Common Mistakes:

• Ignoring out-of-bound access
• Changing outer loop only
• Assuming code is correct without checking array access

5. Given an array arr = {7, 2, 9, 4, 3}, how many total swaps will Bubble Sort perform to sort it in ascending order?

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Trace swaps in each pass

   Pass 1: (7,2) swap, (7,9) no, (9,4) swap, (9,3) swap -> 3 swaps
   Array now: {2,7,4,3,9}

2. Step 2: Continue tracing swaps

   Pass 2: (2,7) no, (7,4) swap, (7,3) swap -> 2 swaps
   Array now: {2,4,3,7,9}
   Pass 3: (2,4) no, (4,3) swap -> 1 swap
   Array now: {2,3,4,7,9}
   Pass 4: no swaps

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Total swaps counted = 6 [OK]

Hint: Count swaps each pass until no swaps left [OK]

Common Mistakes:

• Counting comparisons instead of swaps
• Stopping early without counting all passes
• Miscounting swaps in passes