Bubble Sort - Python Programming

Organizing data in order is fundamental to computing, from displaying search results to preparing data for efficient lookup. Bubble sort is one of the simplest sorting algorithms to understand and implement, making it an excellent starting point for learning how sorting works, even though faster algorithms exist for production use.

Counting Comparisons

basic.py

# Basic bubble sort


def bubble_sort(arr):
    """Bubble sort implementation"""
    n = len(arr)

    # Bubble sort implementation
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


# Test bubble sort
numbers = 

print("Before:", numbers)
bubble_sort(numbers)
print("After: ", numbers)

# Basic bubble sort


def bubble_sort(arr):
    """Bubble sort implementation"""
    n = len(arr)

    # Bubble sort implementation
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


# Test bubble sort
numbers = 

print("Before:", numbers)
bubble_sort(numbers)
print("After: ", numbers)

# Basic bubble sort


def bubble_sort(arr):
    """Bubble sort implementation"""
    n = len(arr)

    # Bubble sort implementation
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


# Test bubble sort
numbers = 

print("Before:", numbers)
bubble_sort(numbers)
print("After: ", numbers)

trace.py

# Bubble sort with trace


def bubble_sort_trace(arr):
    """Bubble sort with step-by-step trace"""
    n = len(arr)

    # Trace each pass
    for i in range(n - 1):
        print(f"Pass {i + 1}:")
        swapped = False

        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                print(f"  Swap {arr[j]} and {arr[j + 1]}")
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        print(f"  Result: {arr}")

        if not swapped:
            print("  No swaps - array is sorted!")
            break


# Test with trace
numbers = [5, 2, 8, 1, 9]

print("Initial:", numbers)
print()
bubble_sort_trace(numbers)

optimized.py

# Optimized bubble sort


def bubble_sort_optimized(arr):
    """Optimized bubble sort with early termination"""
    n = len(arr)
    passes = 0

    # Optimized with early termination
    for i in range(n - 1):
        passes += 1
        swapped = False

        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True

        # If no swaps, array is sorted
        if not swapped:
            break

    return passes


# Test on different inputs
almost_sorted = [1, 2, 3, 5, 4, 6, 7, 8]
reversed_list = [8, 7, 6, 5, 4, 3, 2, 1]

print("Almost sorted:")
print("Before:", almost_sorted)
passes1 = bubble_sort_optimized(almost_sorted)
print("After: ", almost_sorted)
print("Passes:", passes1)

print("\nReverse sorted:")
print("Before:", reversed_list)
passes2 = bubble_sort_optimized(reversed_list)
print("After: ", reversed_list)
print("Passes:", passes2)

descending.py

# Sort descending


def bubble_sort_ascending(arr):
    """Sort in ascending order"""
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            # Ascending: swap if left > right
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


def bubble_sort_descending(arr):
    """Sort in descending order"""
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            # Descending: swap if left < right
            if arr[j] < arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


# Test both directions
numbers1 = [64, 34, 25, 12, 22]
numbers2 = [64, 34, 25, 12, 22]

bubble_sort_ascending(numbers1)
print("Ascending: ", numbers1)

bubble_sort_descending(numbers2)
print("Descending:", numbers2)

comparison_count.py

# Count comparisons and swaps


def bubble_sort_counted(arr):
    """Bubble sort that counts operations"""
    n = len(arr)
    comparisons = 0
    swaps = 0

    # Count operations
    for i in range(n - 1):
        for j in range(n - i - 1):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                swaps += 1
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

    return comparisons, swaps


# Test on different inputs
sorted_list = [1, 2, 3, 4, 5]
reversed_list = [5, 4, 3, 2, 1]
random_list = [3, 1, 4, 2, 5]

comp1, swap1 = bubble_sort_counted(sorted_list.copy())
print(f"Already sorted: {comp1} comparisons, {swap1} swaps")

comp2, swap2 = bubble_sort_counted(reversed_list.copy())
print(f"Reverse sorted: {comp2} comparisons, {swap2} swaps")

comp3, swap3 = bubble_sort_counted(random_list.copy())
print(f"Random order:   {comp3} comparisons, {swap3} swaps")

Characteristics

Time complexity: O(n^2) - two nested loops
Space complexity: O(1) - sorts in place
Stable: equal elements maintain relative order
Best case: O(n) - already sorted with optimization
Worst case: O(n^2) - reverse sorted

When to Use

Teaching sorting concepts
Small datasets
Nearly sorted data with optimization
When simplicity is more important than speed

adjacent_swap Compare neighboring elements and swap if out of order

early_termination Stop early if no swaps occur in a pass, meaning list is sorted

quadratic_time O(n^2) means doubling the data quadruples the time

Exercise: practical.py

Implement bubble sort to sort a list of student records by grade, preserving the original order for students with the same grade