Test Bubble Sort

In the previous tutorial, we learned the fundamentals of algorithm analysis—particularly how to use Big O notation to evaluate an algorithm’s time and space complexity. Today, we’ll continue with hands-on algorithm practice by implementing a simple sorting algorithm: Bubble Sort.

Overview of Bubble Sort

Bubble Sort is a straightforward sorting algorithm. It repeatedly traverses the array to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until no more swaps are needed. The name “bubble sort” comes from the way smaller elements gradually “bubble up” to the beginning (top) of the array.

Basic Steps of Bubble Sort

1. Start from the leftmost element of the array and compare two adjacent elements.
2. If the first element is greater than the second, swap them.
3. Move one position to the right and repeat steps 1 and 2 until reaching the end of the array.
4. After one complete pass, the largest element will have “bubbled up” to the last position.
5. Exclude the last (now correctly placed) element and repeat the above steps until the entire array is sorted.

Time Complexity of Bubble Sort

Bubble Sort has a worst-case and average-case time complexity of $O(n^2)$, where $n$ is the length of the array. In the best case—when the input array is already sorted—the time complexity improves to $O(n)$. This is because only a single pass is needed; if no swaps occur during that pass, the algorithm can terminate early.

Implementing Bubble Sort

Below is a Python implementation of the Bubble Sort algorithm:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Flag to track whether any swap occurred
        swapped = False
        for j in range(0, n-i-1):
            # Compare adjacent elements
            if arr[j] > arr[j+1]:
                # Swap elements
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no swap occurred, array is already sorted—exit early
        if not swapped:
            break
    return arr

# Test Bubble Sort
sample_array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(sample_array)
print("Sorted array:", sorted_array)

Code Walkthrough

1. len(arr) retrieves the array length to determine how many passes are required.
2. The outer loop controls the number of passes; the inner loop performs pairwise comparisons of adjacent elements.
3. The swapped flag enables an optimization: if no swaps occur during a full pass, the array must already be sorted, allowing early termination.
4. Finally, the sorted array is returned.

Step-by-Step Example

Let’s trace through the example code:

• Initial array: [64, 34, 25, 12, 22, 11, 90].
• After the first pass:
  • [34, 25, 12, 22, 11, 64, 90] (64 ↔ 34)
  • [25, 12, 22, 11, 34, 64, 90] (34 ↔ 25)
  • [12, 22, 11, 25, 34, 64, 90] (25 ↔ 12)
  • [12, 11, 22, 25, 34, 64, 90] (22 ↔ 11)
  • [11, 12, 22, 25, 34, 64, 90] (12 ↔ 11)
  • Note: 90 remains at the end—it’s the largest element, so it’s excluded in subsequent passes.

After several such passes involving comparisons and swaps, the final sorted array becomes [11, 12, 22, 25, 34, 64, 90].

Conclusion

Today, we explored Bubble Sort, a foundational sorting algorithm. Through clear explanation and practical code implementation, we grasped its core idea and mechanics. While Bubble Sort is intuitive and easy to understand, its $O(n^2)$ performance makes it inefficient for large datasets—more advanced algorithms (e.g., Quick Sort, Merge Sort) are typically preferred in real-world applications.

In our next article, we’ll dive into another fundamental algorithm: a simple search algorithm.

We encourage you to implement and experiment with sorting algorithms in your own coding practice—to deepen your understanding and build fluency.