Bubble sort is a simple sorting algorithm that repeatedly iterates through the list of elements, compares adjacent elements, and swaps them if they are in the wrong order. The algorithm repeats this process until the list is sorted.
Code:
def bubble_sort(lst):
for i in range(len(lst) - 1):
for j in range(len(lst) - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
# Test the bubble sort function
lst = [5, 4, 3, 2, 1]
bubble_sort(lst)
print(lst) # Output: [1, 2, 3, 4, 5]This implementation of bubble sort has a time complexity of O(n^2) in the worst case, which makes it less efficient for large lists compared to other sorting algorithms such as quicksort or mergesort. However, it is simple to implement and can be useful for small lists or as a teaching tool.
Using Recursion
Code:
def bubble_sort_recursive(lst, n):
# Base case: if the list is empty or has only one element, it is already sorted
if n == 0 or n == 1:
return
# Iterate through the list and swap adjacent elements if they are in the wrong order
for i in range(n - 1):
if lst[i] > lst[i + 1]:
lst[i], lst[i + 1] = lst[i + 1], lst[i]
# Recursively call the function on the shortened list
bubble_sort_recursive(lst, n - 1)
# Test the bubble sort function
lst = [5, 4, 3, 2, 1]
bubble_sort_recursive(lst, len(lst))
print(lst) # Output: [1, 2, 3, 4, 5]This implementation works by sorting the list in a similar way to the iterative version of bubble sort, but instead of using a loop to iterate through the list, it uses recursion to shorten the list by one element at each step. The base case for the recursion is when the list has zero or one elements, in which case the list is already sorted.
As with the iterative version of bubble sort, this implementation has a time complexity of O(n^2) in the worst case, which makes it less efficient for large lists compared to other sorting algorithms. However, it can be a useful exercise to understand the concept of recursion and how it can be applied to sorting algorithms.
