Bubble Sort Complete Guide

Video Explainer

Prefer video learning? This explainer gives a quick visual walkthrough of the core idea before you dive into the detailed sections below.

Related Sorting Guides

Bubble, merge, and quick sort are tightly related. Compare them side-by-side to understand tradeoffs in runtime, memory, and stability.

Core Concepts

Learn the core building blocks and terminology in one place before comparisons, so the mechanics are clear and duplicates are removed.

How It Compares

Real-World Stories and Company Examples

Bubble sort with early-exit optimization

function bubbleSort(values: number[]): number[] {
  const sortedValues = [...values]
  for (let passIndex = 0; passIndex < sortedValues.length - 1; passIndex += 1) {
    let didSwap = false
    for (let compareIndex = 0; compareIndex < sortedValues.length - 1 - passIndex; compareIndex += 1) {
      if (sortedValues[compareIndex] > sortedValues[compareIndex + 1]) {
        ;[sortedValues[compareIndex], sortedValues[compareIndex + 1]] = [sortedValues[compareIndex + 1], sortedValues[compareIndex]]
        didSwap = true
      }
    }
    if (!didSwap) break
  }
  return sortedValues
}

Common Problems and Failure Modes

• Running full n passes even when array is already sorted.
• Ignoring shrinking upper bound and doing redundant comparisons.
• Using bubble sort on large production datasets.
• Off-by-one errors in inner loop boundary.
• Assuming O(n) behavior without early-exit optimization.

Tips and Tricks

• Bubble sort is mainly for learning and tiny inputs, not production-scale datasets.
• Use early-exit flag so already-sorted data finishes in linear time.
• Shrink the inner loop boundary each pass because the tail becomes sorted.
• Step through a five-element example manually to internalize swap flow.

When to Use

Use these signals to decide if this data structure/algorithm is the right fit before implementation.

Real-system usage signals

• Great for learning sorting fundamentals and swap-based ordering.
• Very easy to implement and debug step-by-step.
• Can short-circuit early when input is already sorted.

LeetCode-specific tips (including pattern-identification signals)

• Identification signal: educational adjacent-swap process is required explicitly or for teaching mechanics.
• Identification signal: problem expects simple in-place sort with tiny inputs where clarity matters more than scale.
• If prompt emphasizes repeated neighbor comparisons/swaps, bubble sort pattern is being tested.
• For Bubble Sort questions, start by naming the core invariant before writing code.
• Use the constraint section to set time/space target first, then pick the data structure/algorithm.
• Solve one tiny example by hand and map each transition to your variables before implementing.
• Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
• During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.