Mastering Algorithms

Bubble Sort

Overview

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

The name "bubble sort" comes from the way smaller elements "bubble" to the top of the list (beginning of the array) with each pass, similar to how bubbles rise to the surface in water.

How It Works

The algorithm works by:

  1. Comparing adjacent elements in the array
  2. Swapping them if they are in the wrong order (ascending or descending)
  3. Repeating this process for each pair of adjacent elements
  4. Continuing until no more swaps are needed

With each complete pass through the array, the largest unsorted element "bubbles up" to its correct position at the end of the array.

Algorithm


BubbleSort(arr):
    n = length of arr
    for i = 0 to n - 1:
        swapped = false
        for j = 0 to n - i - 2:
            if arr[j] > arr[j + 1]:
                swap arr[j] and arr[j + 1]
                swapped = true
        if swapped == false:
            break  # Array is already sorted

Implementation


def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps occurred, array is sorted
        if not swapped:
            break
    return arr

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n) - when array is already sorted (with optimization)
    • Average Case: O(n²)
    • Worst Case: O(n²) - when array is sorted in reverse order
  • Space Complexity: O(1) - only uses a constant amount of extra space

The nested loops result in O(n²) comparisons in the worst case. The optimization that checks if any swaps occurred allows the algorithm to terminate early if the array is already sorted, giving O(n) best case.

Characteristics

  • Stable: Yes - equal elements maintain their relative order
  • In-place: Yes - only requires O(1) extra space
  • Adaptive: Yes - can detect if array is already sorted
  • Online: No - requires the entire array to be present

When to Use Bubble Sort

Bubble Sort is rarely used in practice due to its poor performance compared to other sorting algorithms. However, it can be useful:

  • For educational purposes to understand sorting concepts
  • When simplicity is more important than efficiency
  • For very small datasets where the overhead of more complex algorithms isn't justified
  • When you need a stable, in-place sorting algorithm and performance is not critical

Example

Sorting [64, 34, 25, 12, 22, 11, 90]: 

Pass 1: [34, 25, 12, 22, 11, 64, 90]  (64 and 90 are in correct positions)
Pass 2: [25, 12, 22, 11, 34, 64, 90]  (34 is in correct position)
Pass 3: [12, 22, 11, 25, 34, 64, 90]  (25 is in correct position)
Pass 4: [12, 11, 22, 25, 34, 64, 90]  (22 is in correct position)
Pass 5: [11, 12, 22, 25, 34, 64, 90]  (12 is in correct position)
Pass 6: [11, 12, 22, 25, 34, 64, 90]  (No swaps, array is sorted)

Related Algorithms

Explore other sorting algorithms: