Bubble Sort — Why 50K Items Took 12 Minutes in Production

public class BubbleSortBasic {

    public static void main(String[] args) {

        // Our unsorted list of exam scores
        int[] scores = {5, 3, 8, 1, 4};

        int numberOfScores = scores.length;

        System.out.println("Before sorting:");
        printArray(scores);

        // Outer loop: controls how many passes we make.
        // After each pass, the largest unsorted element is in its final spot,
        // so we shrink the range by 1 each time (hence numberOfScores - pass - 1).
        for (int pass = 0; pass < numberOfScores - 1; pass++) {

            System.out.println("\n--- Pass " + (pass + 1) + " ---");

            // Inner loop: walks through neighboring pairs in the unsorted portion.
            // We stop earlier each pass because the tail is already sorted.
            for (int index = 0; index < numberOfScores - pass - 1; index++) {

                // Compare the current element with the one immediately to its right
                if (scores[index] > scores[index + 1]) {

                    // They're in the wrong order — swap them using a temp variable
                    int temp = scores[index];
                    scores[index] = scores[index + 1];
                    scores[index + 1] = temp;

                    System.out.println("  Swapped index " + index + " and " + (index + 1)
                            + " → " + java.util.Arrays.toString(scores));
                } else {
                    System.out.println("  No swap at index " + index
                            + " → " + java.util.Arrays.toString(scores));
                }
            }
        }

        System.out.println("\nAfter sorting:");
        printArray(scores);
    }

    // Helper method to print the array in a readable format
    static void printArray(int[] array) {
        System.out.println(java.util.Arrays.toString(array));
    }
}

Initial: [5, 3, 8, 1, 4]

Pass 1: [3, 5, 1, 4, 8]   <- 8 is now sorted at end
Pass 2: [3, 1, 4, 5, 8]   <- 5 is sorted
Pass 3: [1, 3, 4, 5, 8]   <- 4 is sorted
Pass 4: [1, 3, 4, 5, 8]   <- no swap, done early

public class BubbleSortOptimized {

    public static void main(String[] args) {

        // Test 1: A random unsorted list of temperatures
        int[] temperatures = {34, 12, 45, 7, 29};
        System.out.println("Test 1 — Unsorted input:");
        System.out.println("Before: " + java.util.Arrays.toString(temperatures));
        optimizedBubbleSort(temperatures);
        System.out.println("After:  " + java.util.Arrays.toString(temperatures));

        System.out.println();

        // Test 2: An already-sorted array — watch how few passes it takes
        int[] alreadySorted = {1, 2, 3, 4, 5};
        System.out.println("Test 2 — Already sorted input:");
        System.out.println("Before: " + java.util.Arrays.toString(alreadySorted));
        optimizedBubbleSort(alreadySorted);
        System.out.println("After:  " + java.util.Arrays.toString(alreadySorted));
    }

    static void optimizedBubbleSort(int[] array) {
        int size = array.length;
        int passCount = 0;

        for (int pass = 0; pass < size - 1; pass++) {

            // Assume no swaps have happened this pass
            boolean swappedThisPass = false;
            passCount++;

            for (int index = 0; index < size - pass - 1; index++) {

                if (array[index] > array[index + 1]) {

                    // Swap the two neighboring elements
                    int temp = array[index];
                    array[index] = array[index + 1];
                    array[index + 1] = temp;

                    // At least one swap happened, so the array wasn't fully sorted yet
                    swappedThisPass = true;
                }
            }

            // If we completed a full pass with zero swaps, the array is sorted.
            // No point continuing — exit early.
            if (!swappedThisPass) {
                System.out.println("Early exit after " + passCount + " pass(es) — array is sorted!");
                return;
            }
        }

        System.out.println("Completed in " + passCount + " pass(es).");
    }
}

public class BubbleSortComplexityDemo {

    // We'll count actual comparisons to verify the O(n²) claim ourselves
    static int comparisonCount = 0;

