Bubble Sort

Overview#

Time Complexity: Best - O(n), Worst - O(n^2)
Space Complexity: O(1)
In-Place
Stable

General Idea#

Think of bubbling each element across the array. Starting from the first element we compare it with the neighbouring element. If the current element is larger than the neighbouring element, we swap the positions. Now we increase the positions of both pointers by one and repeat the same.

At the end of the first iteration the largest element in the array is placed at the last index in the array.

Time Complexity#

As we can see, there are 2 loops. An outer loop which goes through the entire array and an inner loop which traverses from the current to the (arr.length - i - 1) index. This is because we do not need to consider the last i elements which have already been populated with the top i largest elements.

This yields a time complexity of O(n^2).

To optimise this, we can have a flag to check if any swaps have been made in the inner loop. If there are no swaps, this indicates that all the elements in the array have been sorted.

Space Complexity#

We only need some temporary variables to store things like the flag. Hence, space required is in order of O(1).

Implementation#

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        flag = False
        for j in range(n-i-1):
            if(arr[j] > arr[j+1]):
                # swap
                temp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = temp
                flag = True
        print(flag)
        if(flag is False):
            return arr
    return arr

if __name__ == "__main__":
    arr = [9,8,7,6,5,4,3,2,1]
    arr = bubble_sort(arr)
    print(arr)