On this concept: Formula

Not sure which lesson to do first? Find your level and get a plan →

CS Thinking · Computational Thinking · Grade 6-8

Bubble Sort

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.

O(n2) time complexity

Quick Answer

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. Each pass carries the largest remaining value to the end, like a bubble rising, so each new pass can stop one place sooner. When a whole pass makes no swaps, the list is sorted and you can stop. Use it for small lists or to learn how sorting works; for n items it can need about n2/2 comparisons, far too many for big data.

Why This 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.

Intuitive Explanation

Line up the numbers [6, 2, 8, 3]. Compare the first two, 6 and 2: out of order, so swap, giving [2, 6, 8, 3]. Compare 6 and 8: fine. Compare 8 and 3: swap, giving [2, 6, 3, 8]. That was one pass. The 8, the largest value, was carried along by every swap it took part in until it reached the end, the way a bubble rises to the top of a glass. It is now in its final place.

The second pass only needs to reach the second-to-last spot: compare 2 and 6 (fine), then 6 and 3 (swap), giving [2, 3, 6, 8]. Now 6 is in place too. A third pass compares 2 and 3 and makes no swaps, which proves the list is sorted: if no neighbors are out of order, nothing is. That took 3 passes and 3 + 2 + 1 = 6 comparisons.

Small values travel the other way slowly. A small number at the end moves only one place left per pass, so [2, 3, 4, 5, 1] needs 4 passes just to bring the 1 to the front. That slowness is why bubble sort makes up to n(n−1)/2 comparisons. It is a fine way to sort ten cards and a poor way to sort ten thousand records.

Swapping neighbors is what makes it bubble sort. Sliding each new item into place among already sorted ones is insertion sort, and repeatedly moving the smallest remaining item to the front is selection sort: different methods, same final list.

Think of it like this. 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.

Core idea. Each pass moves the largest unsorted element to its correct position at the end.


When to Use

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.

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

How to Recognize It

Watch which items get compared: bubble sort only ever looks at two neighbors side by side.

  1. Is each comparison between two items standing next to each other?

    Yes fits bubble sort. If items far apart are compared, such as the front items of two sorted halves, it is Merge Sort.

  2. Does the largest unsorted value end up at the end after each pass?

    Yes is the bubbling that names the method. If instead each new item is slid into place among the ones already sorted, like cards in a hand, it is Insertion Sort.

  3. Does the method stop once a whole pass makes no swaps?

    Yes is bubble sort with the early exit. If the question only asks what the sorted list is, not how it got there, the topic is Sorting.

  4. Is the list small, or being sorted by hand to learn how sorting works?

    Yes makes bubble sort a fair choice. For thousands of items, its roughly n2/2 comparisons make Merge Sort the sensible pick.

Bubble Sort vs Merge Sort vs Insertion Sort vs Sorting

Bubble sort, insertion sort and merge sort all produce the same sorted list, so only the moves tell them apart. Ask which items get compared and how they travel.

Bubble Sort

Meaning
Bubble sort walks through the list again and again, swapping any two neighbors that are in the wrong order.
Key test
Only side-by-side items are compared and swapped.
Formula
n(n−1)2 comparisons in the worst case
Example
For 10 items, the worst case needs 10×92=45 comparisons.

Merge Sort

Meaning
Merge sort cuts the list into halves, sorts each half and merges the two sorted halves.
Key test
Two sorted halves are merged by comparing their front items.
Formula
O(nlog⁡n)
Example
Merging [1, 5] and [2, 3] takes the fronts in turn: 1, then 2, then 3, then 5.

Insertion Sort

Meaning
Insertion sort takes items one at a time and slides each into its place among the items already sorted.
Key test
A sorted section grows from the left, one new item inserted at a time.
Formula
O(n2) at worst
Example
Sorting a hand of cards by picking up each new card and placing it in order.

Sorting

Meaning
Sorting is the task of arranging every item of a list into order, whatever method is used.
Key test
Only the ordered result matters, not which items were compared.
Example
Arranging [9, 4, 7] from smallest to largest gives [4, 7, 9].

Formula & Notation

O(n2) time complexity
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 — Trace passes with early exit

Easy

