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.