Bubble Sort Algorithm

Bubble Sort Algorithm Explained

Bubble Sort is one of the simplest sorting algorithms in computer science. It works by repeatedly comparing two adjacent elements and swapping them if they are in the wrong order. After each full pass through the array, the largest unsorted element moves to its correct position at the end of the array.

Although Bubble Sort is not efficient for large datasets, it is very useful for beginners because it explains important algorithmic ideas such as comparison, swapping, iteration, optimization, best-case behavior, worst-case behavior, and time complexity.

Introduction

Sorting is one of the most common operations in programming. Developers sort numbers, names, dates, prices, products, database results, scores, logs, and many other types of data. Because sorting appears frequently in real software projects, learning sorting algorithms helps developers understand how data can be organized and processed efficiently.

Bubble Sort is usually one of the first sorting algorithms taught to beginners. The reason is not that it is the fastest algorithm, but that its logic is easy to visualize. The algorithm compares neighboring values, swaps them when needed, and repeats this process until the array becomes sorted.

Understanding Bubble Sort also helps developers understand why algorithm efficiency matters. A solution may be correct, but still slow when the input size becomes large. This is why Bubble Sort is a good starting point for learning time complexity and Big O notation.

What Is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm. It compares adjacent elements in an array and swaps them if they are not in the correct order.

For ascending order, Bubble Sort checks whether the left element is greater than the right element. If it is greater, the two elements are swapped. This process is repeated many times until all elements are sorted from smallest to largest.

The name Bubble Sort comes from the way large values gradually move, or bubble, toward the end of the array. After one complete pass, the largest value reaches its final position. After the next pass, the second largest value reaches its final position, and so on.

Core Idea of Bubble Sort

The core idea of Bubble Sort is simple:

• Compare two neighboring elements.

• If they are in the wrong order, swap them.

• Move one position forward and repeat.

• After one full pass, the largest unsorted value is placed correctly.

• Repeat the process until the whole array is sorted.

This makes Bubble Sort easy to understand, but not very efficient for large arrays because it performs many repeated comparisons.

Bubble Sort in Simple Words

Imagine a row of numbers. Bubble Sort starts from the left side and compares each pair of neighboring numbers. If the first number is bigger than the second number, they change places.

When the algorithm reaches the end of the row, the biggest number has moved to the last position. Then the algorithm starts again from the beginning, but this time it does not need to check the last number because it is already sorted.

This process continues until no more swaps are needed, or until the algorithm completes all required passes.

Bubble Sort Algorithm Steps

For sorting an array in ascending order, Bubble Sort follows these steps:

1. Start from the first element of the array.

2. Compare the current element with the next element.

3. If the current element is greater than the next element, swap them.

4. Move to the next pair of elements.

5. Continue until the end of the unsorted part of the array.

6. Repeat the process for multiple passes.

7. Stop when the array is sorted.

The algorithm can be improved by stopping early if a full pass finishes without any swaps. This means the array is already sorted.

Manual Run Example

To understand Bubble Sort clearly, let us manually sort this array in ascending order:

[5, 1, 4, 2, 8]

The goal is to reorder the array from smallest to largest:

[1, 2, 4, 5, 8]

Pass 1

Initial array:

[5, 1, 4, 2, 8]

After the first pass, the largest value, 8, is already in its correct final position.

Pass 2

Array before pass 2:

[1, 4, 2, 5, 8]

After the second pass, the second largest value, 5, is also in its correct final position.

Pass 3

Array before pass 3:

[1, 2, 4, 5, 8]

No swaps happened in this pass. This means the array is already sorted. An optimized Bubble Sort can stop here instead of continuing unnecessary passes.

Final Sorted Array

The final sorted array is:

[1, 2, 4, 5, 8]

This manual run shows how larger elements move step by step toward the end of the array. It also shows why the optimized version can stop early when no swaps happen during a pass.

Bubble Sort Pseudocode

Pseudocode helps explain the algorithm without focusing on a specific programming language.

repeat for each pass:
    swapped = false

    compare each adjacent pair in the unsorted part:
        if left element is greater than right element:
            swap them
            swapped = true

    if swapped is false:
        stop because the array is already sorted

The important part is the swapped flag. It helps the algorithm detect whether the array is already sorted before all passes are completed.

Bubble Sort Example in PHP

The following example implements Bubble Sort in PHP. It sorts an array of numbers in ascending order.

<?php

declare(strict_types=1);

function bubbleSort(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                $temporary = $numbers[$j];
                $numbers[$j] = $numbers[$j + 1];
                $numbers[$j + 1] = $temporary;
            }
        }
    }

    return $numbers;
}

$values = [5, 1, 4, 2, 8];
$sortedValues = bubbleSort($values);

print_r($sortedValues);

Output:

Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 8
)

This version is correct, but it continues running even if the array becomes sorted before all passes are completed.

Optimized Bubble Sort in PHP

The optimized version uses a boolean variable named swapped. If a complete pass finishes without any swap, the algorithm stops early.

<?php

declare(strict_types=1);

function optimizedBubbleSort(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;

        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                [$numbers[$j], $numbers[$j + 1]] = [$numbers[$j + 1], $numbers[$j]];
                $swapped = true;
            }
        }

        if ($swapped === false) {
            break;
        }
    }

    return $numbers;
}

$values = [5, 1, 4, 2, 8];
$sortedValues = optimizedBubbleSort($values);

print_r($sortedValues);

This version is better for arrays that are already sorted or nearly sorted. In the best case, it can finish after only one pass.

Bubble Sort Example in JavaScript

The same idea can be implemented in JavaScript. The syntax changes, but the algorithm remains the same.

function bubbleSort(numbers) {
    const result = [...numbers];
    const count = result.length;

    for (let i = 0; i < count - 1; i++) {
        let swapped = false;

        for (let j = 0; j < count - i - 1; j++) {
            if (result[j] > result[j + 1]) {
                const temporary = result[j];
                result[j] = result[j + 1];
                result[j + 1] = temporary;
                swapped = true;
            }
        }

        if (!swapped) {
            break;
        }
    }

    return result;
}

const values = [5, 1, 4, 2, 8];
console.log(bubbleSort(values));

Output:

[1, 2, 4, 5, 8]

This JavaScript example creates a copy of the original array before sorting. This keeps the original input unchanged, which can be useful in many applications.

Why the Inner Loop Gets Shorter

In Bubble Sort, after each pass, one large element reaches its final position at the end of the array. Because of that, the algorithm does not need to compare that final sorted part again.

This is why the inner loop uses this condition:

$j < $count - $i - 1

When $i increases, the number of comparisons decreases. This avoids checking elements that are already known to be sorted.

Time Complexity of Bubble Sort

Time complexity describes how the running time of an algorithm grows as the input size grows. If an array has n elements, Bubble Sort may need to compare many pairs of elements.

The time complexity of Bubble Sort depends on the input order and whether the optimized version is used.

The best case is only O(n) when the optimized version is used. Without the swapped flag, Bubble Sort usually remains O(n²) even when the array is already sorted because it still performs unnecessary passes.

Best-Case Time Complexity

The best case happens when the input array is already sorted.

[1, 2, 3, 4, 5]

In the optimized version, Bubble Sort makes one pass through the array and finds that no swaps are needed. Since no swaps happen, the algorithm stops immediately.

For an array of n elements, one pass needs about n - 1 comparisons. Therefore, the best-case time complexity is:

O(n)

This makes optimized Bubble Sort acceptable for very small or nearly sorted arrays, but it still should not be used as the default sorting solution in real applications.

Average-Case Time Complexity

The average case happens when the array elements are in random order.

[4, 1, 5, 2, 3]

In this situation, Bubble Sort usually performs multiple passes. Some elements need to move several positions before they reach their correct place.

The number of comparisons grows roughly with the square of the input size. Therefore, the average-case time complexity is:

O(n²)

This means that when the input size doubles, the amount of work can grow much more than double. For large datasets, this becomes inefficient.

Worst-Case Time Complexity

The worst case happens when the array is sorted in reverse order.

[5, 4, 3, 2, 1]

In this case, every adjacent pair is in the wrong order. The algorithm must perform many swaps to move each element to its correct position.

The total number of comparisons in the standard Bubble Sort approach is:

(n - 1) + (n - 2) + (n - 3) + ... + 1

This sum equals:

n × (n - 1) / 2

When Big O notation is used, constants and smaller terms are removed. So the worst-case time complexity becomes:

O(n²)

This is the main reason Bubble Sort is not suitable for large datasets.

Space Complexity of Bubble Sort

Space complexity describes how much extra memory an algorithm needs. Bubble Sort can sort the array in place, meaning it does not need another array to store the sorted result.

It only needs a few extra variables, such as loop counters and a temporary variable for swapping. Therefore, the space complexity of Bubble Sort is:

O(1)

This means Bubble Sort uses constant extra memory regardless of the input size.

Is Bubble Sort Stable?

Bubble Sort is a stable sorting algorithm when implemented correctly. Stability means that equal elements keep their original relative order after sorting.

For example, if two students have the same score, a stable sorting algorithm keeps them in the same relative order they had before sorting.

Bubble Sort remains stable because it swaps elements only when the left element is greater than the right element. It does not swap equal elements.

if ($numbers[$j] > $numbers[$j + 1]) {
    // swap only when left value is greater
}

If the condition used >= instead of >, equal elements might be swapped, and the algorithm could lose stability.

Is Bubble Sort In-Place?

Bubble Sort is an in-place sorting algorithm when it modifies the original array directly. This means it does not require a second array proportional to the input size.

