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 wrong order.

The Formula

O(n2) time complexity

Ask yourself: Is a list sorted by repeatedly swapping adjacent items that are out of order?

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.

Bubble sort is like tidying books by height on a shelf when you may only swap two neighboring books. Walking left to right, you swap whenever a taller book stands left of a shorter one, so the tallest book is carried to the right end in a single sweep. A short book stuck at the far right moves only one place per sweep, which is why the method is slow.

Formal view

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

Worked examples

Example 1

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

Answer

[1,2,3,4]; 5 swaps

First step

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

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

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

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

Example 3

medium
Bubble sort [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
  • Comparing elements beyond the sorted portion at the end of the array, wasting comparisons
  • Using bubble sort for large datasets when O(nlog⁡n) algorithms are available and dramatically faster

Why this formula matters

Bubble sort is easy to trace by hand, which makes it the clearest place to see what a sorting algorithm promises: after pass k, the k largest values are in their final places. Its cost is the warning: 10 items need at most 45 comparisons, but 10,000 items need up to about 50 million. The early-exit check matters too, because it turns an already sorted list into a one-pass job.

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?

Bubble sort fits when the list is small (a few dozen items), when you are tracing a sort by hand, or when the list is nearly sorted with items only slightly out of place, since the early-exit check then finishes in a pass or two. Count its passes, comparisons and swaps when a question asks how a simple sort behaves. For large lists, use an O(nlog⁡n) method such as merge sort instead.

Why is the Bubble Sort formula important in CS Thinking?

Bubble sort is easy to trace by hand, which makes it the clearest place to see what a sorting algorithm promises: after pass k, the k largest values are in their final places. Its cost is the warning: 10 items need at most 45 comparisons, but 10,000 items need up to about 50 million. The early-exit check matters too, because it turns an already sorted list into a one-pass job.

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.