Bubble Sort Algorithm

Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. The algorithm gets its name from the way larger elements "bubble" to the top (end) of the list through successive comparisons and swaps, much like air bubbles rising to the surface of water.

Interactive Visualization

Bubble Sort Animation

Speed: 500ms

Array Visualization

Normal

Comparing

Swapping

Sorted

How Bubble Sort Works:

• Compare: Compare adjacent elements in the array

• Swap: If they're in wrong order, swap them

• Repeat: Continue until no more swaps are needed

• Time Complexity: O(n²) average and worst case

• Space Complexity: O(1) - sorts in place

• Stability: Stable - maintains relative order of equal elements

Adjacent Swapping Strategy

Bubble sort employs an adjacent swapping strategy that systematically compares neighboring elements and exchanges them when they are out of order. This simple approach ensures that after each complete pass through the array, the next largest element is guaranteed to be in its final sorted position.

1. Compare

Compare each pair of adjacent elements in the array

2. Swap

Swap them if they are in the wrong order (left > right)

3. Repeat

Repeat for all elements to complete one pass through the array

Key Insight

After each complete pass through the array, the largest unsorted element "bubbles up" to its correct position at the end. This means we can reduce the range of comparison in each subsequent pass, as the last n elements are already in their final sorted positions after n passes.

How Bubble Sort Works

Step-by-Step Process

Start: Begin with the first element and compare it with the next element

Compare & Swap: If the first element is larger, swap the two elements

Move Forward: Move to the next pair and repeat the comparison and swap

Complete Pass: Continue until reaching the end of the unsorted portion

Repeat Passes: Repeat the entire process for remaining unsorted elements

Example: Sorting [5, 1, 4, 2]

Initial: [5, 1, 4, 2]

Pass 1: [1, 4, 2, 5] - 5 bubbles to the end

Pass 2: [1, 2, 4, 5] - 4 bubbles to position 3

Pass 3: [1, 2, 4, 5] - no swaps needed, array is sorted

Result: [1, 2, 4, 5] - fully sorted array

Optimization - The 'Swapped' Flag

A crucial optimization for bubble sort involves using a swapped flag to detect when the array becomes sorted before all passes are completed. If no swaps occur during a complete pass, the array is already sorted and the algorithm can terminate early.

How the Optimization Works

Initialize Flag: Set swapped = false at the start of each pass

Track Swaps: Set swapped = true whenever elements are exchanged

Early Exit: If swapped remains false after a pass, terminate the algorithm

Best Case Impact: Reduces time complexity from O(n²) to O(n) for sorted arrays

Pseudocode

ALGORITHM BubbleSort(arr[], n)
BEGIN
    // Outer loop for number of passes
    // n-2 is done for two reasons:
    // 1. size of array is n-1 due to 0 based indexing
    // 2. To avoid out of bound error while comparing i with i+1 element
    FOR i = 0 TO n-2 DO
        swapped = false               // Optimization flag
        
        // Inner loop for comparisons in current pass
        FOR j = 0 TO n-i-2 DO
            // Compare adjacent elements
            IF arr[j] > arr[j+1] THEN
                SWAP arr[j] WITH arr[j+1]    // Exchange elements
                swapped = true               // Mark that swap occurred
            END IF
        END FOR
        
        // Early termination optimization
        IF swapped = false THEN
            BREAK                     // Array is already sorted
        END IF
    END FOR
END

// Basic version without optimization
ALGORITHM BasicBubbleSort(arr[], n)
BEGIN
    FOR i = 0 TO n-2 DO
        FOR j = 0 TO n-i-2 DO
            IF arr[j] > arr[j+1] THEN
                SWAP arr[j] WITH arr[j+1]
            END IF
        END FOR
    END FOR
END

Complexity Analysis

Case	Time Complexity	Space Complexity	Explanation
Best Case	O(n)	O(1)	Array already sorted - single pass with optimization flag
Average Case	O(n²)	O(1)	Random order - approximately half the maximum comparisons
Worst Case	O(n²)	O(1)	Reverse sorted array - maximum number of comparisons and swaps