The PHP example above returns a sorted copy because arrays in PHP are passed by value by default. However, the algorithmic idea itself can be implemented in place by modifying the same array.

Being in-place is useful when memory is limited, but Bubble Sort is still slow compared with more efficient sorting algorithms.

Bubble Sort for Descending Order

Bubble Sort can also sort values in descending order. The only change is the comparison condition.

For ascending order, swap when the left element is greater than the right element:

if ($numbers[$j] > $numbers[$j + 1])

For descending order, swap when the left element is smaller than the right element:

if ($numbers[$j] < $numbers[$j + 1])

Here is a simple PHP example for descending order:

<?php

declare(strict_types=1);

function bubbleSortDescending(array $numbers): array
{
    $count = count($numbers);

    for ($i = 0; $i < $count - 1; $i++) {
        $swapped = false;

        for ($j = 0; $j < $count - $i - 1; $j++) {
            if ($numbers[$j] < $numbers[$j + 1]) {
                [$numbers[$j], $numbers[$j + 1]] = [$numbers[$j + 1], $numbers[$j]];
                $swapped = true;
            }
        }

        if ($swapped === false) {
            break;
        }
    }

    return $numbers;
}

Common Mistakes When Implementing Bubble Sort

Beginners often understand the general idea of Bubble Sort, but still make small implementation mistakes. These mistakes can cause incorrect output, unnecessary comparisons, or even runtime errors.

Common mistakes include:

• Using the wrong comparison operator for ascending or descending order.

• Forgetting to reduce the inner loop after each pass.

• Accessing an invalid index such as $numbers[$j + 1] when $j is already at the last index.

• Forgetting to reset the swapped flag at the beginning of each pass.

• Using Bubble Sort for large datasets in real applications.

• Thinking that Bubble Sort is efficient because it is easy to write.

The most important point is to understand the loop boundaries. Bubble Sort compares each element with the next element, so the inner loop must stop before the last unchecked index.

When Should You Use Bubble Sort?

Bubble Sort is useful mainly for learning and teaching. It helps beginners understand how sorting works internally and how algorithms can be analyzed.

Bubble Sort may be acceptable when:

• The dataset is very small.

• The array is already sorted or almost sorted.

• The goal is educational, not performance-based.

• You want to demonstrate swapping and nested loops.

• You want to explain best, average, and worst-case complexity.

In professional projects, developers usually use built-in sorting functions or more efficient algorithms instead of Bubble Sort.

When Not to Use Bubble Sort

Bubble Sort should not be used when performance matters. It becomes slow as the input size grows because its average and worst-case time complexity is O(n²).

Avoid Bubble Sort when:

• The dataset contains many elements.

• The application needs fast sorting.

• The code runs frequently in production.

• The sorting operation affects user experience.

• A built-in optimized sorting function is available.

For example, in PHP, functions such as sort(), usort(), asort(), and ksort() are usually better choices for real projects.

Bubble Sort Compared with Better Sorting Algorithms

Bubble Sort is simple, but it is not competitive with more efficient sorting algorithms. Algorithms such as Merge Sort, Quick Sort, and Heap Sort are usually much faster for larger datasets.

This comparison shows why Bubble Sort is important for learning, but not usually selected for production-level sorting.

Bubble Sort and Big O Notation

Bubble Sort is a practical example for understanding Big O notation. Big O does not measure exact execution time in seconds. Instead, it describes how the number of operations grows as the input size increases.

For small arrays, Bubble Sort may seem fast. But when the input size grows, the number of comparisons grows quickly.

This growth explains why O(n²) algorithms can become expensive quickly.

Practical Checklist for Understanding Bubble Sort

Before moving to more advanced sorting algorithms, make sure you understand the following points:

• Bubble Sort compares adjacent elements.

• It swaps elements when they are in the wrong order.

• After each pass, one element reaches its final sorted position.

• The inner loop becomes shorter after each pass.

• The optimized version can stop early if no swaps happen.

• The best-case time complexity is O(n) only with optimization.

• The average and worst-case time complexity is O(n²).

• The space complexity is O(1).

• Bubble Sort is stable when equal elements are not swapped.

• Bubble Sort is mainly useful for learning, not large production datasets.

Conclusion

Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and swaps them when they are in the wrong order. Its logic is easy to follow, which makes it a useful algorithm for beginners who want to understand sorting, nested loops, swapping, and algorithm analysis.

The manual run shows how the largest values gradually move to the end of the array after each pass. The optimized version improves the best-case performance by stopping early when no swaps are needed.

From a complexity perspective, Bubble Sort has a best-case time complexity of O(n) when optimized, but its average and worst-case time complexity is O(n²). Its space complexity is O(1) because it can sort data in place using only a small amount of extra memory.

In real software projects, Bubble Sort is rarely the best choice for performance. However, it remains an excellent educational algorithm because it teaches the foundation of sorting and prepares developers to understand more advanced algorithms such as Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.