Bubble Sort Algorithm

Complexity (theory): best O(n) with early exit, average O(n²), worst O(n²). Extra space O(1). Stable and in place. The counters above are measured for your array only.

What Is the Bubble Sort Algorithm?

Bubble sort is one of the simplest sorting algorithms. It walks through the array again and again. In each walk, called a pass, it compares every pair of neighboring elements and swaps them if the left one is larger. Large values move toward the end like bubbles rising in water, which gives the algorithm its name.

Bubble sort is rarely used for real workloads because it is slow on large inputs. Even so, it is a popular teaching tool: the logic is short, the swaps are easy to see, and it introduces ideas such as passes, invariants and early termination.

How Bubble Sort Works: Steps, Example and Code

How Bubble Sort Works Step by Step

1. Start at the first element of the array.
2. Compare the current element with the next one.
3. If the current element is larger, swap the two.
4. Move one position to the right and repeat until you reach the end of the unsorted part.
5. After the pass, the largest unsorted element sits in its final position at the end.
6. Repeat the pass on the remaining unsorted part.
7. Stop when a pass makes no swaps, or when only one element remains.

The “no swaps” check is an optimization. Without it, bubble sort always makes about n²/2 comparisons. With it, an already sorted array needs just one pass.

Bubble Sort Example With a Step-by-Step Walkthrough

Sort the array [5, 1, 4, 2, 8].

1. Pass 1: compare 5 and 1, swap: [1, 5, 4, 2, 8]. Compare 5 and 4, swap: [1, 4, 5, 2, 8]. Compare 5 and 2, swap: [1, 4, 2, 5, 8]. Compare 5 and 8, no swap. The 8 is final.
2. Pass 2: compare 1 and 4, no swap. Compare 4 and 2, swap: [1, 2, 4, 5, 8]. Compare 4 and 5, no swap. The 5 is final.
3. Pass 3: compare 1 and 2, no swap. Compare 2 and 4, no swap. A pass with no swaps means the array is sorted.

The final array is [1, 2, 4, 5, 8]. In total this run made 9 comparisons and 4 swaps, and the visualization reports the same kind of counters for your own array.

Bubble Sort Pseudocode

bubbleSort(A):
  n = length(A)
  for pass = 0 to n - 2:
    swapped = false
    for j = 0 to n - 2 - pass:
      if A[j] > A[j + 1]:
        swap A[j], A[j + 1]
        swapped = true
    if not swapped: break      // already sorted

The inner loop shrinks by one each pass because the end of the array is already sorted. The swapped flag lets the algorithm stop early.

Bubble Sort Implementation in JavaScript

function bubbleSort(input) {
  const a = [...input];                         // copy: the input is not modified
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {                    // strict ">" keeps the sort stable
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;                        // no swaps: sorted
  }
  return a;
}

An empty array or a single element skips the outer loop and is returned as is. Because only a strictly larger left element triggers a swap, equal elements never pass each other.

Bubble Sort Time and Space Complexity

Time Complexity of Bubble Sort

In the worst case, a reverse-sorted array, every comparison leads to a swap, and the algorithm makes about n²/2 comparisons and n²/2 swaps. On average, about half of the comparisons lead to swaps, which is still quadratic.

Case	Time	When it happens
Best	O(n)	Already sorted, with the early-exit check
Average	O(n²)	Randomly ordered data
Worst	O(n²)	Reverse sorted

Space Complexity of Bubble Sort

Bubble sort works in place and uses only a few variables, so its auxiliary space is O(1). It has no recursion.

Bubble Sort Advantages, Disadvantages and Comparisons

Advantages and Disadvantages of Bubble Sort

Advantages: very simple code, stable, in place, and able to detect a sorted array early. It is also easy to visualize, which makes it great for learning.

Disadvantages: it does many swaps, and its O(n²) running time makes it impractical for large data. Insertion sort usually beats it, and merge sort or quick sort beat both on big arrays.

Bubble Sort vs Insertion Sort

Feature	Bubble sort	Insertion sort
Average time	O(n²)	O(n²)
Best case	O(n) with early exit	O(n)
Stable	Yes	Yes
Typical operations	Many swaps	Fewer, shorter moves
Practical use	Teaching	Small or nearly sorted data

Using Bubble Sort in Practice: Applications and Mistakes

Common Applications of Bubble Sort

• Teaching sorting, passes and loop invariants.
• Checking whether a very small list is sorted, using the swapped flag.
• Demonstrations where visible neighbor swaps help learners.

Production systems almost never choose bubble sort for large data.

Common Mistakes When Implementing Bubble Sort

• Looping the inner loop to n − 1 instead of n − 2 − pass, which reads past the end of the array.
• Forgetting the swapped flag, so sorted input still costs O(n²).
• Using a greater-or-equal test, which swaps equal items and makes the sort unstable.
• Not shrinking the inner range after each pass, which wastes comparisons.
• Skipping tests for sorted, reverse-sorted and duplicate-heavy arrays.

Bubble Sort Variations and Optimizations

Plain bubble sort can be improved in a few simple ways. None of them changes the O(n²) worst case, but they show how small ideas reduce wasted work.

Track the Last Swap Position

Instead of shrinking the range by exactly one element each pass, remember the index of the last swap. Everything after that index is already in order, so the next pass can stop there. On arrays whose tail is already sorted, this saves many comparisons.

Cocktail Shaker Sort

Cocktail shaker sort alternates direction. One pass carries the largest value to the right, and the next pass carries the smallest value to the left. It is still O(n²) in the worst case, but it handles small values near the end of the array better than plain bubble sort.

Why Small Values Move Slowly

In standard bubble sort, a large value can travel all the way to the end in one pass, but a small value near the end moves only one place left per pass. These slow small values are sometimes called turtles, and the fast large values rabbits. Try the array 2, 3, 4, 5, 1 in the visualization: the 1 needs four passes to reach the front, while an already sorted array finishes in a single pass.

When Bubble Sort Is Still Reasonable

Bubble sort is acceptable for tiny arrays, for teaching, and for quickly checking whether a short list is sorted with the early-exit flag. For anything larger, choose insertion sort for small or nearly sorted data, or an O(n log n) algorithm for general data.

How to Test a Bubble Sort Implementation

Test bubble sort with both correctness checks and counter checks.

Edge Cases to Try

• An empty array and a one-element array.
• An already sorted array.
• A reverse-sorted array.
• An array of equal values.
• An array with duplicates, such as [3, 1, 2, 3, 1, 2].

Check the Counters

For a reverse-sorted array of 10 items, bubble sort makes 45 comparisons and 45 swaps, which matches n(n − 1)/2. For an already sorted array of 10 items with the early-exit check, it makes only 9 comparisons and no swaps. Enter 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 as a custom array, press Run to completion, and compare the counters with these numbers.

Check Stability

Sort records by a key and confirm that records with equal keys keep their original order. Bubble sort passes this test when it swaps only on a strictly greater comparison.

Frequently Asked Questions About Bubble Sort

What is bubble sort in simple words?

It repeatedly compares neighbors and swaps them if they are in the wrong order, so large values drift to the end.

Is bubble sort stable?

Yes. It swaps only when the left element is strictly larger.

Is bubble sort in place?

Yes. It needs O(1) extra memory.

What is the time complexity of bubble sort?

O(n²) on average and in the worst case, and O(n) in the best case when the early-exit check is used.

Why is it called bubble sort?

Large values “bubble” toward the end of the array with each pass.

Is bubble sort ever a good choice?

Rarely. It suits teaching and tiny inputs. For real data, use a built-in sort or an O(n log n) algorithm.

How many passes does bubble sort need?

At most n − 1. With early exit it can finish sooner.

Conclusion

Bubble sort repeatedly swaps out-of-order neighbors until nothing moves. It is stable, in place and easy to understand, but its quadratic running time limits it to learning and tiny inputs. Use the visualization to compare a sorted array with a reverse-sorted one and see how the early-exit check changes the counters.