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.

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Larger elements "bubble up" to the end.

Algorithm

Repeat for each element:
- Compare adjacent pairs
- If out of order, swap them
After each pass, the largest unsorted element is in its final position
Repeat until no swaps are made

adjacent_swap Compare neighboring elements and swap if out of order

Basic Implementation

                            numbers
                            numbers = [64, 34, 25, 12, 22, 11, 90] (default)numbers = [5, 1, 4, 2, 8]numbers = [3, 2, 1]
                        

                            basic.py
                        
Replay: real traced execution (multi-file project)

                            # 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 = [64, 34, 25, 12, 22, 11, 90]

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

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 = [3, 2, 1]

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


                        
1numbers ← [64, 34, 25, 12, 22, 11, 90]⋯16# Test bubble sort17numbers→ [64, 34, 25, 12, 22, 11, 90] = [64, 34, 25, 12, 22, 11, 90]18#@numbers=[5, 1, 4, 2, 8], [3, 2, 1]1920print("Before:", numbers[64, 34, 25, 12, 22, 11, 90])21bubble_sort(numbers[64, 34, 25, 12, 22, 11, 90])22print("After: ", numbers)⋯outputBefore: [64, 34, 25, 12, 22, 11, 90]
2n ← 7⋯4def bubble_sort(arr[64, 34, 25, 12, 22, 11, 90]):5    """Bubble sort implementation"""6    n→ 7 = len(arr[64, 34, 25, 12, 22, 11, 90])⋯
3for i in range(n - 1):pass 1 of 6⋯8# Bubble sort implementation9for i0 in range(n7 - 1):10    for j in range(n - i - 1):11        if arr[j] > arr[j + 1]:⋯All 6 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
4for j in range(n - i - 1):pass 1 of 21⋯9for i in range(n - 1):10    for j0 in range(n7 - i0 - 1):11        if arr[j] > arr[j + 1]:12            # Swap⋯21 passes — pass 1 is the card abovepassji
100
210
320
430
540
650
701
811
921
⋯ 10 more passes ⋯
2014
2105
5arr[j] ← 34, arr[j + 1] ← 64pass 1 of 14⋯10for j in range(n - i - 1):11    if arr[j]64 > arr[j + 1]34:12        # Swap13        arr[j]→ 34, arr[j + 1]→ 64 = arr[j + 1], arr[j]⋯14 passes — pass 1 is the card abovepassarr[j]arr[j + 1]
164 → 3434 → 64
264 → 2525 → 64
364 → 1212 → 64
464 → 2222 → 64
564 → 1111 → 64
634 → 2525 → 34
734 → 1212 → 34
834 → 2222 → 34
934 → 1111 → 34
⋯ 3 more passes ⋯
1322 → 1111 → 22
1412 → 1111 → 12
6numbers ← [11, 12, 22, 25, 34, 64, 90]⋯20print("Before:", numbers)21bubble_sort(numbers→ [11, 12, 22, 25, 34, 64, 90])22print("After: ", numbers[11, 12, 22, 25, 34, 64, 90])⋯outputAfter:  [11, 12, 22, 25, 34, 64, 90]
1numbers ← [5, 1, 4, 2, 8]⋯16# Test bubble sort17numbers→ [5, 1, 4, 2, 8] = [5, 1, 4, 2, 8]1819print("Before:", numbers[5, 1, 4, 2, 8])20bubble_sort(numbers[5, 1, 4, 2, 8])21print("After: ", numbers)⋯outputBefore: [5, 1, 4, 2, 8]
2n ← 5⋯4def bubble_sort(arr[5, 1, 4, 2, 8]):5    """Bubble sort implementation"""6    n→ 5 = len(arr[5, 1, 4, 2, 8])⋯
3for i in range(n - 1):pass 1 of 4⋯8# Bubble sort implementation9for i0 in range(n5 - 1):10    for j in range(n - i - 1):11        if arr[j] > arr[j + 1]:⋯All 4 passes — pass 1 is the card abovepassi
10
21
32
43
4for j in range(n - i - 1):pass 1 of 10⋯9for i in range(n - 1):10    for j0 in range(n5 - i0 - 1):11        if arr[j] > arr[j + 1]:12            # Swap⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5arr[j] ← 1, arr[j + 1] ← 5pass 1 of 4⋯10for j in range(n - i - 1):11    if arr[j]5 > arr[j + 1]1:12        # Swap13        arr[j]→ 1, arr[j + 1]→ 5 = arr[j + 1], arr[j]⋯All 4 passes — pass 1 is the card abovepassarr[j]arr[j + 1]
15 → 11 → 5
25 → 44 → 5
35 → 22 → 5
44 → 22 → 4
6numbers ← [1, 2, 4, 5, 8]⋯19print("Before:", numbers)20bubble_sort(numbers→ [1, 2, 4, 5, 8])21print("After: ", numbers[1, 2, 4, 5, 8])⋯outputAfter:  [1, 2, 4, 5, 8]
1numbers ← [3, 2, 1]⋯16# Test bubble sort17numbers→ [3, 2, 1] = [3, 2, 1]1819print("Before:", numbers[3, 2, 1])20bubble_sort(numbers[3, 2, 1])21print("After: ", numbers)⋯outputBefore: [3, 2, 1]
2n ← 3⋯4def bubble_sort(arr[3, 2, 1]):5    """Bubble sort implementation"""6    n→ 3 = len(arr[3, 2, 1])⋯
3for i in range(n - 1):pass 1 of 2⋯8# Bubble sort implementation9for i0 in range(n3 - 1):10    for j in range(n - i - 1):11        if arr[j] > arr[j + 1]:⋯
4for j in range(n - i - 1):pass 1 of 3⋯9for i in range(n - 1):10    for j0 in range(n3 - i0 - 1):11        if arr[j] > arr[j + 1]:12            # Swap⋯All 3 passes — pass 1 is the card abovepassji
100
210
301
5arr[j] ← 2, arr[j + 1] ← 3pass 1 of 3⋯10for j in range(n - i - 1):11    if arr[j]3 > arr[j + 1]2:12        # Swap13        arr[j]→ 2, arr[j + 1]→ 3 = arr[j + 1], arr[j]⋯All 3 passes — pass 1 is the card abovepassinarr[j]arr[j + 1]
1——3 → 22 → 3
2133 → 11 → 3
3——2 → 11 → 2
6for i in range(n - 1):pass 2 of 2⋯8# Bubble sort implementation9for i1 in range(n3 - 1):10    for j in range(n - i - 1):11        if arr[j] > arr[j + 1]:⋯
7numbers ← [1, 2, 3]⋯19print("Before:", numbers)20bubble_sort(numbers→ [1, 2, 3])21print("After: ", numbers[1, 2, 3])⋯outputAfter:  [1, 2, 3]

