

In [1]:

    
{
    "nb_display_name": "Bubble Sort",
    "nb_description": "An example implementation of bubble sort",
    "nb_filename": "bubble_sort.ipynb",
    "params":[
        {
            "name":"user_id",
            "display_name":"Test num",
            "description":"",
            "input_type":"integer"
        },
        {
            "name":"username",
            "display_name":"Test str",
            "description":"",
            "input_type":"string"
        }
    ]
}









    Out[1]:





{'nb_description': 'An example implementation of bubble sort',
 'nb_display_name': 'Bubble Sort',
 'nb_filename': 'bubble_sort.ipynb',
 'params': [{'description': '',
   'display_name': 'Test num',
   'input_type': 'integer',
   'name': 'user_id'},
  {'description': '',
   'display_name': 'Test str',
   'input_type': 'string',
   'name': 'username'}]}

Sebastian Raschka



In [1]:

    
import time
print('Last updated: %s' %time.strftime('%d/%m/%Y'))









    



Last updated: 10/06/2014

Sorting Algorithms

Overview



In [2]:

    
import platform
import multiprocessing

def print_sysinfo():
    
    print('\nPython version  :', platform.python_version())
    print('compiler        :', platform.python_compiler())

    print('\nsystem          :', platform.system())
    print('release         :', platform.release())
    print('machine         :', platform.machine())
    print('processor       :', platform.processor())
    print('CPU count       :', multiprocessing.cpu_count())
    print('interpreter     :', platform.architecture()[0])
    print('\n\n')

Bubble sort

[back to top]

Quick note about Bubble sort

I don't want to get into the details about sorting algorithms here, but there is a great report
"Sorting in the Presence of Branch Prediction and Caches - Fast Sorting on Modern Computers" written by Paul Biggar and David Gregg, where they describe and analyze elementary sorting algorithms in very nice detail (see chapter 4).

And for a quick reference, this website has a nice animation of this algorithm.

A long story short: The "worst-case" complexity of the Bubble sort algorithm (i.e., "Big-O")
$\Rightarrow \pmb O(n^2)$



In [2]:

    
print_sysinfo()









    



Python version  : 3.4.0
compiler        : GCC 4.2.1 (Apple Inc. build 5577)

system          : Darwin
release         : 13.2.0
machine         : x86_64
processor       : i386
CPU count       : 4
interpreter     : 64bit

Bubble sort implemented in (C)Python



In [3]:

    
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

Below is a improved version that quits early if no further swap is needed.



In [4]:

    
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

Verifying that all implementations work correctly



In [5]:

    
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

Performance comparison



In [6]:

    
# 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.36 ms per loop
100000 loops, best of 3: 17.9 µs per loop



In [7]:

    
# larger list

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

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









    



1 loops, best of 3: 15.6 s per loop
1 loops, best of 3: 2.07 ms per loop