Bubble Sort (Using Recursion)

Can you give me python code for bubble sort?

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. The pass through the list is repeated until the list is sorted.

Here's a simple Python implementation of the bubble sort algorithm:


def bubble_sort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Example usage:
my_list = [64, 25, 12, 22, 11]
bubble_sort(my_list)

print("Sorted array:", my_list)


This code defines a function bubble_sort that takes a list as input and sorts it in ascending order using the bubble sort algorithm. The example usage shows how to sort an example list, and the sorted array is then printed.

Using recursion?

Although bubble sort is not typically implemented using recursion due to its inefficiency compared to iterative methods, it can be done for educational purposes. Here's an example of a recursive implementation of bubble sort in Python:


def recursive_bubble_sort(arr, n=None):
    # Base case: If the array is empty or contains only one element, it is already sorted
    if n is None:
        n = len(arr)
    
    if n <= 1:
        return
    
    # One pass of bubble sort: Traverse the array and swap adjacent elements if they are in the wrong order
    for i in range(n - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

    # Recursively call the function with a reduced size of the array
    recursive_bubble_sort(arr, n - 1)

# Example usage:
my_list = [64, 25, 12, 22, 11]
recursive_bubble_sort(my_list)

print("Sorted array:", my_list)

In this recursive implementation, the function recursive_bubble_sort takes an additional parameter n to represent the size of the array being considered in each recursive call. The base case checks if the array size is 1 or less, in which case the array is considered sorted. Otherwise, one pass of the bubble sort is performed, and the function is called recursively with a reduced size of the array.

What is the time complexity of the recursion based code?

The time complexity of the recursive version of bubble sort remains O(n^2) in the worst and average cases, just like the iterative version. This is because, even though recursion is used, the number of comparisons and swaps required to sort the array is still proportional to the square of the number of elements in the array.

Each recursive call performs one pass through the array, and there are a total of n recursive calls (each reducing the size of the array by 1). In each pass, the algorithm compares and potentially swaps adjacent elements, and this process is repeated for each pass until the array is sorted.

Therefore, the overall time complexity is still O(n^2), which makes bubble sort, whether implemented iteratively or recursively, inefficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

Tags: Algorithms,Python,Technology,