Bubble Sort Algorithm

Bubble Sort is one of the simplest sorting algorithms. It repeatedly compares neighboring elements and swaps them when they are in the wrong order.

What is Bubble Sort?

Bubble Sort is a comparison-based sorting algorithm that sorts an array by repeatedly comparing adjacent elements. If two neighboring elements are in the wrong order, the algorithm swaps them.

After each full pass through the array, the largest unsorted element moves to its correct position at the end. This is why the algorithm is called Bubble Sort: larger elements “bubble up” toward the end of the array.

Core Intuition

Imagine the array as a line of numbers. Bubble Sort only looks at two neighbors at a time.

If the left number is greater than the right number, they are out of order, so Bubble Sort swaps them. By doing this repeatedly, the largest number gradually moves to the far right.

Bubble Sort Algorithm Steps

1. Start from the beginning of the array.
   Compare the first pair of adjacent elements.
2. Swap if needed.
   If the left element is greater than the right element, swap them.
3. Move one position forward.
   Compare the next adjacent pair and repeat the same logic.
4. Complete one full pass.
   At the end of the first pass, the largest element is at its correct position.
5. Repeat for the remaining unsorted elements.
   Ignore the sorted suffix at the end and continue until the array is sorted.

Interactive Bubble Sort Visualization

Use the controls below to see how Bubble Sort compares adjacent elements, swaps them, and gradually builds the sorted part of the array from right to left.

Dry Run Example

Suppose we want to sort:

[5, 1, 4, 2, 8]

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 → [1, 4, 2, 5, 8]

At the end of Pass 1, the largest element, 8, is already in the correct position.

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 array is now sorted.

Bubble Sort Code in Python

This implementation includes a useful optimization: if a complete pass finishes without any swap, the array is already sorted, and the algorithm stops early.

def bubble_sort(nums):
    n = len(nums)

    for i in range(n):
        swapped = False

        # Last i elements are already in their correct positions.
        for j in range(0, n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True

        # If no swaps happened, the array is already sorted.
        if not swapped:
            break

    return nums


print(bubble_sort([5, 1, 4, 2, 8]))
# Output: [1, 2, 4, 5, 8]..

Time and Space Complexity

When Should You Use Bubble Sort?

Interview Notes and Common Pitfalls

This section highlights the key concepts interviewers expect you to understand, along with common mistakes that can cost you points during coding interviews.

What interviewers may expect you to know

• Bubble Sort repeatedly compares adjacent elements.
• After each pass, the largest unsorted element reaches its final position.
• Its average and worst-case time complexity is O(n²).
• It can be optimized with a swapped flag.
• It is stable because equal elements are not swapped out of their original order.
• It is in place because it does not require another array.

Common mistakes

• Looping too far and accessing nums[j + 1] out of bounds.
• Forgetting that the last i elements are already sorted after i passes.
• Claiming the best case is O(n²) even when using the early-stop optimization.
• Using Bubble Sort when a faster sorting algorithm is required.

Related coding interview problems

• Sort an Array
• Sort Colors
• Move Zeroes
• Merge Sorted Array
• Squares of a Sorted Array

Quick Quiz

Key Takeaways

• Bubble Sort compares adjacent elements and swaps them if they are out of order.
• Each pass places the largest remaining element in its final position.
• It is simple, stable, and in-place.
• Its average and worst-case time complexity is O(n²).
• It is best used for learning, not for optimized interview solutions.