Python bubble sort

Move the largest remaining item to the end with adjacent swaps.

Python

def bubble_sort(values):
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if result[i] > result[i + 1]:
                result[i], result[i + 1] = result[i + 1], result[i]
                swapped = True
        if not swapped:
            break
    return result

print(bubble_sort([3, 2, 1]))
assert bubble_sort([]) == []
assert bubble_sort([1, 1, 2]) == [1, 1, 2]

Output

[1, 2, 3]

Explanation

Each pass compares neighboring values and swaps an inverted pair. After a full pass, the largest value in the unsorted prefix is in its final position.

A swapped flag allows early exit when a pass makes no changes. Strict comparison keeps equal elements in their original relative order.

Explore the dry run

Guided walkthroughReady

1def bubble_sort(values):

2 result = values.copy()

3 for end in range(len(result) - 1, 0, -1):

4 swapped = False

5 for i in range(end):

6 if result[i] > result[i + 1]:

7 result[i], result[i + 1] = result[i + 1], result[i]

8 swapped = True

9 if not swapped:

10 break

11 return result

13print(bubble_sort([3, 2, 1]))

14assert bubble_sort([]) == []

15assert bubble_sort([1, 1, 2]) == [1, 1, 2]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Copy the input.	`result = [3, 2, 1]`	—
First pass swaps 3 and 2.	`result = [2, 3, 1]`	—
Then swap 3 and 1; the largest item is placed.	`result = [2, 1, 3]`	—
Second pass swaps 2 and 1.	`result = [1, 2, 3]`	—
Return and print the copy.	`result = [1, 2, 3]`	[1, 2, 3]

Cost and common mistakes

O(n²) worst-case time, O(n) best-case time with early exit; O(n) auxiliary space for this copying version.

The inner loop stops before end so i+1 remains valid.
Bubble sort is mainly educational; built-in sorting is preferable for ordinary use.

Try it yourself

Trace [1, 2, 3].

Reveal answer and reasoning

The first pass makes no swaps and exits early, returning the unchanged order.

Python bubble sort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading