Bubble Sort: Implementing Ascending Order Sorting in Python¶

Have you ever wondered how bubbles rise in water? They slowly ascend from the bottom, with larger bubbles reaching the surface faster. The name “bubble sort” comes from this phenomenon—it causes larger elements in an array to “bubble up” to the end of the array.

In simple terms, Bubble Sort is a basic sorting algorithm. Its core idea is: Repeatedly traverse the array to be sorted, comparing two adjacent elements at a time. If their order is incorrect, swap them until the entire array is sorted.

How Bubble Sort Works¶

1. Compare Adjacent Elements: Start from the first element of the array and compare adjacent elements one by one (e.g., 1st and 2nd, 2nd and 3rd, …).
2. Swap Elements: If the previous element is larger than the next, swap their positions.
3. Repeat: Continue the above steps until all elements are in place. After each round, the largest element in the unsorted portion will “bubble” to its correct position at the end.
4. Optimization for Early Termination: If no swaps occur in a round, the array is already sorted, and we can stop early.

Implementing Bubble Sort in Python¶

Let’s use a concrete example to understand the sorting process and write the Python code. Suppose we want to sort the array: [64, 34, 25, 12, 22, 11, 90].

Step-by-Step Simulation:¶

• Round 1: Compare adjacent elements. The largest number (90) “bubbles up” to the end. The array becomes: [34, 25, 12, 22, 11, 64, 90].
• Round 2: Compare the first 6 elements. The second-largest number (64) bubbles to the second-to-last position. The array becomes: [25, 12, 22, 11, 34, 64, 90].
• Round 3: Continue comparing until all elements are sorted.

Python Code Implementation:¶

def bubble_sort(arr):
    n = len(arr)
    # Outer loop controls the number of rounds (at most n-1 rounds)
    for i in range(n - 1):
        swapped = False  # Flag to check if swaps occurred in this round
        # Inner loop compares adjacent elements, reducing iterations by 1 each round (elements at the end are sorted)
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap adjacent elements (Python simplifies the swap syntax)
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps, the array is already sorted; terminate early
        if not swapped:
            break
        print(f"After round {i+1}: {arr}")
    return arr

# Test the function
test_arr = [64, 34, 25, 12, 22, 11, 90]
print("Original array:", test_arr)
sorted_arr = bubble_sort(test_arr)
print("Sorted array:  ", sorted_arr)

Code Explanation:¶

1. Outer Loop: for i in range(n - 1)
   Controls the number of sorting rounds. At most n-1 rounds are needed (where n is the array length), as each round fixes one largest element’s position.

2. Inner Loop: for j in range(0, n - i - 1)
   Compares adjacent elements. Each round reduces the number of comparisons by 1 (since the last i elements are already sorted).

3. Swap Logic: arr[j], arr[j + 1] = arr[j + 1], arr[j]
   Uses Python’s tuple assignment to swap adjacent elements concisely.

4. Optimization Flag: swapped
   If no swaps occur in a round, the array is sorted, and the loop terminates early to avoid unnecessary comparisons.

Sample Output (with intermediate steps):¶

Original array: [64, 34, 25, 12, 22, 11, 90]
After round 1: [34, 25, 12, 22, 11, 64, 90]
After round 2: [25, 12, 22, 11, 34, 64, 90]
After round 3: [12, 22, 11, 25, 34, 64, 90]
After round 4: [12, 11, 22, 25, 34, 64, 90]
After round 5: [11, 12, 22, 25, 34, 64, 90]
Sorted array:   [11, 12, 22, 25, 34, 64, 90]

Characteristics of Bubble Sort¶

• Time Complexity: Worst case (completely reversed array) is O(n²); Best case (already sorted array) is O(n) (after optimization).
• Space Complexity: O(1) (only temporary variables are used; no extra space).
• Stability: Stable sort (relative order of equal elements is preserved).

Conclusion¶

Bubble Sort is one of the simplest sorting algorithms, with its core being “comparing and swapping adjacent elements.” Although it is inefficient (suitable for small datasets), understanding its principles is crucial for mastering sorting algorithms. After implementing it in Python, you can easily handle simple sorting tasks or try optimizing it into more efficient versions (e.g., Merge Sort, Quick Sort).

Try testing Bubble Sort with other arrays, such as [5, 3, 8, 4, 2], to verify if it correctly outputs the sorted result!