Python Program for Bubble Sort with Example and Explanation

A Python program for bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order using nested loops, like for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j].

Examples

Input[5, 2, 9, 1]

Output[1, 2, 5, 9]

Input[3, 3, 2, 1]

Output[1, 2, 3, 3]

Input[]

Output[]

How to Think About It

To sort a list using bubble sort, think of repeatedly passing through the list and comparing each pair of neighbors. If a pair is out of order, swap them. Each pass moves the largest unsorted number to its correct place at the end. Repeat until no swaps are needed.

Algorithm

1

Get the list of numbers to sort.

2

Repeat for each element in the list:

3

Compare each pair of adjacent elements.

4

If the left element is greater than the right, swap them.

5

After each full pass, the largest unsorted element moves to the end.

6

Stop when no swaps happen in a full pass.

Code

python

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

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

Output

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

Dry Run

Let's trace the list [5, 2, 9, 1] through the bubble sort code.

1

Initial list

[5, 2, 9, 1]

2

First pass comparisons and swaps

Compare 5 and 2, swap -> [2, 5, 9, 1]; Compare 5 and 9, no swap; Compare 9 and 1, swap -> [2, 5, 1, 9]

3

Second pass comparisons and swaps

Compare 2 and 5, no swap; Compare 5 and 1, swap -> [2, 1, 5, 9]

4

Third pass comparisons and swaps

Compare 2 and 1, swap -> [1, 2, 5, 9]

5

Sorted list

[1, 2, 5, 9]

Pass	List after pass
1	[2, 5, 1, 9]
2	[2, 1, 5, 9]
3	[1, 2, 5, 9]

Why This Works

Step 1: Compare adjacent elements

The code uses nested loops to compare each pair of neighbors with if arr[j] > arr[j+1].

Step 2: Swap if out of order

If the left element is bigger, it swaps places with the right one using arr[j], arr[j+1] = arr[j+1], arr[j].

Step 3: Repeat passes

Each outer loop pass moves the largest unsorted element to the end, shrinking the unsorted part.

Alternative Approaches

Optimized bubble sort with early stop

python

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

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

Stops early if no swaps happen, improving performance on nearly sorted lists.

Using Python's built-in sort

python

numbers = [64, 34, 25, 12, 22, 11, 90]
numbers.sort()
print(numbers)

Much faster and simpler, but does not teach the bubble sort algorithm.

Complexity: O(n^2) time, O(1) space

Time Complexity

Bubble sort uses nested loops over the list, leading to O(n^2) time because each element is compared multiple times.

Space Complexity

It sorts the list in place, so it uses O(1) extra space.

Which Approach is Fastest?

The optimized bubble sort can stop early, improving best-case time to O(n), but built-in sorts like Timsort are much faster overall.

Approach	Time	Space	Best For
Basic Bubble Sort	O(n^2)	O(1)	Learning sorting basics
Optimized Bubble Sort	O(n) best, O(n^2) worst	O(1)	Nearly sorted lists
Python Built-in Sort	O(n log n)	O(n)	All practical sorting needs