All 6 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	4
6	5

21 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	4	0
6	5	0
7	0	1
8	1	1
9	2	1
⋯ 10 more passes ⋯
20	1	4
21	0	5

14 passes — pass 1 is the card above
pass	`arr[j]`	`arr[j + 1]`
1	64 → 34	34 → 64
2	64 → 25	25 → 64
3	64 → 12	12 → 64
4	64 → 22	22 → 64
5	64 → 11	11 → 64
6	34 → 25	25 → 34
7	34 → 12	12 → 34
8	34 → 22	22 → 34
9	34 → 11	11 → 34
⋯ 3 more passes ⋯
13	22 → 11	11 → 22
14	12 → 11	11 → 12

All 4 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 4 passes — pass 1 is the card above
pass	`arr[j]`	`arr[j + 1]`
1	5 → 1	1 → 5
2	5 → 4	4 → 5
3	5 → 2	2 → 5
4	4 → 2	2 → 4

All 3 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	0	1

All 3 passes — pass 1 is the card above
pass	`i`	`n`	`arr[j]`	`arr[j + 1]`
1	—	—	3 → 2	2 → 3
2	1	3	3 → 1	1 → 3
3	—	—	2 → 1	1 → 2

Trace Example

                            trace.py
                        
Replay: real traced execution (multi-file project)

                            # 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)


                        
