Bubble Sort

Category: Classical
Difficulty: Beginner
Time Complexity: O(n²)
Space Complexity: O(1)

Overview

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order. After each full pass, the largest unsorted element ‘bubbles up’ to its correct position. The algorithm terminates early if a pass completes with no swaps, indicating the array is already sorted. While its O(n²) worst-case performance makes it impractical for large datasets, Bubble Sort is an excellent educational algorithm for understanding sorting fundamentals, invariants, and optimization techniques like early termination.

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("bubble-sort")

Default Inputs

{
  "array": [
    64,
    34,
    25,
    12,
    22,
    11,
    90
  ]
}

Input Examples

Default (unsorted)

{
  "array": [
    64,
    34,
    25,
    12,
    22,
    11,
    90
  ]
}

Already sorted

{
  "array": [
    1,
    2,
    3,
    4,
    5
  ]
}

Reverse sorted (worst case)

{
  "array": [
    5,
    4,
    3,
    2,
    1
  ]
}

Single element

{
  "array": [
    42
  ]
}

Empty array

{
  "array": []
}

With duplicates

{
  "array": [
    5,
    3,
    8,
    3,
    2,
    5,
    1
  ]
}

Nearly sorted

{
  "array": [
    1,
    2,
    5,
    3,
    4
  ]
}

Code

Pseudocode

function bubbleSort(array):
  n = length(array)
  for pass = 0 to n - 2:
    swapped = false
    for j = 0 to n - 2 - pass:
      if array[j] > array[j + 1]:
        swap(array[j], array[j + 1])
        swapped = true
    if not swapped:
      break          // Early termination
  return array

Python

def bubble_sort(array: list[int]) -> list[int]:
    n = len(array)
    for pass_num in range(n - 1):
        swapped = False
        for j in range(n - 1 - pass_num):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                swapped = True
        if not swapped:
            break
    return array

JavaScript

function bubbleSort(array) {
  const n = array.length;
  for (let pass = 0; pass < n - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < n - 1 - pass; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }
  return array;
}

Key Concepts

Bubbling Up

In each pass, the largest unsorted element ‘bubbles up’ to its correct position at the end of the unsorted portion. After pass p, the element at index N-1-p is in its final sorted position.

Early Termination

If a complete pass makes no swaps, the array is already sorted. This optimization reduces the best-case time complexity from O(n²) to O(n) for already-sorted arrays.

Stability

Bubble Sort is a stable sorting algorithm. Equal elements are never swapped (we use strict > comparison), so their relative order from the original array is preserved.

Adaptive Behavior

Bubble Sort is adaptive — it performs fewer operations on nearly-sorted arrays. The number of swaps equals the number of inversions in the input, and early termination can skip unnecessary passes.

Common Pitfalls

• O(n²) worst case: A reverse-sorted array requires the maximum number of comparisons and swaps: n(n-1)/2. For large arrays, this makes Bubble Sort impractical compared to O(n log n) algorithms like Merge Sort or Quick Sort.
• Forgetting early termination: Without the swapped flag, Bubble Sort always runs all n-1 passes even on a sorted array. The early termination optimization is simple to implement and dramatically improves best-case performance.
• Using >= instead of >: Using >= for comparison instead of > breaks stability. Equal elements would be swapped unnecessarily, changing their relative order from the original array.

Quiz

Q1: After 2 passes of Bubble Sort on an array of 6 elements, how many elements are guaranteed to be in their final positions?

• A) 1
• B) 2
• C) 3
• D) 6

Show answer

Answer: B) 2

After each pass, the largest unsorted element bubbles to its correct position. After 2 passes, the 2 largest elements are in their final positions at the end of the array.

Q2: What is the best-case time complexity of optimized Bubble Sort (with early termination)?

• A) O(1)
• B) O(n)
• C) O(n log n)
• D) O(n²)

Show answer

Answer: B) O(n)

On an already-sorted array, Bubble Sort makes one pass with n-1 comparisons and zero swaps, then terminates early. This gives O(n) best-case time complexity.

Q3: How many swaps does Bubble Sort perform on the array [3, 1, 2]?

• A) 1
• B) 2
• C) 3
• D) 4

Show answer

Answer: B) 2

Pass 1: Compare 3,1 → swap (→[1,3,2]), compare 3,2 → swap (→[1,2,3]). Pass 2: Compare 1,2 → no swap. Early termination. Total: 2 swaps.

Further Reading

• Bubble Sort — Wikipedia (reference)
• VisuAlgo — Sorting Visualizations (interactive)

Related Algorithms

• Merge Sort
• QuickSort
• Binary Search