Sort [5, 1, 4, 2, 8] in ascending order with bubble sort, stopping after the first pass with no swaps. Show each pass and count comparisons and swaps.
Show the steps and the answer
  1. Pass 1: 5 and 1 swap → [1, 5, 4, 2, 8]; 5 and 4 swap → [1, 4, 5, 2, 8]; 5 and 2 swap → [1, 4, 2, 5, 8]; 5 and 8 stay. 4 comparisons, 3 swaps.

    The 5 travels right until it meets the larger 8. After this pass the largest value, 8, is certain to be in last place.

  2. Pass 2, up to the 4th position: 1 and 4 stay; 4 and 2 swap → [1, 2, 4, 5, 8]; 4 and 5 stay. 3 comparisons, 1 swap.

    The last position is already final, so this pass needs one comparison fewer.

  3. Pass 3, up to the 3rd position: 1 and 2 stay; 2 and 4 stay. 2 comparisons, no swaps, so stop.

    A pass with no swaps means every neighboring pair is in order, so the whole list is sorted.

  4. Total: 4 + 3 + 2 = 9 comparisons and 3 + 1 = 4 swaps. Without the early exit, a 4th pass would add 1 more comparison, making 10.

    The early exit saves every pass after the list is already in order.

Answer: [1, 2, 4, 5, 8] after 3 passes, with 9 comparisons and 4 swaps.

Takeaway: Shorten each pass by one position, and stop after the first pass that makes no swaps.

Example 2 — Best case, worst case, and the limit

Standard

Count bubble sort's comparisons and swaps (with early exit) on [1, 2, 3, 4, 5] and on [5, 4, 3, 2, 1]. Then estimate the work for 1,000 items in reverse order and compare with merge sort.
Show the steps and the answer
  1. Sorted [1, 2, 3, 4, 5]: one pass of 4 comparisons, no swaps, stop.

    The early exit makes the best case a single pass of n−1 comparisons.

  2. Reversed [5, 4, 3, 2, 1]: pass 1 carries 5 to the end with 4 swaps, giving [4, 3, 2, 1, 5]; passes 2, 3 and 4 make 3, 2 and 1 swaps. Total: 10 comparisons and 10 swaps.

    Every pair starts out of order, so every comparison is a swap and no pass can end early.

  3. 1,000 items in reverse: 1000⋅999/2=499,500 comparisons and as many swaps.

    The worst case grows with n2: for large lists, ten times the items means about a hundred times the work.

  4. Merge sort on the same 1,000 items: at most about 1000×log⁡21000≈10,000 comparisons.

    Input order barely changes merge sort's cost, while it decides everything for bubble sort.

Answer: Sorted: 4 comparisons, 0 swaps. Reversed: 10 comparisons, 10 swaps. For 1,000 reversed items, 499,500 comparisons, against at most about 10,000 for merge sort.

Takeaway: Bubble sort is quick only on lists that are already close to sorted; on large, badly ordered lists its n2 growth rules it out.

Example 3 — Find the mistake: one pass is not a sort

Application

Sofia runs one pass of bubble sort on [3, 9, 1, 7] and gets [3, 1, 7, 9]. She writes: "Bubble sort walked through the whole list, so it is sorted now." Find the mistake and correct it.
Show the steps and the answer
  1. Check her result: in [3, 1, 7, 9] the first pair, 3 and 1, is still out of order.

    One pair out of order is enough to show the list is not sorted.

  2. Say what one pass really guarantees: only that the largest value, 9, has reached the end.

    A pass carries just one value, the biggest still unsorted, to its final place; smaller values may move only one step.

  3. Pass 2 on the first three positions: 3 and 1 swap → [1, 3, 7, 9]; 3 and 7 stay.

    With 9 fixed, the pass stops one place earlier.

  4. Pass 3: 1 and 3 stay, no swaps, so stop.

    Only a pass with zero swaps proves the list is in order.

Answer: One pass is not enough. After 3 passes and 3 + 2 + 1 = 6 comparisons, the list is [1, 3, 7, 9].

Takeaway: After one pass only the largest value is guaranteed to be in place. Keep making passes until one makes no swaps.