1numbers ← [5, 2, 8, 1, 9]⋯26# Test with trace27numbers→ [5, 2, 8, 1, 9] = [5, 2, 8, 1, 9]2829print("Initial:", numbers[5, 2, 8, 1, 9])30print()31bubble_sort_trace(numbers[5, 2, 8, 1, 9])⋯outputInitial: [5, 2, 8, 1, 9]
2n ← 5⋯4def bubble_sort_trace(arr[5, 2, 8, 1, 9]):5    """Bubble sort with step-by-step trace"""6    n→ 5 = len(arr[5, 2, 8, 1, 9])⋯
3swapped ← Falsepass 1 of 4⋯8# Trace each pass9for i0 in range(n5 - 1):10    print(f"Pass {i0 + 1}:")11    swapped→ False = False⋯outputPass 1:All 4 passes — pass 1 is the card abovepassiswapped
10False
21False
32False
43False
4for j in range(n - i - 1):pass 1 of 10⋯13for j0 in range(n5 - i0 - 1):14    if arr[j] > arr[j + 1]:15        print(f"  Swap {arr[j]} and {arr[j + 1]}")⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5arr[j] ← 2, arr[j + 1] ← 5, swapped ← Truepass 1 of 4⋯13for j in range(n - i - 1):14    if arr[j]5 > arr[j + 1]2:15        print(f"  Swap {arr[j]5} and {arr[j + 1]2}")16        arr[j]→ 2, arr[j + 1]→ 5 = arr[j + 1], arr[j]17        swapped→ True = True⋯output  Swap 5 and 2All 4 passes — pass 1 is the card abovepassarr[j]arr[j + 1]swapped
15 → 22 → 5True
28 → 11 → 8True
35 → 11 → 5True
42 → 11 → 2True
6print(f"  Result: {arr}")⋯19print(f"  Result: {arr[2, 5, 1, 8, 9]}")⋯output  Result: [2, 5, 1, 8, 9]
7print(f"  Result: {arr}")⋯19print(f"  Result: {arr[2, 1, 5, 8, 9]}")⋯output  Result: [2, 1, 5, 8, 9]
8print(f"  Result: {arr}")⋯19print(f"  Result: {arr[1, 2, 5, 8, 9]}")⋯output  Result: [1, 2, 5, 8, 9]
9print(f"  Result: {arr}")⋯19print(f"  Result: {arr[1, 2, 5, 8, 9]}")⋯output  Result: [1, 2, 5, 8, 9]
10if not swapped:⋯21if not swappedFalse:22    print("  No swaps - array is sorted!")23    break⋯output  No swaps - array is sorted!
11numbers ← [1, 2, 5, 8, 9]⋯30print()31bubble_sort_trace(numbers→ [1, 2, 5, 8, 9])⋯

All 4 passes — pass 1 is the card above
pass	`i`	`swapped`
1	0	False
2	1	False
3	2	False
4	3	False

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 4 passes — pass 1 is the card above
pass	`arr[j]`	`arr[j + 1]`	`swapped`
1	5 → 2	2 → 5	True
2	8 → 1	1 → 8	True
3	5 → 1	1 → 5	True
4	2 → 1	1 → 2	True

Optimized Version

                            optimized.py
                        
Replay: real traced execution (multi-file project)

                            # 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)


                        