    public static void main(String[] args) {

        System.out.println("Demonstrating how comparison count scales with input size:\n");
        System.out.printf("%-15s %-20s %-20s%n", "Array Size (n)", "Comparisons Made", "n² (theoretical)");
        System.out.println("-".repeat(55));

        // Test with different array sizes to show the quadratic growth
        int[] testSizes = {5, 10, 20, 50, 100};

        for (int size : testSizes) {

            // Build a worst-case (reverse-sorted) array of the given size
            int[] reverseArray = buildReverseSortedArray(size);

            comparisonCount = 0; // Reset counter before each sort
            bubbleSortWithCounter(reverseArray);

            System.out.printf("%-15d %-20d %-20d%n",
                    size, comparisonCount, (long) size * size);
        }

        System.out.println("\nNotice: actual comparisons ≈ n²/2, which is still O(n²).");
    }

    static void bubbleSortWithCounter(int[] array) {
        int size = array.length;

        for (int pass = 0; pass < size - 1; pass++) {
            boolean swappedThisPass = false;

            for (int index = 0; index < size - pass - 1; index++) {
                comparisonCount++; // Count every comparison we make

                if (array[index] > array[index + 1]) {
                    int temp = array[index];
                    array[index] = array[index + 1];
                    array[index + 1] = temp;
                    swappedThisPass = true;
                }
            }

            if (!swappedThisPass) break;
        }
    }

    // Builds an array [n, n-1, n-2, ..., 2, 1] — the worst case for Bubble Sort
    static int[] buildReverseSortedArray(int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = size - i; // Fills from largest to smallest
        }
        return array;
    }
}

public class BubbleSortStrings {

    public static void main(String[] args) {

        // A list of student names that need to be sorted alphabetically
        String[] studentNames = {"Zara", "Ahmed", "Maya", "Liam", "Sofia", "Ben"};

        System.out.println("Student names before sorting:");
        printNames(studentNames);

        alphabeticalBubbleSort(studentNames);

        System.out.println("\nStudent names after sorting:");
        printNames(studentNames);
    }

    static void alphabeticalBubbleSort(String[] names) {
        int size = names.length;

        for (int pass = 0; pass < size - 1; pass++) {
            boolean swappedThisPass = false;

            for (int index = 0; index < size - pass - 1; index++) {

                // compareTo() returns a positive number when names[index]
                // comes AFTER names[index+1] alphabetically.
                // That means they're in the wrong order — swap them.
                if (names[index].compareTo(names[index + 1]) > 0) {

                    String temp = names[index];
                    names[index] = names[index + 1];
                    names[index + 1] = temp;

                    swappedThisPass = true;
                }
            }

            if (!swappedThisPass) {
                break; // Early exit if already sorted
            }
        }
    }

    static void printNames(String[] names) {
        for (String name : names) {
            System.out.print(name + "  ");
        }
        System.out.println();
    }
}

def optimized_bubble_sort(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

# Example usage
scores = [5, 3, 8, 1, 4]
print("Before:", scores)
optimized_bubble_sort(scores)
print("After:", scores)

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

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int pass = 0; pass < n - 1; ++pass) {
        bool swapped = false;
        for (int i = 0; i < n - pass - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                swap(arr[i], arr[i + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> data = {5, 3, 8, 1, 4};
    bubbleSort(data);
    for (int x : data) cout << x << " ";
    return 0;
}

public class RecursiveAndCocktailSort {

    // Recursive Bubble Sort
    public static void recursiveBubbleSort(int[] arr, int n) {
        if (n <= 1) return;
        boolean swapped = false;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) return; // already sorted
        recursiveBubbleSort(arr, n - 1);
    }

    // Cocktail Shaker Sort
    public static void cocktailSort(int[] arr) {
        boolean swapped = true;
        int start = 0;
        int end = arr.length - 1;

        while (swapped) {
            swapped = false;

            // Left to right
            for (int i = start; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;
            end--;
            swapped = false;

            // Right to left
            for (int i = end - 1; i >= start; i--) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }
            start++;
        }
    }

    public static void main(String[] args) {
        int[] test1 = {5, 1, 4, 2, 8};
        recursiveBubbleSort(test1, test1.length);
        System.out.println("Recursive: " + java.util.Arrays.toString(test1));

        int[] test2 = {5, 1, 4, 2, 8};
        cocktailSort(test2);
        System.out.println("Cocktail:   " + java.util.Arrays.toString(test2));
    }
}

// Minimal Bubble Sort without early exit (for demonstration only)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // swap
      }
    }
  }
  return arr;
}

