Bubble sort

Problem¶

Implement stable bubble sort for a Python list.

Key trick¶

Repeatedly swap adjacent out-of-order elements. After each pass, the largest remaining element has moved to the end.

A linked-list version is possible, but swapping adjacent nodes is unnecessarily awkward; insertion sort or merge sort is preferable.

Trap¶

Without the early-exit flag, sorted input still takes \(O(n^2)\) time.

Why is it interesting?¶

It demonstrates stability, adjacent swaps, and adaptive best-case behavior, but is rarely appropriate in production.

Python solution¶

class sort_bubble_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]

        # Everything after `end` is already in its final position.
        for end in range(len(arr) - 1, 0, -1):
            swapped = False

            # Swap adjacent inversions.
            # The largest value in this range moves to `end`.
            for i in range(end):
                if arr[i] > arr[i + 1]:
                    arr[i], arr[i + 1] = arr[i + 1], arr[i]
                    swapped = True

            # No inversions means the entire list is sorted.
            if not swapped:
                break

        return arr