Bubble Sort in Python

Sorting algorithms are essential tools in computer science, and one of the simplest and most intuitive sorting algorithms is Bubble Sort. Although it’s not the most efficient algorithm for large datasets, Bubble Sort is a great starting point for those learning about sorting techniques and algorithm design. In this blog post, we will dive into Bubble Sort, explain how it works, and show you how to implement it in Python.

What is Bubble Sort?

Bubble Sort is a comparison-based algorithm that 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. This algorithm is called “Bubble Sort” because smaller elements “bubble” to the top of the list (or the beginning), and larger elements sink to the bottom (or the end) with each iteration.

How Does Bubble Sort Work?

Here’s a step-by-step explanation of how Bubble Sort works:

1. Start at the beginning of the list: Compare the first two adjacent elements.
2. Swap if necessary: If the first element is greater than the second, swap them.
3. Move to the next pair: Move to the next pair of adjacent elements and repeat the comparison and swapping if needed.
4. Repeat for the entire list: Once you reach the end of the list, the largest element will be in its correct position.
5. Repeat the process: The next iteration will ignore the last element (since it is already sorted), and continue the process for the remaining unsorted elements.
6. End when no swaps are needed: The algorithm terminates when no swaps are made during a new pass through the list, meaning the list is fully sorted.

Time Complexity of Bubble Sort

The time complexity of Bubble Sort is:

• Worst-case time complexity: O(n²), where n is the number of elements in the list. This happens when the list is sorted in reverse order.
• Best-case time complexity: O(n), when the list is already sorted.
• Average-case time complexity: O(n²), which is typical for most unsorted lists.

Given its O(n²) time complexity, Bubble Sort is inefficient on large lists and is generally not recommended for practical use. However, its simplicity and ease of understanding make it a good educational tool for learning about sorting.

Bubble Sort Algorithm in Python

Now, let’s implement Bubble Sort in Python. Below is a simple Python function that sorts a list of numbers using the Bubble Sort algorithm.

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all elements in the list
    for i in range(n):
        # Last i elements are already sorted
        swapped = False
        for j in range(0, n-i-1):
            # Compare the adjacent elements
            if arr[j] > arr[j+1]:
                # Swap if they are in the wrong order
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no two elements were swapped by the inner loop, then the list is sorted
        if not swapped:
            break
    return arr

Explanation of the Code:

1. Outer loop: This loop runs n times, where n is the number of elements in the list. After each pass through the list, the largest element “bubbles” to its correct position at the end.
2. Inner loop: The inner loop compares adjacent elements and swaps them if they are in the wrong order. After each inner loop iteration, the last element is guaranteed to be in the correct position.
3. Optimization (swapped flag): The swapped flag helps optimize the algorithm. If no elements were swapped during a pass, the list is already sorted, and the algorithm stops early, saving unnecessary iterations.

Example of Using Bubble Sort

Let’s test the bubble_sort function with an example:

# Test list
numbers = [64, 34, 25, 12, 22, 11, 90]

# Sort the list using bubble sort
sorted_numbers = bubble_sort(numbers)

# Print the sorted list
print("Sorted list:", sorted_numbers)

Output:

Sorted list: [11, 12, 22, 25, 34, 64, 90]

Visualizing Bubble Sort

Let’s walk through a quick example with the list [64, 34, 25, 12, 22, 11, 90] to understand how Bubble Sort works:

• 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 → [34, 25, 12, 22, 11, 64, 90] (largest element is in place)
• Second pass:
  • Compare 34 and 25, swap → [25, 34, 12, 22, 11, 64, 90]
  • Compare 34 and 12, swap → [25, 12, 34, 22, 11, 64, 90]
  • Compare 34 and 22, swap → [25, 12, 22, 34, 11, 64, 90]
  • Compare 34 and 11, swap → [25, 12, 22, 11, 34, 64, 90]
  • Compare 34 and 64, no swap → [25, 12, 22, 11, 34, 64, 90]

This process continues until the list is fully sorted.

Conclusion

Bubble Sort is a great algorithm for learning about sorting and algorithm design. While it’s not the most efficient sorting method, its simplicity makes it an excellent tool for beginners to grasp the concepts of sorting and algorithmic thinking. When working with smaller datasets or when you need a simple sorting solution, Bubble Sort might still come in handy. For larger datasets, however, it’s worth exploring more efficient algorithms like Merge Sort or Quick Sort.

Happy coding!