1almost_sorted ← [1, 2, 3, 5, 4, 6, 7, 8], reversed_list ← [8, 7, 6, 5, 4, 3, 2, 1]⋯26# Test on different inputs27almost_sorted→ [1, 2, 3, 5, 4, 6, 7, 8] = [1, 2, 3, 5, 4, 6, 7, 8]28reversed_list→ [8, 7, 6, 5, 4, 3, 2, 1] = [8, 7, 6, 5, 4, 3, 2, 1]2930print("Almost sorted:")31print("Before:", almost_sorted[1, 2, 3, 5, 4, 6, 7, 8])32passes1 = bubble_sort_optimized(almost_sorted[1, 2, 3, 5, 4, 6, 7, 8])33print("After: ", almost_sorted)⋯outputAlmost sorted:
Before: [1, 2, 3, 5, 4, 6, 7, 8]
2n ← 8, passes ← 0pass 1 of 2⋯4def bubble_sort_optimized(arr[1, 2, 3, 5, 4, 6, 7, 8]):5    """Optimized bubble sort with early termination"""6    n→ 8 = len(arr[1, 2, 3, 5, 4, 6, 7, 8])7    passes→ 0 = 0⋯
3passes ← 1, swapped ← Falsepass 1 of 9⋯9# Optimized with early termination10for i0 in range(n8 - 1):11    passes→ 1 += 112    swapped→ False = False⋯All 9 passes — pass 1 is the card abovepassipassesswapped
100 → 1False
211 → 2False
300 → 1False
411 → 2False
522 → 3False
633 → 4False
744 → 5False
855 → 6False
966 → 7False
4for j in range(n - i - 1):pass 1 of 41⋯14for j0 in range(n8 - i0 - 1):15    if arr[j] > arr[j + 1]:16        arr[j], arr[j + 1] = arr[j + 1], arr[j]⋯41 passes — pass 1 is the card abovepassjiswapped
100—
210—
320—
430—
540—
650—
760—
801—
911—
⋯ 30 more passes ⋯
4015—
4106—
5arr[j] ← 4, arr[j + 1] ← 5, swapped ← Truepass 1 of 29⋯14for j in range(n - i - 1):15    if arr[j]5 > arr[j + 1]4:16        arr[j]→ 4, arr[j + 1]→ 5 = arr[j + 1], arr[j]17        swapped→ True = True⋯29 passes — pass 1 is the card abovepassarr[j]arr[j + 1]swapped
15 → 44 → 5True
28 → 77 → 8True
38 → 66 → 8True
48 → 55 → 8True
58 → 44 → 8True
68 → 33 → 8True
78 → 22 → 8True
88 → 11 → 8True
97 → 66 → 7True
⋯ 18 more passes ⋯
283 → 11 → 3True
292 → 11 → 2True
6if not swapped:⋯19# If no swaps, array is sorted20if not swappedFalse:21    break⋯
7return passes⋯23return passes2⋯
8almost_sorted ← [1, 2, 3, 4, 5, 6, 7, 8], passes1 ← 2⋯31print("Before:", almost_sorted)32passes1→ 2 = bubble_sort_optimized(almost_sorted→ [1, 2, 3, 4, 5, 6, 7, 8])33print("After: ", almost_sorted[1, 2, 3, 4, 5, 6, 7, 8])34print("Passes:", passes12)3536print("\nReverse sorted:")37print("Before:", reversed_list[8, 7, 6, 5, 4, 3, 2, 1])38passes2 = bubble_sort_optimized(reversed_list[8, 7, 6, 5, 4, 3, 2, 1])39print("After: ", reversed_list)⋯outputAfter:  [1, 2, 3, 4, 5, 6, 7, 8]
Passes: 2

Reverse sorted:
Before: [8, 7, 6, 5, 4, 3, 2, 1]
9n ← 8, passes ← 0pass 2 of 2⋯4def bubble_sort_optimized(arr[8, 7, 6, 5, 4, 3, 2, 1]):5    """Optimized bubble sort with early termination"""6    n→ 8 = len(arr[8, 7, 6, 5, 4, 3, 2, 1])7    passes→ 0 = 0⋯
10return passes⋯23return passes7⋯
11reversed_list ← [1, 2, 3, 4, 5, 6, 7, 8], passes2 ← 7⋯37print("Before:", reversed_list)38passes2→ 7 = bubble_sort_optimized(reversed_list→ [1, 2, 3, 4, 5, 6, 7, 8])39print("After: ", reversed_list[1, 2, 3, 4, 5, 6, 7, 8])40print("Passes:", passes27)⋯outputAfter:  [1, 2, 3, 4, 5, 6, 7, 8]
Passes: 7

