Python Bubble Sort

Bubble sort is one of the simplest sorting algorithms to understand, which is exactly why it is usually the first sorting algorithm taught in programming courses. It works by repeatedly stepping through a list, comparing pairs of neighboring elements, and swapping them if they are in the wrong order. Larger values gradually “bubble” toward the end of the list with each pass, hence the name. While it is rarely used in production code because faster algorithms exist, understanding bubble sort builds the foundation for understanding sorting, algorithmic complexity, and optimization in general.

Overview: How Bubble Sort Works

Bubble sort is a comparison-based, in-place, stable sorting algorithm. It repeatedly scans a list from the beginning to the end, comparing each pair of adjacent elements. If a pair is out of order (the left element is greater than the right one, for ascending order), the two elements are swapped. After one full pass through the list, the largest unsorted element is guaranteed to be in its correct final position at the end. The algorithm then repeats this process for the remaining unsorted portion of the list, one element shorter each time, until no more swaps are needed.

In Python, a list stores references to objects rather than the objects themselves. When you write arr[j], arr[j + 1] = arr[j + 1], arr[j], Python builds a temporary tuple of the two references, then reassigns them to the opposite positions in the list. No data is copied or mutated — only the pointers stored in the list are rearranged. This is why bubble sort (and Python’s tuple-swap idiom in general) works uniformly for integers, strings, floats, or any other comparable object, and why it never needs a temporary variable the way swaps do in lower-level languages.

Because bubble sort only swaps elements when the left one is strictly greater than the right one (using >, not >=), equal elements are never swapped past each other. That means their relative order in the original list is preserved — this property is called stability, and it matters when you are sorting complex objects by one field but want ties to keep their original order.

The cost of this simplicity is speed: bubble sort compares roughly n * (n - 1) / 2 pairs in the worst case, giving it a time complexity of O(n2). For a list of 10,000 items, that is around 50 million comparisons — far more than the ~130,000 comparisons a good O(n log n) algorithm like Timsort (Python’s built-in sort) would need. Bubble sort should be treated as a learning tool, not a tool for real workloads.

Syntax

The general shape of a bubble sort function uses two nested loops: an outer loop that controls how many passes are made, and an inner loop that performs the adjacent comparisons and swaps for a single pass.

def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
Part Purpose
n = len(arr) Caches the list length so it isn’t recomputed every iteration.
for i in range(n - 1) Controls the number of passes. After n - 1 passes the list is guaranteed sorted.
for j in range(n - 1 - i) Scans the unsorted portion of the list. It shrinks by one each pass because the last i elements are already in their final sorted position.
if arr[j] > arr[j + 1] Compares two adjacent elements; change to < for descending order.
arr[j], arr[j + 1] = arr[j + 1], arr[j] Swaps the two elements using Python’s tuple-assignment idiom.
return arr Returns the sorted list. Since sorting happens in place, this is the same object that was passed in.

Examples

Example 1: Basic ascending sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)

Output:
[11, 12, 22, 25, 34, 64, 90]

Each outer-loop pass pushes the current largest unsorted value to its final position. On the first pass, 90 bubbles all the way to the end; on the second pass, 64 settles into place, and so on, until the whole list is ordered.

Example 2: Optimized version with early exit

If a pass completes with no swaps, the list is already sorted, and there is no point continuing. Tracking this with a boolean flag turns the best case into O(n) instead of always running the full O(n2) work.

