Bubble Sort Algorithm

Bubble sort is one of the simplest sorting algorithms to understand and implement. It’s commonly taught as a starting point for learning more advanced sorting techniques. This algorithm repeatedly steps through a list, compares adjacent items, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.

In this guide, we’ll explain how bubble sort works, its time complexity, and provide a Python implementation. If you're preparing for technical interviews or brushing up on algorithms, this guide is for you.

What Is Bubble Sort

Bubble sort gets its name from the way larger elements "bubble" to the top (end) of the list while smaller elements gradually sink to the bottom. The algorithm works by comparing two adjacent elements at a time and swapping them if the first is larger than the second.

How Does Bubble Sort Work

Here’s a step-by-step breakdown:

1. Start at the beginning of the list.
2. Compare the first two elements. If the first is greater than the second, swap them.
3. Move to the next pair of adjacent elements and repeat step 2.
4. Continue this process until you reach the end of the list.
5. Repeat the process for the entire list, but ignore the last element in each subsequent pass (since it’s already sorted).
6. The sorting is complete when no swaps are made during a pass through the list.

Bubble Sort Example

Let’s say we have the following list: [5, 3, 8, 4, 2].

• First pass: We compare adjacent pairs and swap if necessary:
  • Compare 5 and 3 → swap → [3, 5, 8, 4, 2]
  • Compare 5 and 8 → no swap
  • Compare 8 and 4 → swap → [3, 5, 4, 8, 2]
  • Compare 8 and 2 → swap → [3, 5, 4, 2, 8]

After the first pass, the largest element (8) is in its final position.

• Second pass: We repeat the process, ignoring the last element (8):
  • Compare 3 and 5 → no swap
  • Compare 5 and 4 → swap → [3, 4, 5, 2, 8]
  • Compare 5 and 2 → swap → [3, 4, 2, 5, 8]

After the second pass, 5 is in its final position.

• Third pass: We continue, ignoring the last two elements (5 and 8):
  • Compare 3 and 4 → no swap
  • Compare 4 and 2 → swap → [3, 2, 4, 5, 8]
• Fourth pass: Only the first two elements need comparison:
  • Compare 3 and 2 → swap → [2, 3, 4, 5, 8]

At this point, the list is sorted.

Python Implementation Of Bubble Sort

Here’s a Python implementation of the bubble sort algorithm:

pythonCopy code
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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]
                swapped = True
        if not swapped:
            break
    return arr

# Example usage
array = [5, 3, 8, 4, 2]
sorted_array = bubble_sort(array)
print("Sorted array:", sorted_array)

Explanation Of Code

• n = len(arr): We get the length of the list.
• The outer loop runs n times, where n is the length of the list.
• The inner loop compares adjacent elements and swaps them if they’re in the wrong order.
• The swapped flag helps optimize the algorithm. If no swaps are made during an entire pass, the list is already sorted, and the loop can break early.

Time Complexity Of Bubble Sort

The time complexity of bubble sort is as follows:

• Worst-case time complexity: O(n^2) – This occurs when the list is in reverse order.
• Best-case time complexity: O(n) – This occurs when the list is already sorted, and the algorithm can break after one pass (due to the swapped flag).
• Average-case time complexity: O(n^2)

Bubble sort is inefficient for large datasets due to its quadratic time complexity. However, it can be useful for small lists or as a teaching tool for understanding basic sorting algorithms.

Space Complexity of Bubble Sort

Bubble sort has a space complexity of O(1) because it only requires a constant amount of additional memory for the swaps, regardless of the input size.

Advantages And Disadvantages Of Bubble Sort

Advantages:

• Simple to understand and implement.
• Can be optimized with the swapped flag to stop early if the list is already sorted.

Disadvantages:

• Inefficient for large datasets.
• Time complexity of O(n^2) makes it slower compared to more advanced algorithms like quicksort or mergesort.

Conclusion

Bubble sort is an easy-to-understand algorithm, making it a great starting point for learning about sorting. Although it’s not the most efficient, it teaches the basics of sorting algorithms, iteration, and comparisons.

For technical interviews or algorithmic study, understanding bubble sort can be valuable, especially for its educational merit. If you're working with small datasets or just learning to code, this algorithm can help you build a foundation in sorting algorithms.

By mastering bubble sort, you’ll be ready to tackle more advanced sorting techniques such as quicksort and mergesort in your programming journey.