All 9 passes — pass 1 is the card above
pass	`i`	`passes`	`swapped`
1	0	0 → 1	False
2	1	1 → 2	False
3	0	0 → 1	False
4	1	1 → 2	False
5	2	2 → 3	False
6	3	3 → 4	False
7	4	4 → 5	False
8	5	5 → 6	False
9	6	6 → 7	False

41 passes — pass 1 is the card above
pass	`j`	`i`	`swapped`
1	0	0	—
2	1	0	—
3	2	0	—
4	3	0	—
5	4	0	—
6	5	0	—
7	6	0	—
8	0	1	—
9	1	1	—
⋯ 30 more passes ⋯
40	1	5	—
41	0	6	—

29 passes — pass 1 is the card above
pass	`arr[j]`	`arr[j + 1]`	`swapped`
1	5 → 4	4 → 5	True
2	8 → 7	7 → 8	True
3	8 → 6	6 → 8	True
4	8 → 5	5 → 8	True
5	8 → 4	4 → 8	True
6	8 → 3	3 → 8	True
7	8 → 2	2 → 8	True
8	8 → 1	1 → 8	True
9	7 → 6	6 → 7	True
⋯ 18 more passes ⋯
28	3 → 1	1 → 3	True
29	2 → 1	1 → 2	True

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

Descending Order

                            descending.py
                        
Replay: real traced execution (multi-file project)

                            # 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)


                        
1numbers1 ← [64, 34, 25, 12, 22], numbers2 ← [64, 34, 25, 12, 22]⋯24# Test both directions25numbers1→ [64, 34, 25, 12, 22] = [64, 34, 25, 12, 22]26numbers2→ [64, 34, 25, 12, 22] = [64, 34, 25, 12, 22]2728bubble_sort_ascending(numbers1[64, 34, 25, 12, 22])29print("Ascending: ", numbers1)⋯
2n ← 5⋯4def bubble_sort_ascending(arr[64, 34, 25, 12, 22]):5    """Sort in ascending order"""6    n→ 5 = len(arr[64, 34, 25, 12, 22])7    for i in range(n - 1):⋯
3for i in range(n - 1):pass 1 of 4⋯6n = len(arr)7for i0 in range(n5 - 1):8    for j in range(n - i - 1):9        # Ascending: swap if left > right⋯All 4 passes — pass 1 is the card abovepassi
10
21
32
43
4for j in range(n - i - 1):             # Ascending: swap if left > rig…pass 1 of 10⋯7for i in range(n - 1):8    for j0 in range(n5 - i0 - 1):9        # Ascending: swap if left > right10        if arr[j] > arr[j + 1]:11            arr[j], arr[j + 1] = arr[j + 1], arr[j]⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5arr[j] ← 34, arr[j + 1] ← 64pass 1 of 9⋯9# Ascending: swap if left > right10if arr[j]64 > arr[j + 1]34:11    arr[j]→ 34, arr[j + 1]→ 64 = arr[j + 1], arr[j]⋯All 9 passes — pass 1 is the card abovepassarr[j]arr[j + 1]
164 → 3434 → 64
264 → 2525 → 64
364 → 1212 → 64
464 → 2222 → 64
534 → 2525 → 34
634 → 1212 → 34
734 → 2222 → 34
825 → 1212 → 25
925 → 2222 → 25
6numbers1 ← [12, 22, 25, 34, 64]⋯28bubble_sort_ascending(numbers1→ [12, 22, 25, 34, 64])29print("Ascending: ", numbers1[12, 22, 25, 34, 64])3031bubble_sort_descending(numbers2[64, 34, 25, 12, 22])32print("Descending:", numbers2)⋯outputAscending:  [12, 22, 25, 34, 64]
7n ← 5⋯14def bubble_sort_descending(arr[64, 34, 25, 12, 22]):15    """Sort in descending order"""16    n→ 5 = len(arr[64, 34, 25, 12, 22])17    for i in range(n - 1):⋯
8for i in range(n - 1):pass 1 of 4⋯16n = len(arr)17for i0 in range(n5 - 1):18    for j in range(n - i - 1):19        # Descending: swap if left < right⋯All 4 passes — pass 1 is the card abovepassiarr[j]arr[j + 1]
1012 → 2222 → 12
21——
32——
43——
9for j in range(n - i - 1):             # Descending: swap if left < ri…pass 1 of 10⋯17for i in range(n - 1):18    for j0 in range(n5 - i0 - 1):19        # Descending: swap if left < right20        if arr[j] < arr[j + 1]:21            arr[j], arr[j + 1] = arr[j + 1], arr[j]⋯All 10 passes — pass 1 is the card abovepassjiarr[j]arr[j + 1]
100——
210——
320——
43012 → 2222 → 12
501——
611——
721——
802——
912——
1003——
10arr[j] ← 22, arr[j + 1] ← 12⋯19# Descending: swap if left < right20if arr[j]12 < arr[j + 1]22:21    arr[j]→ 22, arr[j + 1]→ 12 = arr[j + 1], arr[j]⋯
11numbers2 ← [64, 34, 25, 22, 12]⋯31bubble_sort_descending(numbers2→ [64, 34, 25, 22, 12])32print("Descending:", numbers2[64, 34, 25, 22, 12])⋯outputDescending: [64, 34, 25, 22, 12]