console.log(bubbleSort([4, 2, 9, 1])); // [1, 2, 4, 9]

Advantages:
- Simplicity: Easy to understand and implement.
- In-place: O(1) space.
- Stable: Preserves equal element order.
- Adaptive: O(n) with early exit.

Disadvantages:
- Slow: O(n²) time.
- Many swaps: Inefficient.
- Rarely used: Not practical for large datasets.

public class BubbleSortGuard {
    public static void safeSort(int[] arr) {
        // Only use Bubble Sort for very small arrays
        if (arr.length <= 20) {
            optimizedBubbleSort(arr);
        } else {
            // Fall back to built-in Quicksort for larger data
            java.util.Arrays.sort(arr);
        }
    }

    static void optimizedBubbleSort(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 tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}

// io.thecodeforge — dsa tutorial

public class BubbleSortBaseline {
    public static void bubbleSort(int[] inventory) {
        int n = inventory.length;
        for (int pass = 0; pass < n - 1; pass++) {
            for (int j = 0; j < n - pass - 1; j++) {
                if (inventory[j] > inventory[j + 1]) {
                    int temp = inventory[j];
                    inventory[j] = inventory[j + 1];
                    inventory[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] inventory = {5, 3, 8, 2};
        bubbleSort(inventory);
        for (int id : inventory) {
            System.out.print(id + " ");
        }
    }
}

// io.thecodeforge — dsa tutorial

public class BubbleSortTrace {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int pass = 1; pass <= n - 1; pass++) {
            System.out.print("Pass " + pass + ": ");
            for (int j = 0; j < n - pass; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            for (int val : arr) System.out.print(val + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 3, 8, 2};
        bubbleSort(data);
    }
}

// io.thecodeforge — dsa tutorial

public class BubbleSortPseudocode {
    // Translating the pseudocode:
    // procedure bubbleSort(A: list of sortable items)
    //     n = length(A)
    //     repeat
    //         swapped = false
    //         for i = 1 to n-1 inclusive do
    //             if A[i-1] > A[i] then
    //                 swap(A[i-1], A[i])
    //                 swapped = true
    //             end if
    //         end for
    //         n = n - 1
    //     until not swapped
    // end procedure

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2, 8};
        bubbleSort(arr);
        for (int v : arr)
            System.out.print(v + " ");
    }

    static void bubbleSort(int[] a) {
        int n = a.length;
        boolean swapped;
        do {
            swapped = false;
            for (int i = 1; i < n; i++) {
                if (a[i - 1] > a[i]) {
                    int t = a[i - 1];
                    a[i - 1] = a[i];
                    a[i] = t;
                    swapped = true;
                }
            }
            n--;
        } while (swapped);
    }
}

// io.thecodeforge — dsa tutorial

class User {
    String name;
    int regDay;
    User(String n, int d) { name = n; regDay = d; }
    public String toString() { return name + ":" + regDay; }
}

public class StableBubble {
    public static void main(String[] args) {
        User[] users = {
            new User("Alice", 1),
            new User("Bob", 2),
            new User("Alice", 3)
        };
        // Bubble sort by name (ascending)
        for (int i = 0; i < users.length - 1; i++)
            for (int j = 0; j < users.length - 1 - i; j++)
                if (users[j].name.compareTo(users[j+1].name) > 0) {
                    User t = users[j];
                    users[j] = users[j+1];
                    users[j+1] = t;
                }
        for (User u : users)
            System.out.print(u + " ");
    }
}

// io.thecodeforge — dsa tutorial

public class BubbleSortDemo {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean 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 tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] data = {5, 1, 4, 2, 8};
        bubbleSort(data);
        for (int v : data) System.out.print(v + " ");
    }
}

// io.thecodeforge — dsa tutorial

public class BubbleSortAgenda {
    // 1. Why Bubble Sort fails at scale
    // 2. Neighbor-swapping passes
    // 3. Early-stop optimization
    // 4. Stability for object sorting
    // 5. When O(n²) is acceptable
    public static void main(String[] args) {
        int[] arr = {3, 0, 2, 1};
        boolean swapped;
        for (int i = 0; i < arr.length - 1; i++) {
            swapped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int t = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = t;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }
}