

In [11]:

    
import numpy as np

from IPython.display import clear_output
from pjdiagram import *
from ipywidgets import *

Bubble Sort

Summary

Performance	Complexity
Worst-case	$O(n^{2})$
Best-case	$O(n)$
Average	$O(n^{2})$
Worst-case space	$O(1)$

Algorithm

Perform a pass over list, performing a swap any time element $i+1$ is less than element $i$. Stop when no more swaps have been performed. Maximum number of passes will be $n^2$.

Code



In [18]:

    
def bubble_sort(lst):
    swapped = True
    
    # keep running until all the items have been swapped
    # NB: in the worst case scenario this will loop $n$ times
    while swapped:
        swapped = False
        
        # traverse entire list
        for i in range(len(lst)-1):
            
            # if next item is less than current item...
            if lst[i] > lst[i+1]:
                # swap values
                lst[i], lst[i+1] = lst[i+1], lst[i]
                
                # make sure we keep looping
                swapped = True

A quick demonstration of the algorithm:



In [20]:

    
lst = [5, 1, 2, 3, 6, 10, 2, 33, 7, 100]
bubble_sort(lst)

print(lst)









    



[1, 2, 2, 3, 5, 6, 7, 10, 33, 100]