All 4 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 9 passes — pass 1 is the card above
pass	`arr[j]`	`arr[j + 1]`
1	64 → 34	34 → 64
2	64 → 25	25 → 64
3	64 → 12	12 → 64
4	64 → 22	22 → 64
5	34 → 25	25 → 34
6	34 → 12	12 → 34
7	34 → 22	22 → 34
8	25 → 12	12 → 25
9	25 → 22	22 → 25

All 4 passes — pass 1 is the card above
pass	`i`	`arr[j]`	`arr[j + 1]`
1	0	12 → 22	22 → 12
2	1	—	—
3	2	—	—
4	3	—	—

All 10 passes — pass 1 is the card above
pass	`j`	`i`	`arr[j]`	`arr[j + 1]`
1	0	0	—	—
2	1	0	—	—
3	2	0	—	—
4	3	0	12 → 22	22 → 12
5	0	1	—	—
6	1	1	—	—
7	2	1	—	—
8	0	2	—	—
9	1	2	—	—
10	0	3	—	—

Counting Comparisons

                            comparison_count.py
                        
Replay: real traced execution (multi-file project)

                            # 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")


                        
1sorted_list ← [1, 2, 3, 4, 5], reversed_list ← [5, 4, 3, 2, 1]⋯21# Test on different inputs22sorted_list→ [1, 2, 3, 4, 5] = [1, 2, 3, 4, 5]23reversed_list→ [5, 4, 3, 2, 1] = [5, 4, 3, 2, 1]24random_list→ [3, 1, 4, 2, 5] = [3, 1, 4, 2, 5]2526comp1, swap1 = bubble_sort_counted(sorted_list[1, 2, 3, 4, 5].copy())27print(f"Already sorted: {comp1} comparisons, {swap1} swaps")⋯
2n ← 5, comparisons ← 0, swaps ← 0pass 1 of 3⋯4def bubble_sort_counted(arr[1, 2, 3, 4, 5]):5    """Bubble sort that counts operations"""6    n→ 5 = len(arr[1, 2, 3, 4, 5])7    comparisons→ 0 = 08    swaps→ 0 = 0⋯All 3 passes — pass 1 is the card abovepassarrncomparisonsswaps
1[1, 2, 3, 4, 5]500
2[5, 4, 3, 2, 1]500
3[3, 1, 4, 2, 5]500
3for i in range(n - 1):pass 1 of 12⋯10# Count operations11for i0 in range(n5 - 1):12    for j in range(n - i - 1):13        comparisons += 1⋯All 12 passes — pass 1 is the card abovepassi
10
21
32
43
50
61
72
83
90
101
112
123
4comparisons ← 1pass 1 of 30⋯11for i in range(n - 1):12    for j0 in range(n5 - i0 - 1):13        comparisons→ 1 += 114        if arr[j] > arr[j + 1]:⋯30 passes — pass 1 is the card abovepassjicomparisons
1000 → 1
2101 → 2
3202 → 3
4303 → 4
5014 → 5
6115 → 6
7216 → 7
8027 → 8
9128 → 9
⋯ 19 more passes ⋯
29128 → 9
30039 → 10
5return comparisons, swaps⋯18return comparisons10, swaps0⋯
6comp1 ← 10, swap1 ← 0⋯26comp1→ 10, swap1→ 0 = bubble_sort_counted(sorted_list[1, 2, 3, 4, 5].copy())27print(f"Already sorted: {comp110} comparisons, {swap10} swaps")2829comp2, swap2 = bubble_sort_counted(reversed_list[5, 4, 3, 2, 1].copy())30print(f"Reverse sorted: {comp2} comparisons, {swap2} swaps")⋯outputAlready sorted: 10 comparisons, 0 swaps
7swaps ← 1, arr[j] ← 4, arr[j + 1] ← 5pass 1 of 13⋯13comparisons += 114if arr[j]5 > arr[j + 1]4:15    swaps→ 1 += 116    arr[j]→ 4, arr[j + 1]→ 5 = arr[j + 1], arr[j]⋯13 passes — pass 1 is the card abovepassswapsarr[j]arr[j + 1]
10 → 15 → 44 → 5
21 → 25 → 33 → 5
32 → 35 → 22 → 5
43 → 45 → 11 → 5
54 → 54 → 33 → 4
65 → 64 → 22 → 4
76 → 74 → 11 → 4
87 → 83 → 22 → 3
98 → 93 → 11 → 3
⋯ 2 more passes ⋯
121 → 24 → 22 → 4
132 → 33 → 22 → 3
8return comparisons, swaps⋯18return comparisons10, swaps10⋯
9comp2 ← 10, swap2 ← 10⋯29comp2→ 10, swap2→ 10 = bubble_sort_counted(reversed_list[5, 4, 3, 2, 1].copy())30print(f"Reverse sorted: {comp210} comparisons, {swap210} swaps")3132comp3, swap3 = bubble_sort_counted(random_list[3, 1, 4, 2, 5].copy())33print(f"Random order:   {comp3} comparisons, {swap3} swaps")⋯outputReverse sorted: 10 comparisons, 10 swaps
10return comparisons, swaps⋯18return comparisons10, swaps3⋯
11comp3 ← 10, swap3 ← 3⋯32comp3→ 10, swap3→ 3 = bubble_sort_counted(random_list[3, 1, 4, 2, 5].copy())33print(f"Random order:   {comp310} comparisons, {swap33} swaps")⋯outputRandom order:   10 comparisons, 3 swaps

