Sorting Algorithms

In this notebook, serveral algorithms are displayed and compared



In [54]:

    
from random import shuffle

testdata = [i for i in range(1000)]
shuffle(dataset)

Bubble Sort



In [55]:

    
# %load bubble.py
def bubble(iterable):
    done = False
    while not done:
        done = True
        for i in range(len(iterable) - 1):
            if iterable[i] > iterable[i + 1]:
                iterable[i], iterable[i + 1] = iterable[i + 1], iterable[i]
                done = False
    return iterable



In [56]:

    
%%timeit
bubble(testdata)









    



1000 loops, best of 3: 204 µs per loop



In [57]:

    
# %load cocktail_bubble.py
def cocktail_bubble(iterable):
    d = 0
    l = len(iterable) - 1
    while d * 2 < l:
        a = range(d, l - d)
        bare = range(l - d, d, -1)
        for i, j in zip(a, bare):
            if iterable[i] > iterable[i + 1]:
                iterable[i], iterable[i + 1] = \
                    iterable[i + 1], iterable[i]
            if iterable[j] < iterable[j - 1]:
                iterable[j], iterable[j - 1] = \
                    iterable[j - 1], iterable[j]
        d += 1
    return iterable



In [58]:

    
%%timeit
cocktail_bubble(testdata)









    



1 loop, best of 3: 118 ms per loop



In [59]:

    
# %load false_bubble_0.py
def false_bubble_0(iterable):
    l = len(iterable)
    for i in range(0, l - 1):
        for j in range(0, l):
            if iterable[i] > iterable[j] and j > i:
                iterable[i], iterable[j] = iterable[j], iterable[i]
    return iterable



In [60]:

    
%%timeit
false_bubble_0(testdata)









    



10 loops, best of 3: 161 ms per loop



In [61]:

    
# %load false_bubble_i.py
def false_bubble_i(iterable):
    l = len(iterable)
    for i in range(0, l - 1):
        for j in range(i, l):
            if iterable[i] > iterable[j]:
                iterable[i], iterable[j] = iterable[j], iterable[i]
    return iterable



In [62]:

    
%%timeit
false_bubble_i(testdata)









    



10 loops, best of 3: 66.6 ms per loop



In [63]:

    
# %load insertion.py
def insertion(iterable):
    done = False
    while not done:
        done = True
        for i in range(len(iterable) - 1):
            if not iterable[i] < iterable[i + 1]:
                done = False
                j = i
                while not (iterable[j] < iterable[j + 1]) and j >= 0:
                    iterable[j], iterable[j + 1] = \
                        iterable[j + 1], iterable[j]
                    j -= 1
    return iterable



In [64]:

    
%%timeit
insertion(testdata)









    



1000 loops, best of 3: 200 µs per loop



In [65]:

    
# %load selection.py
def selection(iterable):
    first = 0
    last = len(iterable) - 1
    while first < last:
        minimo = iterable[first]
        for i in range(first, last + 1):
            if iterable[i] < minimo:
                minimo = iterable[i]
        minindex = iterable.index(minimo)
        iterable[first], iterable[minindex] = \
            iterable[minindex], iterable[first]
        first += 1
    return iterable



In [66]:

    
%%timeit
selection(testdata)









    



10 loops, best of 3: 62.6 ms per loop



In [67]:

    
# %load cocktail_selection.py
def cocktail_selection(iterable):
    first = 0
    last = len(iterable) - 1
    while first < last:
        minimo = iterable[first]
        maximo = iterable[last]
        for i in range(first, last + 1):
            if iterable[i] > maximo:
                maximo = iterable[i]
            if iterable[i] < minimo:
                minimo = iterable[i]
        minindex = iterable.index(minimo)
        iterable[first], iterable[minindex] = \
            iterable[minindex], iterable[first]
        maxindex = iterable.index(maximo)
        iterable[last], iterable[maxindex] = \
            iterable[maxindex], iterable[last]
        first += 1
        last -= 1
    return iterable



In [68]:

    
%%timeit
cocktail_selection(testdata)









    



10 loops, best of 3: 57.6 ms per loop



In [ ]:



In [ ]:



In [ ]: