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.
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
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))
[-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).