In [3]:

    

def fib(n):
    if n==0:
        return 0
    if n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)


    

In [11]:

    

import time

t0=time.clock()
print fib(30)
t1=time.clock()


    

    




832040

In [10]:

    

t1-t0


    

    
Out[10]:





0.41323374980191946

In [30]:

    

known={0:0,1:1}
def fib2(n):
    if n not in known:
        known[n] = fib2(n-1)+fib2(n-2)
    return known[n]


    

In [31]:

    

t0=time.clock()
print fib2(30)
t1=time.clock()
print t1-t0


    

    




832040
0.000200748970087

In [64]:

    

A=[5, 20, 1, -4, 6, -6, 5, 5, 20, 1, -4, 6, -6, 5]
def insertionSort(A):
    for i in range(len(A)):
        j=i
        while j>0 and A[j-1]>A[j]:
            A[j-1], A[j]= A[j], A[j-1]
            j-=1
    return A

t0=time.clock()
print insertionSort(A)
t1=time.clock()
print t1-t0


    

    




[-6, -6, -4, -4, 1, 1, 5, 5, 5, 5, 6, 6, 20, 20]
0.000231949218687

In [70]:

    

def quickSort(A):
    if len(A)<=1:
        return A
    else:
        pivot=A[0]
        #A=A[1:len(A)]
        #left= [i for i in A if i<=pivot]
        #right= [i for i in A if i > pivot]
        left=[]
        right=[]
        for i in range(1,len(A)):
            if A[i]<=pivot:
                left.append(A[i])
            else:
                right.append(A[i])            
        left = quickSort(left)
        right = quickSort(right)
        return left + [pivot] + right

t0=time.clock()
print quickSort(A)
t1=time.clock()
print t1-t0


    

    




[-6, -6, -4, -4, 1, 1, 5, 5, 5, 5, 6, 6, 20, 20]
0.00024754934293

In [78]:

    

def merge(left,right):
    if left[len(left)-1] <= right[0]:
        return left + right
    else:
        a=0
        b=0
        result=[]
        while a<len(left) and b<len(right):
            if left[a]<=right[b]:
                result.append[left[a]]
                a+=1
            else:
                result.append[right[b]]
                b+=1
                
                
def mergeSort(A):
    if len(A)<=1:
        return A
    mid=len(A)//2
    left=A[:mid]
    right=A[mid:]
    left=mergeSort(left)
    right=mergeSort(right)
    return merge(left,right)
    
t0=time.clock()
print mergeSort(A)
t1=time.clock()
print t1-t0


    

    




[-6, -6, -4, -4, 1, 1, 5, 5, 5, 5, 6, 6, 20, 20]
0.000243444047555

In [84]:

    

def bubbleSort(A):
    for i in range(len(A)):
        for j in range(1,len(A)-i):
            if A[j-1]>A[j]:
                A[j-1], A[j]= A[j], A[j-1]
    return A

bubbleSort(A)


    

    
Out[84]:





[-6, -6, -4, -4, 1, 1, 5, 5, 5, 5, 6, 6, 20, 20]

In [ ]: