def bubble_sort(list_data: list, length: int = 0) -> list:
    """
    It is similar is bubble sort but recursive.
    :param list_data: mutable ordered sequence of elements
    :param length: length of list data
    :return: the same list in ascending order

    >>> bubble_sort([0, 5, 2, 3, 2], 5)
    [0, 2, 2, 3, 5]

    >>> bubble_sort([], 0)
    []

    >>> bubble_sort([-2, -45, -5], 3)
    [-45, -5, -2]

    >>> bubble_sort([-23, 0, 6, -4, 34], 5)
    [-23, -4, 0, 6, 34]

    >>> bubble_sort([-23, 0, 6, -4, 34], 5) == sorted([-23, 0, 6, -4, 34])
    True

    >>> bubble_sort(['z','a','y','b','x','c'], 6)
    ['a', 'b', 'c', 'x', 'y', 'z']

    >>> bubble_sort([1.1, 3.3, 5.5, 7.7, 2.2, 4.4, 6.6])
    [1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7]
    """
    length = length or len(list_data)
    swapped = False
    for i in range(length - 1):
        if list_data[i] > list_data[i + 1]:
            list_data[i], list_data[i + 1] = list_data[i + 1], list_data[i]
            swapped = True

    return list_data if not swapped else bubble_sort(list_data, length - 1)


if __name__ == "__main__":
    import doctest

    doctest.testmod()

Bubble Sort is one of the simplest sorting algorithms that compares two elements at a time and swaps them if they are in the wrong order. This process is repeated until the entire sequence is in order.

• Time Complexity: O(n ^ 2) for average case; O(n) for best case.
• Space Complexity: O(n); note that iterative bubble sort has space complexity as O(1).

Steps

Base case: If the size of the array is 1, return.

• We need to fix the last element of the current sub-array. For this, iterate over the entire array using normal Bubble Sort, and perform swapping.
• Next, call the function on the entire array excluding the last element(which was fixed by the iteration in the above step)
• Repeat until Base Case is reached.

Example

Let the given array be: {5, 3, 2, 1, 4}

First Iteration:

• {5, 3, 2, 1, 4} -> {3, 5, 2, 1, 4} Swap since 5 > 3
• {3, 5, 2, 1, 4} -> {3, 2, 5, 1, 4} Swap since 5 > 2
• {3, 2, 5, 1, 4} -> {3, 2, 1, 5, 4} Swap since 5 > 1
• {3, 2, 1, 5, 4} -> {3, 2, 1, 4, 5} Swap since 5 > 4

This iteration has fixed the position of 5. Now, we will consider the array up to index 3.

Second Iteration:

• {3, 2, 1, 4, 5} -> {2, 3, 1, 4, 5} Swap since 3 > 2
• {2, 3, 1, 4, 5} -> {2, 1, 3, 4, 5} Swap since 3 > 1
• {2, 1, 3, 4, 5}; As 3 < 4, do not swap

Note: As we check one less element with every iteration, we do not need elements at index 3 and 4 i.e., 4 and 5, as 5 is already in order. Formally, for an array with n integers, we consider elements only up to index n - i, where i is the iteration number.

Third Iteration:

• {2, 1, 3, 4, 5} -> {1, 2, 3, 4, 5} Swap since 1 > 2
• {1, 2, 3, 4, 5}; As 2 < 3, do not swap

Fourth Iteration:

• {1, 2, 3, 4, 5}; As 1 < 2, do not swap

Fifth Iteration:

• {1, 2, 3, 4, 5}; As the size of the array is 1, return.

Note: This is the base case.

Pseudo Code

void bubbleSort(arr[], n)
    if(n==1)
        return;

    for(i = 0; i<n-1; i++)
        if(arr[i] > arr[i+1])
            swap(arr[i], arr[i+1])

    bubbleSort(arr, n-1)

Implementations

• Java
• C

Video Explanation

A video explaining iterative as well as recursive bubble sort