Bubble Sort in Python – Sorting Algorithms

Last Updated on August 22, 2024 by GeeksGod

Introduction

Bubble Sort in Python, Sorting is a fundamental operation in computer science, and one of the simplest sorting algorithms is Bubble Sort. It is easy to understand and implement, making it a great starting point for beginners learning about sorting algorithms.

In this article, we’ll explore how the Bubble Sort algorithm works and how to implement it in Python.

What is Bubble Sort?

Bubble Sort is a straightforward comparison-based sorting algorithm. It repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.

Key Characteristics of Bubble Sort in Python:

• Comparisons are made between adjacent elements.
• Swaps occur if the elements are in the wrong order.
• The algorithm continues to iterate through the list until no more swaps are needed.

How Bubble Sort in Python Works

The algorithm works by iterating over the list multiple times. During each pass, it compares adjacent elements and swaps them if necessary. After each full pass through the list, the next largest element is placed in its correct position, and the number of elements to be checked reduces by one.

Example:

Let’s say we have the following list of numbers: [5, 1, 4, 2, 8]

Here’s how Bubble Sort would sort this list:

1. First Pass:
   • Compare 5 and 1: Swap them → [1, 5, 4, 2, 8]
   • Compare 5 and 4: Swap them → [1, 4, 5, 2, 8]
   • Compare 5 and 2: Swap them → [1, 4, 2, 5, 8]
   • Compare 5 and 8: No swap → [1, 4, 2, 5, 8]
2. Second Pass:
   • Compare 1 and 4: No swap → [1, 4, 2, 5, 8]
   • Compare 4 and 2: Swap them → [1, 2, 4, 5, 8]
   • Compare 4 and 5: No swap → [1, 2, 4, 5, 8]
3. Third Pass:
   • Compare 1 and 2: No swap → [1, 2, 4, 5, 8]
   • Compare 2 and 4: No swap → [1, 2, 4, 5, 8]
4. The list is now sorted.

Bubble Sort in Python

Now that we understand how the algorithm works, let’s implement Bubble Sort in Python. The code is simple and straightforward.

Python 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

In this implementation:

• n: Length of the list.
• swapped: A flag to detect if any swap happened during the inner loop. If no swaps occur, the list is already sorted.

Time Complexity

The time complexity of Bubble Sort is O(n²) in the worst and average cases, where n is the number of items being sorted. The best-case scenario occurs when the list is already sorted, giving a time complexity of O(n).

Space Complexity

Bubble Sort is an in-place sorting algorithm, meaning it requires only a constant amount of additional memory space. Therefore, its space complexity is O(1).

Conclusion: Bubble Sort in Python

Bubble Sort is one of the simplest sorting algorithms and serves as a good introduction to the concept of sorting. While it is not the most efficient algorithm for large datasets, it is useful for educational purposes and for understanding the basics of sorting algorithms.

Once you’re comfortable with Bubble Sort, you can explore more efficient sorting algorithms like Quick Sort, Merge Sort, and Heap Sort.