Bubble Sort: Algorithm, Dry Run, Code & Complexity Explained

What is Bubble Sort?

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. With each pass, the largest unsorted element bubbles up to its correct position at the end of the array.

Algorithm Steps

1. Start from index 0, compare arr[j] and arr[j+1]
2. If arr[j] > arr[j+1], swap them
3. After one full pass, the largest element reaches its final position
4. Repeat for n-1 passes, reducing inner range by 1 each time

Code Implementation

🐍 Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):           # n-1 passes
        for j in range(n - i - 1):   # shrink inner range each pass
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Optimized version
def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

☕ Java

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {          // n-1 passes
            for (int j = 0; j < n - i - 1; j++) {  // shrink each pass
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // Optimized version
    public static void bubbleSortOptimized(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean 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;  // already sorted
        }
    }
}

⚙️ C++

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

void bubbleSort(vector& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {          // n-1 passes
        for (int j = 0; j < n - i - 1; j++) {  // shrink each pass
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

// Optimized version
void bubbleSortOptimized(vector& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // already sorted
    }
}

🟡 JavaScript

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {          // n-1 passes
        for (let j = 0; j < n - i - 1; j++) {  // shrink each pass
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
            }
        }
    }
    return arr;
}

// Optimized version
function bubbleSortOptimized(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break;  // already sorted
    }
    return arr;
}

// Test
console.log(bubbleSort([20, 15, 10, 35, 30, 2]));
// Output: [2, 10, 15, 20, 30, 35]

Dry Run — arr = [20, 15, 10, 35, 30, 2]

Comparisons Summary

Time & Space Complexity

Is Bubble Sort Stable?

✅ Yes. We only swap when arr[j] > arr[j+1] (strict greater than). Equal elements are never swapped, preserving their relative order.