Bubble Sort Formula

Bubble sort is a simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in.

The Formula

O(n2)O(n^2) time complexity

When to use: Heavier bubbles sink and lighter bubbles rise — larger values slowly move to the end of the list.

Quick Example

[5,3,1]: compare 5,3 → swap → [3,5,1]; compare 5,1 → swap → [3,1,5]; repeat until sorted.

What This Formula Means

A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.

Heavier bubbles sink and lighter bubbles rise — larger values slowly move to the end of the list.

Formal View

Bubble sort performs up to n−1n-1 passes over array A[0..n−1]A[0..n-1]. In each pass, for j=0j = 0 to n−2−in-2-i, if A[j]>A[j+1]A[j] > A[j+1], swap them. After pass ii, the i+1i+1 largest elements are in their final positions. Worst and average case: O(n2)O(n^2).

Worked Examples

Example 1

medium
Fully bubble sort [4,2,3,1][4, 2, 3, 1] ascending. Give the list after each pass and the total swaps.

Answer

[1,2,3,4]; 5 swaps[1, 2, 3, 4];\ 5\text{ swaps}

First step

1
Pass 1: [4,2,3,1]→[2,4,3,1]→[2,3,4,1]→[2,3,1,4][4,2,3,1] \to [2,4,3,1] \to [2,3,4,1] \to [2,3,1,4] (3 swaps).

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Unlock answer keys One Family plan — every worked solution, all subjects

Example 2

medium
Bubble sort [1,3,2,4][1, 3, 2, 4] ascending with early-exit. Passes and swaps?

Example 3

medium
Bubble sort [5,1,4,2,8][5, 1, 4, 2, 8] ascending. Final list and total swap count?

Common Mistakes

  • Not optimizing with an early exit—if a pass makes no swaps, the list is already sorted and you can stop - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Comparing elements beyond the sorted portion at the end of the array, wasting comparisons - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Using bubble sort for large datasets when O(nlog⁡n)O(n \log n) algorithms are available and dramatically faster - Fix this by naming the input, process, output, evidence, and checking "Am I judging the steps of a method for correctness, termination, edge cases, and efficiency as inputs change?" before using the concept.
  • Using bubble sort from a keyword alone - Signal words like algorithm, search, sort only point to a possible model; the computing structure must match too.

Why This Formula Matters

Bubble sort is easy to understand and implement, making it an excellent teaching example for understanding how sorting works. However, its O(n2)O(n^2) performance makes it impractical for large datasets, which is why more efficient algorithms like merge sort are used in practice.

Frequently Asked Questions

What is the Bubble Sort formula?

A simple sorting algorithm that repeatedly walks through the list, compares each pair of adjacent elements, and swaps them if they are in the wrong order. This process repeats until no more swaps are needed, meaning the list is fully sorted.

How do you use the Bubble Sort formula?

Heavier bubbles sink and lighter bubbles rise — larger values slowly move to the end of the list.

Why is the Bubble Sort formula important in CS Thinking?

Bubble sort is easy to understand and implement, making it an excellent teaching example for understanding how sorting works. However, its O(n2)O(n^2) performance makes it impractical for large datasets, which is why more efficient algorithms like merge sort are used in practice.

What do students get wrong about Bubble Sort?

Bubble sort is O(n²) — avoid it for large data; use merge sort or quick sort instead.

What should I learn before the Bubble Sort formula?

Before studying the Bubble Sort formula, you should understand: sorting, iteration, efficiency.

← Back to Bubble Sort See All Examples Practice Problems

Related Formulas

Merge Sort Formula