Implementation of Bubble Sort Algorithm in Python

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. This process is repeated until no swaps are needed, which indicates that the list is sorted. In this article, we’ll start with a basic version of the bubble sort algorithm in Python to sort a list of numbers in ascending order. We’ll then explore several variations, including sorting in descending order, optimizing the algorithm for better performance, and sorting custom objects.

Prerequisites:

Basic Bubble Sort Implementation

Let’s begin with the standard iterative implementation of bubble sort. This version sorts an array in ascending order by repeatedly comparing adjacent elements and swapping them if they are in the wrong order.

def bubble_sort(arr):
  # `arr` is the list that we want to sort

  # `n` is the number of elements in the list
  n = len(arr)

  # The outer loop goes through each element in the list
  # After each pass, the largest unsorted element is placed at the end
  for i in range(n):

    # The inner loop compares each adjacent element and swaps them if needed
    # As the largest element is bubbled to end with each outer loop, we exclude the sorted elements from comparison using `n-i-1`
    for j in range(0, n-i-1):

      # Compare the adjacent elements
      # If the first element is larger than the second element then swap
      if arr[j] > arr[j+1] :
        arr[j], arr[j+1] = arr[j+1], arr[j] # swapping elements

# Example of using bubble sort on a list of numbers
arr = [64, 34, 25, 12, 22, 11, 90]

bubble_sort(arr) # calling the bubble_sort method on the list of numbers

print("Sorted array is:", *arr)

# Output: Sorted array is: 11 12 22 25 34 64 90

In this basic implementation:

  • We define a function bubble_sort(arr) that takes a list arr as input.
  • We get the length of the list using len(arr) and store it in the variable n.
  • The outer loop for i in range(n) iterates through each element of the list.
  • The inner loop for j in range(0, n-i-1) compares each adjacent element and swaps them if needed.
  • If the element at index j is greater than the element at index j+1, then we swap them using the Pythonic syntax arr[j], arr[j+1] = arr[j+1], arr[j].

Sorting in Descending Order

Sometimes, we need to sort elements in reverse order (i.e., from largest to smallest). We can easily modify the basic implementation to sort in descending order by changing the comparison operator from > to <. This is useful when you want to arrange items from highest to lowest value.

def bubble_sort_descending(arr):
  # `arr` is the list that we want to sort

  # `n` is the number of elements in the list
  n = len(arr)

  # The outer loop goes through each element in the list
  # After each pass, the smallest unsorted element is placed at the end
  for i in range(n):

    # The inner loop compares each adjacent element and swaps them if needed
    # As the smallest element is bubbled to end with each outer loop, we exclude the sorted elements from comparison using `n-i-1`
    for j in range(0, n-i-1):

      # Compare the adjacent elements
      # If the first element is smaller than the second element then swap
      if arr[j] < arr[j+1]: # Note the change from > to <
        arr[j], arr[j+1] = arr[j+1], arr[j] # swapping elements


# Example of using bubble sort on a list of numbers
arr = [64, 34, 25, 12, 22, 11, 90]

bubble_sort_descending(arr) # calling the bubble_sort_descending method on the list of numbers

print("Sorted array is:", *arr)  # printing sorted list

# Output: Sorted array is: 90 64 34 25 22 12 11

In this descending order implementation, the only change is in the if condition within the inner loop:

  • We now check if arr[j] < arr[j+1] instead of arr[j] > arr[j+1].
  • This ensures that smaller elements “bubble” to the end of the list with each pass.

Optimized Bubble Sort

Bubble sort can be optimized to stop early if no swaps occur during a pass. This means that if the list is already sorted, the algorithm will terminate after just one pass, improving the best-case time complexity from O(n^2) to O(n). This optimization is useful when dealing with nearly sorted data.

