Example usage

In the previous article, we explored how to implement a simple search algorithm. This time, we’ll continue our learning journey by practicing a common sorting algorithm: Bubble Sort. Through this algorithm, we’ll learn how to sort a set of numbers and deepen our understanding of how algorithms operate.

Introduction to Bubble Sort

Bubble Sort is a simple sorting algorithm. Its core idea is to repeatedly compare adjacent elements and gradually “bubble” larger elements toward the end of the array. Although Bubble Sort is relatively inefficient—especially for large datasets—it remains a classic example in algorithm education, helping learners grasp the fundamental concepts behind sorting.

How It Works

The basic steps of Bubble Sort are as follows:

1. Start from the first element of the array and compare each pair of adjacent elements.
2. If the preceding element is greater than the succeeding one, swap them.
3. Repeat steps 1 and 2 until reaching the end of the array.
4. After each full pass, the largest unsorted element “bubbles up” to its correct position at the end.
5. Repeat the above process on the remaining (unsorted) portion of the array until the entire array is sorted.

In pseudocode, Bubble Sort can be expressed as:

for i from 0 to n-1:
    for j from 0 to n-i-1:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])

Here, n is the length of the array, and arr is the array to be sorted.

A Concrete Example

Let’s walk through Bubble Sort step-by-step using a concrete example.

Suppose we have the following array:

arr = [64, 34, 25, 12, 22, 11, 90]

We want to sort this array in ascending order. Following the Bubble Sort procedure, we perform the following operations:

1. First Pass:

   • Compare 64 and 34 → swap → [34, 64, 25, 12, 22, 11, 90]
   • Compare 64 and 25 → swap → [34, 25, 64, 12, 22, 11, 90]
   • Compare 64 and 12 → swap → [34, 25, 12, 64, 22, 11, 90]
   • Compare 64 and 22 → swap → [34, 25, 12, 22, 64, 11, 90]
   • Compare 64 and 11 → swap → [34, 25, 12, 22, 11, 64, 90]
   • Compare 64 and 90 → no swap → unchanged

   After the first pass, the largest element, 90, has settled into its final position at the end.

2. Second Pass:

   • Repeat the same process on the unsorted subarray [34, 25, 12, 22, 11, 64].

After several passes, the array gradually transforms into:

[11, 12, 22, 25, 34, 64, 90]

Code Implementation

Below is a Python implementation of Bubble Sort:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Use a flag to track whether any swaps occurred in this pass
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # swap
                swapped = True
        # If no swaps occurred, the array is already sorted
        if not swapped:
            break

# Example usage
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

In this implementation, we define a function bubble_sort that takes an input array arr. We introduce a flag swapped to optimize performance: if no swaps occur during a complete pass, the array must already be sorted, and we can terminate early.

Summary

In this article, we implemented a simple yet classic sorting algorithm—Bubble Sort. Through code examples and a detailed walkthrough, we gained insight into its underlying mechanism and practical implementation. While Bubble Sort is well-suited for learning and small-scale data, more efficient algorithms are typically preferred in real-world applications.

In the next article, we’ll explore another fundamental sorting algorithm: Selection Sort, diving deeper into its analysis and implementation. We hope this series helps beginners progressively master and apply essential algorithmic concepts.