Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Time complexity:

Average case : n2

Worst case : n2

Best case : n

Bubble sort is considered a very slow sorting algorithm and is mainly used in academic settings to illustrate time complexity with an example. One case where Bubble sort performs very well is when the list is already sorted. The best case has a time complexity of n.

Implementation of Bubble sort:

def bubblesort(to_sort):
    list_len = len(to_sort)
    while list_len>0:
        new_n = 0
        for ix in range(1,list_len): #checks till n-1
            if to_sort[ix-1] > to_sort[ix]:
                temp = to_sort[ix-1]
                to_sort[ix-1] = to_sort[ix]
                to_sort[ix] = temp
                new_n = ix
        list_len = new_n
    return to_sort
    
if __name__ == "__main__":
    to_sort = [1,3,2,0,-1,4,5]
    print(bubblesort(to_sort))

Output:

[-1, 0, 1, 2, 3, 4, 5]

The above implementation has an optimization : new_n keeps track of the last index at which a swap occured and in the next iteration list_len is set to new_n, so if more than one value bubbles up to it’s correct position, there is no need to check if it’s in the correct position in the next iteration. (Ignore the poor naming of variables).

References :