Optimized Bubble Sort Explained with Python Code

Bubble Sort is one of the most fundamental sorting algorithms, with a core idea of repeatedly comparing adjacent elements and swapping their positions to make larger elements “float” to the end of the array like bubbles. It is ideal for programming beginners to learn the basics of sorting algorithms.

I. Core Principles of Bubble Sort

The workflow of Bubble Sort can be briefly summarized in three steps:

Compare adjacent elements: Start from the beginning of the array and compare adjacent elements one by one (1st & 2nd, 2nd & 3rd, …, (n-1)th & nth).
Swap if out of order: If the previous element is larger than the next one, swap their positions (ensuring the larger element moves backward).
Repeat traversal: After each full traversal, one more “sorted largest element” is added to the end of the array. Repeat the traversal on the unsorted part until the entire array is ordered.

Key Optimization Points

Early termination: If no swaps occur in a traversal, the array is already sorted, and we can exit directly (avoiding invalid loops).
Boundary shrinking: After each traversal, the position of the last unsorted element is fixed, so the next traversal does not need to compare up to that position.

II. Complete Implementation Code (Python)

Below is the complete optimized Bubble Sort code with detailed comments:

python

运行

def bubble_sort(arr):
    """
    Bubble Sort (optimized version): Sort the array in ascending order
    :param arr: The list to be sorted (supports numeric types)
    :return: The sorted list (in-place sorting, modifies the original array)
    """
    n = len(arr)
    # Outer loop: Control the number of sorting rounds (at most n-1 rounds, as each round confirms 1 largest element)
    for i in range(n - 1):
        swapped = False  # Flag to check if any swap occurred in this round
        # Inner loop: Traverse the unsorted part (boundary shrinks by i positions each round)
        for j in range(n - 1 - i):
            # Compare adjacent elements and swap if out of order
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True  # Mark that a swap occurred
        # Optimization: Exit if no swaps in this round (array is already sorted)
        if not swapped:
            break
    return arr

# Test cases
if __name__ == "__main__":
    # Test 1: Ordinary unordered array
    test1 = [64, 34, 25, 12, 22, 11, 90]
    print("Before sorting (ordinary array):", test1)
    bubble_sort(test1)
    print("After sorting (ordinary array):", test1)  # Output: [11, 12, 22, 25, 34, 64, 90]

    # Test 2: Already sorted array (verify early termination optimization)
    test2 = [1, 2, 3, 4, 5]
    print("\nBefore sorting (already sorted):", test2)
    bubble_sort(test2)
    print("After sorting (already sorted):", test2)  # Output: [1, 2, 3, 4, 5]

    # Test 3: Array with duplicate elements
    test3 = [5, 3, 8, 3, 2]
    print("\nBefore sorting (with duplicates):", test3)
    bubble_sort(test3)
    print("After sorting (with duplicates):", test3)  # Output: [2, 3, 3, 5, 8]

    # Test 4: Empty array or single-element array
    test4 = []
    test5 = [42]
    bubble_sort(test4)
    bubble_sort(test5)
    print("\nAfter sorting empty array:", test4)  # Output: []
    print("After sorting single-element array:", test5)  # Output: [42]

III. Explanation of Key Code Parts

Outer loop (for i in range(n - 1)):
- When the array length is n, a maximum of n-1 sorting rounds are needed (e.g., 3 elements only need 2 rounds to determine all positions).
- i represents the number of already sorted elements (increases by 1 after each round).
Inner loop (for j in range(n - 1 - i)):
- The boundary of each traversal is n-1-i, because the first i largest elements are already sorted at the end of the array and do not need to be compared again.
- j starts from 0 and compares arr[j] and arr[j+1] in sequence.
Early termination optimization (swapped flag):
- If no swaps occur in a round, it means all adjacent elements in the array are already in order. We jump out of the outer loop directly to reduce unnecessary traversals.

IV. Algorithm Performance Analysis

Metric	Result	Explanation
Time Complexity (Best)	O(n)	Only 1 traversal is needed when the array is already sorted (no swaps).
Time Complexity (Worst)	O(n²)	When the array is in reverse order, n-1 traversals are needed, with n-i comparisons per round.
Time Complexity (Average)	O(n²)	Suitable for small-scale data (n<1000).
Space Complexity	O(1)	In-place sorting, no extra space required (only temporary variables are used).
Stability	Stable	Equal elements do not swap positions (original relative order is preserved).

Applicable Scenarios

Suitable for small-scale data sorting (e.g., n<1000) with simple and easy-to-implement code.
Suitable for nearly sorted data (can achieve O(n) efficiency with optimization).
Not suitable for large-scale data (O(n²) efficiency will cause significant lag when n>10000).

V. Differences from Selection Sort (Easy to Confuse for Beginners)

Feature	Bubble Sort	Selection Sort
Number of Swaps	May be large (O(n²) in reverse order)	Fixed n-1 times (only 1 swap per round).
Stability	Stable	Unstable (may swap the relative positions of equal elements).
Actual Efficiency (Small Scale)	Slightly lower (high swap overhead)	Slightly higher (low swap overhead).