Sorting Algorithms: An Introduction to Bubble Sort, Step-by-Step Explanation + Code Examples

In computer science, a sorting algorithm is the process of rearranging a set of data in a specific order (usually ascending or descending). We frequently encounter sorting in daily life, such as sorting photos by date in a phone album or arranging items alphabetically in a shopping list—all powered by sorting algorithms behind the scenes. Bubble Sort is one of the simplest sorting algorithms, with a core idea analogous to bubbles in water: large elements “bubble up” to the end of the array.

一、Bubble Sort Basic Idea¶

Imagine a pile of stones of varying sizes that need to be sorted from smallest to largest. Bubble Sort works by: starting from the first element of the array, comparing adjacent elements one by one. If the previous element is larger than the next, swap them. After one round of comparisons, the largest element “bubbles up” to the end of the array. This process repeats for the remaining elements until all are sorted.

Example: Sort the array [5, 3, 8, 4, 2].

First round: Compare adjacent elements to push the largest element to the end.
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]
Now the largest element 8 is at the end (sorted).
Second round: Repeat for the first 4 elements [3, 5, 4, 2] to push the second-largest element to the second-to-last position.
Compare 3 and 5: 3 < 5 → no swap
Compare 5 and 4: 5 > 4 → swap → [3, 4, 5, 2, 8]
Compare 5 and 2: 5 > 2 → swap → [3, 4, 2, 5, 8]
Now the second-largest element 5 is at the second-to-last position (sorted).
Third round: Repeat for the first 3 elements [3, 4, 2] to push the third-largest element to the third-to-last position.
Compare 3 and 4: 3 < 4 → no swap
Compare 4 and 2: 4 > 2 → swap → [3, 2, 4, 5, 8]
Now the third-largest element 4 is at the third-to-last position (sorted).
Fourth round: Compare the first 2 elements [3, 2] to push the fourth-largest element to the fourth-to-last position.
Compare 3 and 2: 3 > 2 → swap → [2, 3, 4, 5, 8]
The array is now fully sorted.

二、Bubble Sort Step-by-Step Explanation¶

The core steps of Bubble Sort can be summarized as follows:

Determine Array Length: Let the array be arr with length n.
Outer Loop (Control Rounds): Perform n-1 rounds of comparisons (since each round fixes one element’s position, the last element is naturally sorted).
Inner Loop (Compare Adjacent Elements): In each round, compare adjacent elements from the start (arr[j] and arr[j+1]). If arr[j] > arr[j+1], swap them.
Optimization: Early Termination: If no swaps occur in a round, the array is already sorted—terminate early.

三、Code Example (Python)¶

Below is a Python implementation of Bubble Sort with a test array to verify its functionality. The code has two parts: defining the sorting function and testing it.

def bubble_sort(arr):
    n = len(arr)
    # Outer loop: control the number of rounds (up to n-1)
    for i in range(n - 1):
        swapped = False  # Flag to track if swaps occurred in this round
        # Inner loop: compare adjacent elements (last i elements are already sorted)
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                # Swap elements
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True  # Mark that a swap happened
        # Early termination if no swaps in this round
        if not swapped:
            break
    return arr

# Test the bubble sort function
test_arr = [5, 3, 8, 4, 2]
print("Before sorting:", test_arr)
sorted_arr = bubble_sort(test_arr)
print("After sorting:", sorted_arr)

Output:

Before sorting: [5, 3, 8, 4, 2]
After sorting: [2, 3, 4, 5, 8]

四、Optimizations and Complexity Analysis¶

Optimization: Early Termination: The swapped flag checks if any swaps occurred in a round. If not, the array is sorted, and the algorithm exits early.
Time Complexity:
- Worst Case (Completely Reversed): Requires n-1 + n-2 + ... + 1 = n(n-1)/2 ≈ O(n²) comparisons and swaps.
- Best Case (Already Sorted): Only one round of comparisons (no swaps), with time complexity O(n).
Space Complexity: Uses constant extra space for swaps, so space complexity is O(1).

五、Summary¶

Bubble Sort is one of the simplest sorting algorithms, with the core idea of repeatedly swapping adjacent elements to “bubble” large elements to the end. Its strengths include simplicity and ease of understanding, while its weakness is a high time complexity. It is ideal for small datasets and serves as an excellent entry point for learning sorting logic.