def bubble_sort_optimized(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr


data = [5, 1, 4, 2, 8]
print(f"Before: {data}")
result = bubble_sort_optimized(data)
print(f"After: {result}")

Output:
Before: [5, 1, 4, 2, 8]
After: [1, 2, 4, 5, 8]

Note that data and result refer to the exact same list object — bubble sort mutates the input in place and also returns it, which is convenient but has a gotcha covered in the Common Mistakes section below.

Example 3: Descending sort with strings

Bubble sort works on any type that supports comparison operators, including strings. Flipping the comparison operator reverses the sort order.

def bubble_sort_descending(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


names = ["Mercury", "Venus", "Earth", "Mars", "Jupiter"]
print(bubble_sort_descending(names))

Output:
['Venus', 'Mercury', 'Mars', 'Jupiter', 'Earth']

Using < instead of > means an element is only swapped when it is smaller than its right neighbor, so the smallest elements now bubble toward the end and the largest ones (alphabetically last) end up first.

How It Works Step by Step (Under the Hood)

It helps to watch the array change after every pass. The following trace prints the list’s state after each outer-loop iteration:

def bubble_sort_trace(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        print(f"After pass {i + 1}: {arr}")
        if not swapped:
            break


bubble_sort_trace([5, 3, 8, 1, 2])

Output:
After pass 1: [3, 5, 1, 2, 8]
After pass 2: [3, 1, 2, 5, 8]
After pass 3: [1, 2, 3, 5, 8]
After pass 4: [1, 2, 3, 5, 8]

Notice two things. First, 8 reaches its final position after just one pass, because it started as the largest value and kept getting swapped rightward until it hit the end. Second, the list is actually fully sorted after pass 3, but the algorithm cannot know that until it runs one more pass (pass 4) and finds zero swaps — that is exactly what the swapped flag detects, letting the loop break early instead of running unnecessary comparisons.

Case Comparisons Time Complexity
Worst (reverse sorted) ~n2/2 O(n2)
Average (random order) ~n2/2 O(n2)
Best (already sorted, with early-exit flag) n – 1 O(n)

Space complexity is O(1) extra space, since swaps happen directly inside the original list with no auxiliary array required.

Common Mistakes

Mistake 1: Skipping the early-exit optimization

The plain version of bubble sort (Example 1) always performs the full n - 1 outer-loop passes, even if the list becomes sorted after the very first pass. On a nearly-sorted list of a few thousand items, this wastes a large number of comparisons for no benefit. Always add the swapped flag shown in Example 2 unless you have a specific reason not to.

Mistake 2: Assuming the original list is left untouched

Because bubble sort swaps elements directly inside the list you pass in, the caller’s original list is modified as a side effect — even though the function also returns it. This surprises people who expect a “sort” function to behave like sorted(), which returns a new list and leaves the original alone.

original = [4, 2, 7, 1]


def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


sorted_list = bubble_sort(original)
print(original)

Output:
[1, 2, 4, 7]

Even though only sorted_list was printed for in the code’s intent, original was mutated too, since sorted_list and original point to the very same list object. If you need to keep the input untouched, copy it first:

def bubble_sort_safe(arr):
    arr = arr.copy()
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


original = [4, 2, 7, 1]
sorted_copy = bubble_sort_safe(original)
print(f"Original: {original}")
print(f"Sorted:   {sorted_copy}")

Output:
Original: [4, 2, 7, 1]
Sorted:   [1, 2, 4, 7]

Mistake 3: Getting the inner-loop range wrong

A very common bug is writing the inner loop as for j in range(n - 1) instead of for j in range(n - 1 - i). Using a fixed range that never shrinks means the loop keeps comparing arr[j] with arr[j + 1] all the way to the last index on every pass, which itself won’t crash, but it does throw away the whole point of shrinking the unsorted region and makes the early-exit optimization far less effective since more redundant comparisons run each pass. An even worse variant, for j in range(n - i), will raise an IndexError: list index out of range on the final iteration of the last pass, because arr[j + 1] would try to access an index equal to len(arr). Always double-check that the inner bound is n - 1 - i, not n - i or a constant n - 1.

Best Practices

  • Use Python’s built-in sorted() or list.sort() for real-world code — both use Timsort, which runs in O(n log n) and is heavily optimized in C.
  • Reserve bubble sort for teaching, algorithm interviews, or genuinely tiny lists where simplicity matters more than speed.
  • Always implement the swapped early-exit flag; it costs almost nothing and turns the best case into O(n).
  • Be explicit about mutation: either document that your function sorts in place, or call arr.copy() at the top if callers expect their original list to remain unchanged.
  • Use the tuple-swap idiom arr[j], arr[j + 1] = arr[j + 1], arr[j] instead of a manual temporary variable — it’s the idiomatic, more readable Python way to swap.
  • Add type hints (def bubble_sort(arr: list) -> list:) to make the function’s contract clear.
  • Test edge cases explicitly: an empty list, a single-element list, an already-sorted list, a reverse-sorted list, and a list with duplicate values.
  • If you need a custom sort order, consider generalizing with a key function or a comparison callback, similar to how sorted(items, key=...) works, rather than hardcoding > or <.

Practice Exercises

Exercise 1: Write a function bubble_sort_desc(arr) that sorts a list in descending order using bubble sort, without calling sorted() or reverse(). Test it on [3, 7, 1, 9, 4] and confirm the output is [9, 7, 4, 3, 1].

Exercise 2: Modify the optimized bubble sort so it returns a tuple (sorted_list, swap_count), where swap_count is the total number of swaps performed across all passes. Run it on [4, 2, 2, 8, 1] and check how many swaps occur.

Exercise 3: Given a list of (name, score) tuples, such as [("Ana", 90), ("Bo", 75), ("Cy", 90), ("Di", 60)], use bubble sort to sort by score descending. Because bubble sort is stable, verify that "Ana" still appears before "Cy" in the result, since they tie on score and "Ana" came first originally.

Summary

  • Bubble sort repeatedly compares and swaps adjacent elements, letting the largest remaining value “bubble” to the end of the list on each pass.
  • It is simple, stable, and sorts in place using O(1) extra space, but runs in O(n2) time in the average and worst case.
  • Adding a swapped flag lets the algorithm exit early once a pass makes no swaps, improving the best case to O(n).
  • Because it mutates the input list directly, callers should copy the list first if the original must remain unchanged.
  • The inner loop’s range must shrink as n - 1 - i; getting this bound wrong causes redundant work or an IndexError.
  • For production code, prefer Python’s built-in sorted() or list.sort(), which use the much faster Timsort algorithm.