Learn Everything about Bubble Sort in Python

Introduction

Bubble sort is one of the well-known sort techniques for sorting array-based data. It's a comparison-based algorithm. The name 'Bubble' is because it repeatedly compares each element with the other and set the highest element at the end of the array in each iteration. It happens like a water bubble goes up to the water surface from the ground level.

In this tutorial, you'll learn how to perform Bubble Sort in Python also with its working principle.

How does Bubble Sort Works?

Step 1

Step 2

Step 3

Algorithm for Bubble Sort

BubbleSort(array)
    length = Length of the array
    for i in range(0 to length)
        status = False
        for j in range(0 to length-i-1)
            if array[j] > array[j+1]
                Swap(array[j], array[j+1])
                status = True
        if status is False
            break

Without Recursion

Code

'''Program for Bubble Sort in python using list'''
def BubbleSort(arr):
    for i in range(len(arr)):
        status = False
        for j in range(0, len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # If the swap operation is performed set
                # the status 'True'. It implies the given array
                # isn't in the ascending order. 
                status = True
        # if swap operation is not perform in the
        # first iteration, i.e. array is already in
        # the ascending order; so, no need to check again
        if not status:
            break

# The main function
if __name__ == "__main__":
    arr = [9, 3, 6, 22, 8, 1]
    BubbleSort(arr)
    print("----The Sorted data----")
    print(arr)

Output

----The Sorted data----
[1, 3, 6, 8, 9, 22]

Bubble Sort using Recursion

Code

'''Program for Bubble Sort in python using Recursion'''
def BubbleSortRecursive(arr, size):
    for i in range(size-1):
        if arr[i] > arr[i+1]:
            # Swapping
            arr[i], arr[i+1] = arr[i+1], arr[i]
    if (size - 1) > 1:
        # Calling itself
        BubbleSortRecursive(arr, size-1)

# The main function
if __name__ == "__main__":
    arr = [9, 3, 6, 22, 8, 1]
    BubbleSortRecursive(arr, len(arr))
    print("----The Sorted data----")
    print(arr)

Output

----The Sorted data----
[1, 3, 6, 8, 9, 22]

Complexity Analysis

There are three conditions the array may have: In ascending order, descending order, or random order. The best-case occurs when the array is already sorted. The worst case happens when the array is in descending order and when the data item is in a random order, the average case occurs.

Time Complexity

Best Case: O(n)

Average Case: O(n^2)

Worst Case: O(n^2)

Space Complexity

For all conditions: O(1)