def optimized_bubble_sort(arr):
  # `arr` is the list that we want to sort

  # `n` is the number of elements in the list
  n = len(arr)

  # The outer loop goes through each element in the list
  # After each pass, the largest unsorted element is placed at the end
  for i in range(n):

    # Initialize a flag to check if any swaps occurred in this pass
    swapped = False

    # The inner loop compares each adjacent element and swaps them if needed
    # As the largest element is bubbled to end with each outer loop, we exclude the sorted elements from comparison using `n-i-1`
    for j in range(0, n-i-1):

      # Compare the adjacent elements
      # If the first element is larger than the second element then swap
      if arr[j] > arr[j+1] :
        arr[j], arr[j+1] = arr[j+1], arr[j] # swapping elements
        swapped = True

    # If no two elements were swapped in the inner loop, the array is sorted
    # break the for loop early
    if swapped == False:
      break

# Example of using bubble sort on a list of numbers
arr = [64, 34, 25, 12, 22, 11, 90]

optimized_bubble_sort(arr) # calling the bubble_sort method on the list of numbers

print("Sorted array is:", *arr)

# Output: Sorted array is: 11 12 22 25 34 64 90

In this optimized implementation:

  • We introduce a boolean variable swapped and set it to False at the beginning of each pass (outer loop).
  • If we make any swaps during the inner loop, we set swapped to True.
  • After each pass, we check if swapped is still False. If it is, then we know that no swaps were made during that pass, which means the list is already sorted, and we can break out of the outer loop using the break statement.

Sorting Custom Objects

Bubble sort can also be used to sort lists of custom objects. To do this, you need to provide a way for the algorithm to compare two objects. This is typically done using a custom comparison function.

Let’s say we have a class called Person with attributes name and age, and we want to sort a list of Person objects by age.

class Person:
  def __init__(self, name, age):
    # `name` is name of the person
    self.name = name
    # `age` is age of the person
    self.age = age

  def __repr__(self):
    # return string representation of the `Person` object
    return f"{self.name} ({self.age})"

def bubble_sort_custom(arr, compare_func):
  # `arr` is the list that we want to sort
  # `compare_func` is a function that defines how to compare two elements

  # `n` is the number of elements in the list
  n = len(arr)

  # The outer loop goes through each element in the list
  # After each pass, the largest unsorted element is placed at the end
  for i in range(n):
    # The inner loop compares each adjacent element and swaps them if needed
    # As the largest element is bubbled to end with each outer loop, we exclude the sorted elements from comparison using `n-i-1`
    for j in range(0, n-i-1):
      # Compare the adjacent elements using the custom comparison function
      if compare_func(arr[j], arr[j+1]) > 0:
        arr[j], arr[j+1] = arr[j+1], arr[j] # swapping elements

# Example of using bubble sort on a list of custom objects
people = [
    Person("Alice", 30),
    Person("Bob", 25),
    Person("Charlie", 35),
    Person("David", 20)
]

# Define a custom comparison function to sort by age
def compare_by_age(person1, person2):
  # Compare the ages of two person
  return person1.age - person2.age

bubble_sort_custom(people, compare_by_age)

print("Sorted list of people by age:", people)
# Output: Sorted list of people by age: [David (20), Bob (25), Alice (30), Charlie (35)]

In this custom object sorting implementation:

  • We define a class Person with attributes name and age. The __repr__ method is defined to provide a string representation of the Person object for easy printing.
  • We define a function bubble_sort_custom(arr, compare_func) that takes a list arr and a comparison function compare_func as input.
  • The compare_func is a function that takes two elements from the list and returns:
    • A positive value if the first element should come after the second element.
    • A negative value if the first element should come before the second element.
    • Zero if the two elements are equal.
  • We create a list of Person objects called people.
  • We define a custom comparison function compare_by_age(person1, person2) that compares two Person objects based on their age.
  • We call bubble_sort_custom(people, compare_by_age) to sort the list of Person objects by age.

This approach can be used to sort lists of any custom objects based on any criteria you define in the comparison function.

What’s Next?

Now that you’ve mastered the implementation of bubble sort in Python and its various applications, you might want to deepen your understanding with these related topics: