Bubble Sort

Bubble Sort Algorithm

Sorting data is one of the most common tasks in computer science. When data is sorted, it is much easier to search through (like using Binary Search!).

Bubble Sort is often the very first sorting algorithm you will learn.

1. How Does Bubble Sort Work?

Bubble Sort gets its name because the largest numbers "bubble" up to the top of the list.

Imagine you have a row of numbers. The algorithm works by looking at the first two numbers. If the left number is bigger than the right number, it swaps them. Then, it moves one step to the right and compares the next two numbers.

It repeats this process until it reaches the end of the list. By the end of the first full pass, the absolute largest number is guaranteed to be at the very end of the list!

Bubble Sort: Swapping adjacent elements until the list is sorted.

2. A Step-by-Step Example

Let's sort a small array of numbers from lowest to highest: [5, 3, 8, 4, 2]

Pass 1:

1. Compare 5 and 3. 5 is larger, so swap them. Array becomes [3, 5, 8, 4, 2].
2. Compare 5 and 8. 5 is smaller, so do nothing. Array stays [3, 5, 8, 4, 2].
3. Compare 8 and 4. 8 is larger, so swap them. Array becomes [3, 5, 4, 8, 2].
4. Compare 8 and 2. 8 is larger, so swap them. Array becomes [3, 5, 4, 2, 8].

Notice how the largest number (8) has successfully "bubbled" to the end!

Pass 2: Now we repeat the process, but we can ignore the last number since it is already in the correct spot.

1. Compare 3 and 5. Do nothing.
2. Compare 5 and 4. Swap them. Array becomes [3, 4, 5, 2, 8].
3. Compare 5 and 2. Swap them. Array becomes [3, 4, 2, 5, 8].

We repeat these passes until a full pass happens with zero swaps. That means the array is fully sorted!

3. Bubble Sort Code Example

Let's write the Bubble Sort algorithm in Python. Notice how we use a nested loop (a loop inside a loop).

def bubble_sort(arr):
    n = len(arr)
    # Loop through every element in the array
    for i in range(n):
        # Keep track if we made any swaps this pass
        swapped = False
        # Loop through the unsorted portion of the array
        for j in range(0, n - i - 1):
            # If the left element is larger, swap them!
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no swaps occurred, the array is already sorted
        if not swapped:
            break
    return arr

numbers = [5, 3, 8, 4, 2]
print("Original:", numbers)
print("Sorted:", bubble_sort(numbers))

4. Time Complexity

How fast is Bubble Sort?

• Best Case: O(n). If the array is already sorted, we only have to do one pass to check it.
• Worst Case: O(n²). If the array is sorted in reverse order, we have to do a full pass for every single element.

Because of this O(n²) Time Complexity, Bubble Sort is considered very slow for large datasets. It is rarely used in real-world professional software. However, it is an amazing educational tool for beginners learning how to manipulate arrays!