notebook.community

Edit and run

from http://nbviewer.ipython.org/github/rasbt/algorithms_in_ipython_notebooks/blob/master/ipython_nbs/sorting/sorting_algorithms.ipynb?create=1#Bubble-sort



In [1]:

    
def python_bubblesort(a_list):
    """ Bubblesort in Python for list objects (sorts in place)."""
    length = len(a_list)
    for i in range(length):
        for j in range(1, length):
            if a_list[j] < a_list[j-1]:
                a_list[j-1], a_list[j] = a_list[j], a_list[j-1]
    return a_list



In [2]:

    
def python_bubblesort_improved(a_list):
    """ Bubblesort in Python for list objects (sorts in place)."""
    length = len(a_list)
    swapped = 1
    for i in range(length):
        if swapped: 
            swapped = 0
            for ele in range(length-i-1):
                if a_list[ele] > a_list[ele + 1]:
                    temp = a_list[ele + 1]
                    a_list[ele + 1] = a_list[ele]
                    a_list[ele] = temp
                    swapped = 1
    return a_list



In [3]:

    
import random
import copy
random.seed(4354353)

l = [random.randint(1,1000) for num in range(1, 1000)]
l_sorted = sorted(l)
for f in [python_bubblesort, python_bubblesort_improved]:
    assert(l_sorted  == f(copy.copy(l)))
print('Bubblesort works correctly')









    



Bubblesort works correctly



In [4]:

    
# small list

l_small = [random.randint(1,100) for num in range(1, 100)]
l_small_cp = copy.copy(l_small)

%timeit python_bubblesort(l_small)
%timeit python_bubblesort_improved(l_small_cp)









    



1000 loops, best of 3: 1.4 ms per loop
100000 loops, best of 3: 19 µs per loop