Why O(n) Best Case?

• Optimization Flag: Swapped flag detects when array is already sorted
• Single Pass: Only one pass through the array is needed
• Linear Comparisons: Exactly n-1 comparisons, no swaps required
• Early Termination: Algorithm stops as soon as sorted state is detected

Why O(n²) Average/Worst Case?

• Nested Loops: Two nested loops create quadratic time complexity
• Maximum Comparisons: Up to n(n-1)/2 comparisons in worst case
• All Swaps: Every comparison may result in a swap operation
• No Early Exit: Cannot terminate early when array is not sorted

Code Examples

Here are implementations of bubble sort in different programming languages. Each version includes the swapped flag optimization for improved performance on already sorted or nearly sorted arrays.

 def bubble_sort(arr):
    """
    Sort an array using the bubble sort algorithm.
    Time Complexity: O(n²)
    Space Complexity: O(1)
    """
    n = len(arr)
    for i in range(n - 1):
        # Flag to optimize - if no swaps occur, array is sorted
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap elements using Python tuple assignment
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        
        # If no swapping occurred, array is already sorted
        if not swapped:
            break
    
    return arr

# Example usage
if __name__ == "__main__":
    numbers = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", numbers)
    bubble_sort(numbers)
    print("Sorted array:", numbers) 
 public class BubbleSort {
    
    /**
     * Sorts an array using the bubble sort algorithm
     * @param arr The array to be sorted
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            // Flag to optimize - if no swaps occur, array is sorted
            boolean swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no swapping occurred, array is already sorted
            if (!swapped) {
                break;
            }
        }
    }
    
    /**
     * Helper method to print an array
     */
    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};
        
        System.out.print("Original array: ");
        printArray(numbers);
        
        bubbleSort(numbers);
        
        System.out.print("Sorted array: ");
        printArray(numbers);
    }
} 
 #include <iostream>
#include <vector>
using namespace std;

/**
 * Sorts a vector using the bubble sort algorithm
 * @param arr Reference to the vector to be sorted
 */
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    
    for (int i = 0; i < n - 1; i++) {
        // Flag to optimize - if no swaps occur, array is sorted
        bool swapped = false;
        
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap elements using STL swap function
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        
        // If no swapping occurred, array is already sorted
        if (!swapped) {
            break;
        }
    }
}

/**
 * Helper function to print a vector
 */
void printArray(const vector<int>& arr) {
    for (int value : arr) {
        cout << value << " ";
    }
    cout << endl;
}

int main() {
    vector<int> numbers = {64, 34, 25, 12, 22, 11, 90};
    
    cout << "Original array: ";
    printArray(numbers);
    
    bubbleSort(numbers);
    
    cout << "Sorted array: ";
    printArray(numbers);
    
    return 0;
} 

When to Use Bubble Sort

Advantages

• Simple to Understand: Very intuitive algorithm that's easy to grasp
• Easy to Implement: Minimal code required, straightforward logic
• O(1) Space Complexity: In-place sorting with constant extra memory
• Stable: Maintains relative order of equal elements
• Adaptive: With optimization, performs well on nearly sorted data
• No Additional Data Structures: Works directly on the input array

Disadvantages

• Extremely Inefficient: O(n²) complexity makes it impractical for large datasets
• Poor Performance: Much slower than efficient algorithms like quicksort or mergesort
• Not Suitable for Production: Almost never used in real-world applications
• Excessive Swapping: May perform more swaps than necessary
• No Divide and Conquer: Cannot benefit from parallel processing
• Academic Only: Primarily useful for learning sorting concepts

Practical Recommendations

Use Bubble Sort For: Educational purposes, teaching sorting concepts, very small datasets (n ≤ 10), demonstrating algorithm complexity, coding interviews (to show you understand its limitations), prototyping when simplicity is more important than efficiency

Avoid Bubble Sort For: Any practical application with more than a few dozen elements, performance-critical systems, large datasets, production code, competitive programming, real-time systems where efficiency matters