6. Bubble Sort

In [13]:

def bubble_sort_recursive(arr):

    """
    With this recursive function, it is
    possible to do 1 pass through the array.
    It will ensure that the largest element
    will bubble out to the last position

    """

    # 1. Base case
    # if there are no elements or if there
    # is only 1 element in the array
    # return the array
    if len(arr) == 0 or len(arr) == 1:
        return arr

    # solve 1 case
    # if 0th element is larger than
    # the first element, swap them
    if arr[0] > arr[1]:
        arr[0], arr[1] = arr[1], arr[0]

    # recursive relation for the remaining array
    remaining = [arr[0]] + bubble_sort_recursive(arr[1:])

    return remaining

def bubble_sort_recursive(arr): """ With this recursive function, it is possible to do 1 pass through the array. It will ensure that the largest element will bubble out to the last position """ # 1. Base case # if there are no elements or if there # is only 1 element in the array # return the array if len(arr) == 0 or len(arr) == 1: return arr # solve 1 case # if 0th element is larger than # the first element, swap them if arr[0] > arr[1]: arr[0], arr[1] = arr[1], arr[0] # recursive relation for the remaining array remaining = [arr[0]] + bubble_sort_recursive(arr[1:]) return remaining

In [14]:

def sorting(arr):
    """
    The above function handles what you could say
    one pass through the array.
    For the remaining n-2 passes (why n-2?)*, we
    need to use a for loop

    *Checkout the complete iterative version for
    the bubble sort code
    """
    start_idx = 1
    for i in range(len(arr) - start_idx):
        start_idx = i
        arr = bubble_sort_recursive(arr)
    return arr

def sorting(arr): """ The above function handles what you could say one pass through the array. For the remaining n-2 passes (why n-2?)*, we need to use a for loop *Checkout the complete iterative version for the bubble sort code """ start_idx = 1 for i in range(len(arr) - start_idx): start_idx = i arr = bubble_sort_recursive(arr) return arr

In [15]:

arr = [10, 1, 7, 6, 14, 9]
arr = [64, 25, 12, 22, 11]

arr = [10, 1, 7, 6, 14, 9] arr = [64, 25, 12, 22, 11]

In [16]:

bubble_sort_recursive(arr)

bubble_sort_recursive(arr)

Out[16]:

[25, 12, 22, 11, 64]

In [17]:

sorting(arr)

sorting(arr)

Out[17]:

[11, 12, 22, 25, 64]

Alternative version of the code learned from: Lecture34: Recursion with Strings | Day-4 | 10 Day Recursion Challenge

In [18]:

def bubble_sort_recursive_alt(arr, size):

    # 1. Base case
    if size == 0 or size == 1:
        return arr

    # 2. Processing
    # swap until the largest element gets bubbled
    # out to te last.
    # the extent of the for loop is again size-1
    # as we know that in each iteration
    # the largest remaining elements moves to the last
    for i in range(size - 1):
        if arr[i] > arr[i + 1]:
            arr[i], arr[i + 1] = arr[i + 1], arr[i]
        # 3. Recursive relation
        # recurse for the number of times or rounds
    bubble_sort_recursive_alt(arr, size - 1)

    return arr

def bubble_sort_recursive_alt(arr, size): # 1. Base case if size == 0 or size == 1: return arr # 2. Processing # swap until the largest element gets bubbled # out to te last. # the extent of the for loop is again size-1 # as we know that in each iteration # the largest remaining elements moves to the last for i in range(size - 1): if arr[i] > arr[i + 1]: arr[i], arr[i + 1] = arr[i + 1], arr[i] # 3. Recursive relation # recurse for the number of times or rounds bubble_sort_recursive_alt(arr, size - 1) return arr

In [19]:

bubble_sort_recursive_alt(arr, len(arr))

bubble_sort_recursive_alt(arr, len(arr))

Out[19]:

[11, 12, 22, 25, 64]

In [ ]:

In [ ]: