Bubble Sort Implementation in Python

Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. Bubble Sort is easy to understand and implement, but it is not very efficient for large lists. In this article, we will discuss how to implement Bubble Sort in Python, its time and space complexities, and provide examples with detailed explanations.

How Bubble Sort Works

The algorithm starts at the beginning of the list and compares the first two elements. If the first element is larger than the second element, it swaps them. The algorithm then moves to the next pair of elements and compares them, continuing until it reaches the end of the list. At this point, the largest element is guaranteed to be at the end of the list. The algorithm repeats this process for the remaining elements, with each pass placing the next largest element in its correct position. This process continues until the entire list is sorted.

The steps involved in implementing Bubble Sort can be summarized as follows:

1. Start from the first element and compare it with the next element
2. If the first element is greater than the second element, swap them
3. Move to the next pair of elements and repeat step 2
4. Continue this process until the end of the list is reached
5. Repeat steps 1-4 until the list is sorted

Time Complexity

The time complexity of Bubble Sort is O(n^2), where n is the number of elements in the list. This means that for a list of n elements, Bubble Sort will perform n^2 operations. In the worst-case scenario, when the list is in reverse order, Bubble Sort will perform (n^2 – n) / 2 swaps. Although Bubble Sort is easy to understand and implement, it is not very efficient for large lists, making it unsuitable for real-world applications.

Space Complexity

The space complexity of Bubble Sort is O(1), which means that the amount of memory used by the algorithm is constant and does not depend on the size of the list. Bubble Sort works by swapping adjacent elements, so it does not require any additional memory to store temporary variables or data structures.

Python Code Examples

Let’s take a look at some Python code examples for implementing Bubble Sort:

Example 1: Sorting a List of Integers

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

In this example, we define a function called bubble_sort that takes a list of integers as input. The function then uses two nested loops to iterate over the list and compare adjacent elements. If the current element is larger than the next element, they are swapped. The range function is used to determine the range of values that the loop should iterate over.

We then create a list of integers called arr and call the bubble_sort function on it. Finally, we print the sorted array.

Example 2: Sorting a List of Strings

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
arr = ["apple", "banana", "orange", "pear", "kiwi"]
bubble_sort(arr)
print("Sorted array:", arr)

This example is similar to the previous one, but it sorts a list of strings instead of integers. The same bubble_sort function is used, but this time we create a list of strings called arr and call the function on it. The function works the same way as before, comparing adjacent elements and swapping them if necessary, until the entire list is sorted.

Example 3: Sorting a List of Tuples

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j][0] > arr[j+1][0]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
arr = [("apple", 2), ("banana", 1), ("orange", 3), ("pear", 4), ("kiwi", 5)]
bubble_sort(arr)
print("Sorted array:", arr)

This example demonstrates how Bubble Sort can be used to sort a list of tuples. In this case, each tuple contains a string and an integer. The bubble_sort function is modified to compare the first element of each tuple (i.e., the string) rather than the entire tuple. The function then swaps the tuples if necessary, based on the comparison of the first element. The sorted list of tuples is then printed.

Conclusion

In this article, we discussed how to implement Bubble Sort in Python, its time and space complexities, and provided examples with detailed explanations. Bubble Sort is a simple sorting algorithm that is easy to understand and implement, but it is not very efficient for large lists. For real-world applications, more advanced sorting algorithms such as Quick Sort or Merge Sort are typically used instead.