Where You'll See It

  • Lining up for a class photo by height

    The teacher walks down the row comparing each pair of neighbors and asking the taller one to step right — repeating passes until nobody needs to swap is bubble sort, and you can see the tallest kid 'bubble' to the end after the first pass.

  • Reordering a small playlist by song length by hand

    With only 6 songs, repeatedly swapping any neighboring pair that is out of order is simple and easy to get right — bubble sort shines for tiny lists even though it would be painfully slow for 6,000 songs.

  • Checking a scoreboard that is already in order

    If a list of 100 scores is already sorted, the first bubble-sort pass makes zero swaps and the early-exit check stops right there: 99 comparisons instead of the 4,950 a full run would make. Without that check, bubble sort would grind through every pass anyway.

Common Mistakes

  1. The slip: Bubble sort needs n full passes no matter what, so it is always O(n^2).

    Why it's tempting: The basic version does run n passes, so students assume the count never drops.

    Instead: With the early-exit optimization, a pass that makes no swaps proves the list is sorted, giving O(n) best case on already-sorted data. The O(n^2) is the worst/average case, not a guarantee on every input.

  2. The slip: One full pass of bubble sort sorts the whole list.

    Why it's tempting: After one pass the list clearly looks 'more sorted,' so it feels finished.

    Instead: One pass only guarantees the single largest unsorted element reaches its final spot at the end. You need repeated passes until a pass makes no swaps.

  3. The slip: Each pass should still compare the elements already parked at the end.

    Why it's tempting: Re-scanning the whole array each time feels safer and simpler.

    Instead: After k passes the last k elements are in final position, so each new pass can stop k earlier — comparing into the sorted tail just wastes work.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Do one pass of bubble sort on [5, 1, 4, 2]. Show the list after each comparison.

    Hint: Compare positions 0 and 1, then 1 and 2, then 2 and 3. Swap if the left one is bigger.

  2. After the first pass the list is [1, 4, 2, 5]. Finish the bubble sort with early exit. How many more passes run?

    Hint: Keep making passes until one pass makes no swaps.

  3. Bubble sort runs on 6 items with no early exit, and each pass compares only the unsorted part. How many comparisons does it make in total?

    Hint: The first pass makes 5 comparisons. Each later pass makes one fewer.

  4. Bubble sort with early exit runs on the already sorted list [2, 3, 7, 9, 11]. How many comparisons does it make?

    Hint: How many adjacent pairs are in one pass? What happens if nothing swaps?

  5. A music app must sort 2 million song titles every time the library loads. Bubble sort or merge sort?

    Hint: Estimate n2 and nlog⁡2n for n=2×106.

  6. Sorting [4, 3, 2, 1], a student still compares all three pairs in pass 3, saying: 'Every pass must check every pair.' How many comparisons does pass 3 really need?

    Hint: After two passes, which values are already in their final places?

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Why is [2, 3, 4, 5, 1] so slow for bubble sort when it is almost sorted?

Because the 1 can move only one place to the left per pass, since each pass swaps it with just one neighbor. It needs 4 passes to reach the front, plus a fifth pass with no swaps to prove the list is sorted. Programmers call small values stuck near the end turtles. The opposite case, [5, 1, 2, 3, 4], needs only one pass of swaps and one check pass.

How many swaps does bubble sort make?

Exactly one swap for every pair of items that starts in the wrong order. In [3, 1, 2], the pairs (3, 1) and (3, 2) are out of order, so it makes 2 swaps. A list in reverse order has every pair wrong: for 6 items that is 6×52=15\frac{6 \times 5}{2} = 15 swaps, the most possible. Counting the wrong-order pairs tells you the swaps without running the sort.

Is bubble sort ever used in real programs?

Rarely. Even for small lists, insertion sort usually does the same job with fewer steps, so library sorts use insertion sort for tiny pieces instead. Bubble sort survives mainly in classrooms, because its rule is easy to see and to trace by hand. The computer scientist Donald Knuth wrote that it seems to have nothing to recommend it except a catchy name and some interesting theory.

Learning Path

Bubble Sort

You are here

Next →

Merge Sort
You need Sorting (ordering by a key and direction), Iteration (repeating passes until a condition stops them) and Algorithm Efficiency (what O(n2) means) first. Bubble Sort adds a complete, traceable method: neighbor swaps, a shrinking unsorted range and an early exit. Next, Merge Sort shows how splitting the list beats O(n2), sorting in about nlog⁡2n comparisons.

See Also