What is Sorting?¶

Sorting is a common operation in our daily life. For example, ranking exam scores, sorting a mobile phone contacts list alphabetically, or looking up words in a dictionary in alphabetical order… Essentially, sorting is the process of rearranging a set of unordered data according to a specific rule (such as从小到大 from smallest to largest, or从大到小 from largest to smallest). In computer science, sorting algorithms are one of the most fundamental and core algorithms. Mastering sorting algorithms can help us process data more efficiently.

What is Bubble Sort?¶

Bubble Sort is one of the simplest sorting algorithms. Its name comes from “bubbles”—just like bubbles in water rising to the surface, in Bubble Sort, larger elements gradually “bubble up” to the end of the array through swaps.

For example, if we have an array [5, 3, 8, 4, 2] and want to sort it in ascending order, Bubble Sort works by pushing the “largest bubble” (the largest element) to the end of the unsorted portion in each round until all elements are sorted.

Core Idea of Bubble Sort¶

Let’s take [5, 3, 8, 4, 2] as an example to break down the bubble process step by step:

Round 1 (Determine the largest element)¶

Start from the first element and compare adjacent elements. If the previous element is larger, swap them:
- Compare 5 and 3: 5 > 3, swap → [3, 5, 8, 4, 2]
- Compare 5 and 8: 5 < 8, no swap
- Compare 8 and 4: 8 > 4, swap → [3, 5, 4, 8, 2]
- Compare 8 and 2: 8 > 2, swap → [3, 5, 4, 2, 8]

Result: The largest element 8 has “bubbled up” to the end. The unsorted portion is now [3, 5, 4, 2].

Round 2 (Determine the second largest element)¶

Reduce the length of the unsorted portion by 1 (excluding the already sorted 8 at the end) and continue comparing adjacent elements:
- Compare 3 and 5: 3 < 5, no swap
- Compare 5 and 4: 5 > 4, swap → [3, 4, 5, 2]
- Compare 5 and 2: 5 > 2, swap → [3, 4, 2, 5]

Result: The second largest element 5 has “bubbled up” to the second-to-last position. The unsorted portion is now [3, 4, 2].

Round 3 (Determine the third largest element)¶

Reduce the length of the unsorted portion again and continue comparing:
- Compare 3 and 4: 3 < 4, no swap
- Compare 4 and 2: 4 > 2, swap → [3, 2, 4]

Result: The third largest element 4 has “bubbled up” to the third-to-last position. The unsorted portion is now [3, 2].

Round 4 (Determine the fourth largest element)¶

Only two elements remain in the unsorted portion:
- Compare 3 and 2: 3 > 2, swap → [2, 3]

Result: All elements are sorted. The final array is [2, 3, 4, 5, 8].

Summary of Bubble Sort Steps¶

1. Outer Loop: Controls how many rounds of comparisons are needed. For an array of length n, at most n-1 rounds are required (since each round determines the position of one element).
2. Inner Loop: Compares adjacent elements in each round, pushing larger elements to the end. After each round, the length of the unsorted portion decreases by 1 (no need to compare the already sorted elements at the end).
3. Optimization: If no swaps occur in a round, the array is already sorted, and we can terminate the loop early (to avoid unnecessary computations).

Code Implementation (Python)¶

Basic Version (No Optimization)¶

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # Outer loop: total n-1 rounds
        for j in range(n - 1 - i):  # Inner loop: n-1-i comparisons per round
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Swap adjacent elements
    return arr

# Test
arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr))  # Output: [2, 3, 4, 5, 8]

Optimized Version (Early Termination)¶

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False  # Flag to check if any swaps occurred in this round
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # If no swaps, the array is already sorted
            break
    return arr

# Test (Highly optimized for sorted arrays)
arr = [1, 2, 3, 4, 5]
print(optimized_bubble_sort(arr))  # Output: [1, 2, 3, 4, 5] (only 1 round needed)

Complexity Analysis of Bubble Sort¶

• Time Complexity:
• Worst Case (Completely reversed): Each round requires swaps, totaling n-1 + n-2 + ... + 1 = n(n-1)/2 comparisons. Time complexity is O(n²).

• Best Case (Already sorted): The optimized version requires only 1 round (no swaps), so time complexity is O(n).

• Space Complexity: Uses a constant amount of extra space (temporary variables for swaps), so space complexity is O(1) (in-place sorting).

Characteristics and Applicable Scenarios of Bubble Sort¶

• Advantages: Simple to understand and implement, suitable for grasping the basic idea of sorting algorithms.
• Disadvantages: Low efficiency (O(n²)), not suitable for large datasets.
• Applicable Scenarios: Small datasets or scenarios with low efficiency requirements (e.g., teaching demonstrations, simple data sorting).

Small Exercise¶

Try sorting the array [9, 7, 6, 15, 16, 5, 10, 11] using Bubble Sort. Can you walk through the process manually? You can refer to the steps above and write code to verify the result.

Through the above explanation, you should have mastered the core logic of Bubble Sort. As a foundational sorting algorithm, Bubble Sort helps you understand the “compare and swap” idea, laying the groundwork for learning more complex sorting algorithms like Quick Sort and Merge Sort!