All 3 passes — pass 1 is the card above
pass	`arr`	`n`
1	[1, 2, 3, 4, 5]	5
2	[5, 4, 3, 2, 1]	5
3	[3, 1, 4, 2, 5]	5

All 12 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	0
6	1
7	2
8	3
9	0
10	1
11	2
12	3

30 passes — pass 1 is the card above
pass	`j`	`i`	`comparisons`
1	0	0	0 → 1
2	1	0	1 → 2
3	2	0	2 → 3
4	3	0	3 → 4
5	0	1	4 → 5
6	1	1	5 → 6
7	2	1	6 → 7
8	0	2	7 → 8
9	1	2	8 → 9
⋯ 19 more passes ⋯
29	1	2	8 → 9
30	0	3	9 → 10

13 passes — pass 1 is the card above
pass	`swaps`	`arr[j]`	`arr[j + 1]`
1	0 → 1	5 → 4	4 → 5
2	1 → 2	5 → 3	3 → 5
3	2 → 3	5 → 2	2 → 5
4	3 → 4	5 → 1	1 → 5
5	4 → 5	4 → 3	3 → 4
6	5 → 6	4 → 2	2 → 4
7	6 → 7	4 → 1	1 → 4
8	7 → 8	3 → 2	2 → 3
9	8 → 9	3 → 1	1 → 3
⋯ 2 more passes ⋯
12	1 → 2	4 → 2	2 → 4
13	2 → 3	3 → 2	2 → 3

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

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

When to Use

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

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