def python_bubblesort(a_list):
    """ Plain Python implementation of bubble sort (sorts in place) """
    count = len(a_list)
    for i in range(count):
        for j in range(1, count):
            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

import random
random.seed(12345)

l = [random.randint(1,100) for num in range(1, 100)]
assert(sorted(l) == python_bubblesort(l))
print('bubble sort works correctly')

%load_ext cythonmagic

%%cython
cimport cython
cpdef cython_bubblesort_notypes(a_list):
    """ 
    The Python implementation of bubble sort compiled
    via Cython without C type definitions.
    
    """
    count = len(a_list)
    for i in range(count):
        for j in range(1, count):
            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

%%cython
cimport cython
cpdef cython_bubblesort_ctypes(a_list):
    """ 
    Cython implementation of bubble sort with static
    type declarations.
    
    """
    cdef int count, i, j # static type declarations
    count = len(a_list)
    for i in range(count):
        for j in range(1, count):
            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

%%cython
cimport cython
from libc.stdlib cimport malloc, free

cpdef cython_bubblesort_clist(a_list):
    """ 
    The Cython implementation of bubble sort with internal
    conversion between Python list objects and C arrays.
    
    """
    cdef int *c_list
    c_list = <int *>malloc(len(a_list)*cython.sizeof(int))
    cdef int count, i, j # static type declarations
    count = len(a_list)
    
    # convert Python list to C array
    for i in range(count):
        c_list[i] = a_list[i]

    for i in range(count):
        for j in range(1, count):
            if c_list[j] < c_list[j-1]:
                c_list[j-1], c_list[j] = c_list[j], c_list[j-1]

    # convert C array back to Python list
    for i in range(count):
        a_list[i] = c_list[i]
        
    free(c_list)
    return a_list

%%cython
import numpy as np
cimport numpy as np
cimport cython
@cython.boundscheck(False) 
@cython.wraparound(False)
cpdef cython_bubblesort_numpy(inp_ary):
    """ The Cython implementation of Bubblesort with NumPy memoryview."""
    cdef unsigned long length, i, swapped, ele, temp
    cdef long[:] np_ary = inp_ary
    length = np_ary.shape[0]
    swapped = 1
    for i in range(0, length):
        if swapped: 
            swapped = 0
            for ele in range(0, length-i-1):
                if np_ary[ele] > np_ary[ele + 1]:
                    temp = np_ary[ele + 1]
                    np_ary[ele + 1] = np_ary[ele]
                    np_ary[ele] = temp
                    swapped = 1
    return inp_ary

from numba import jit
@jit
def numba_bubblesort(a_list):
    """ Numba implementation of bubble sort (sorts in place) """
    count = len(a_list)
    for i in range(count):
        for j in range(1, count):
            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

from numba import jit
@jit
def numba_bubblesort_numpy(np_ary):
    """ 
    Numba implementation of bubble sort (sorts in place),
    It is identical to numba_bubble_sort(), but we will feed
    a numpy array type to this function.
    
    """
    count = np_ary.shape[0]
    for i in range(count):
        for j in range(1, count):
            if np_ary[j] < np_ary[j-1]:
                np_ary[j-1], np_ary[j] = np_ary[j], np_ary[j-1]
    return np_ary

import random
import copy
import numpy as np
random.seed(12345)

l = np.asarray([random.randint(1,1000) for num in range(1, 1000)])
l_sorted = np.sort(l)
for f in [python_bubblesort, cython_bubblesort_ctypes, 
          cython_bubblesort_notypes, cython_bubblesort_clist, 
          cython_bubblesort_numpy, numba_bubblesort, 
          numba_bubblesort_numpy]:
    assert(l_sorted.all() == f(copy.copy(l)).all())
print('Bubblesort works correctly')

import timeit
import random
import copy
import numpy as np
random.seed(4567)

def make_copy(l):
    return copy.deepcopy(l)

funcs = ['python_bubblesort', 'numba_bubblesort', 
         'cython_bubblesort_notypes', 'cython_bubblesort_ctypes', 
         'cython_bubblesort_clist', 'cython_bubblesort_numpy', 
         'numba_bubblesort_numpy'
         ]

orders_n = [10**n for n in range(1, 5)]
timings = {f:[] for f in funcs}


for n in orders_n:
    l = [np.random.randint(n) for num in range(n)]
    for f in funcs:
        l_copy = make_copy(l)
        if f in ['numba_bubblesort_numpy', 'cython_bubblesort_numpy']:
            l_copy = np.asarray(l_copy)
        timings[f].append(min(timeit.Timer('%s(l_copy)' %f, 
                      'from __main__ import %s, l_copy' %f)
                              .repeat(repeat=5, number=10)))

import platform
import multiprocessing
from llvm import __version__ as llvm__version__
from numba import __version__ as numba__version__
from cython import __version__ as cython__version__

def print_sysinfo():
    
    print('\nPython version:', platform.python_version())
    print('compiler        :', platform.python_compiler())
    print('Cython version  :', cython__version__)
    print('NumPy version   :', np.__version__)
    print('Numba version   :', numba__version__)
    print('llvm version    :', llvm__version__)
    
    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')

%matplotlib inline

import matplotlib.pyplot as plt

def plot(timings, title, ranked_labels, labels, orders_n):
    plt.rcParams.update({'font.size': 12})

    fig = plt.figure(figsize=(11,10))
    for lb in ranked_labels:
        plt.plot(orders_n, timings[lb], alpha=0.5, label=labels[lb], 
                 marker='o', lw=3)
    plt.xlabel('sample size n (items in the list)')
    plt.ylabel('time per computation for 10 loops in seconds')
    plt.xlim([min(orders_n) / 10, max(orders_n)* 10])
    plt.legend(loc=2)
    plt.grid()
    plt.xscale('log')
    plt.yscale('log')
    plt.title(title)
    plt.show()

import prettytable

def summary_table(ranked_labels):
    fit_table = prettytable.PrettyTable(['n=%s' %orders_n[-1], 
                                         'bubblesort function' ,
                                         'time in sec.',
                                         'rel. performance gain'])
    fit_table.align['bubblesort function'] = 'l'
    for entry in ranked_labels:
        fit_table.add_row(['', labels[entry[1]], round(entry[0], 2), 
                           round(ranked_labels[0][0]/entry[0], 2)])
    print(fit_table)

title = 'Performance of bubblesort in Python, Cython, and Numba'

labels = {'python_bubblesort':'(C)Python - Python lists', 
          'numba_bubblesort': 'Numba - Python lists', 
          'cython_bubblesort_ctypes': 'Cython - with C types, Python lists',
          'cython_bubblesort_notypes': 'Cython - no type declarations, Python lists',
          'cython_bubblesort_clist': 'Cython - Python lists with to-C-array-conversion',
          'cython_bubblesort_numpy': 'Cython - NumPy arrays memoryview',
          'numba_bubblesort_numpy': 'Numba - NumPy arrays'
          }

ranked_by_time = sorted([(time[1][-1],time[0]) for time in timings.items()], reverse=True)



print_sysinfo()
plot(timings, title, [l for t,l in ranked_by_time], labels, orders_n)
summary_table(ranked_by_time)