## Fonctions pour les piles
def estvide(p):
    return(p==[])

def newpile():
    return([])

def depile(p):
    return(p.pop())

def empile(x,p):
    p.append(x)

def sommet(p):
    return(p[-1])
##
import matplotlib.pyplot as plt
from random import randint
L1 = [2*i+1 for i in range(10)]
L2 = [2*i for i in range(10)]

def listalea(a,b,n):
    return([randint(a,b) for i in range(n)])

def fusion1(L1,L2):
    if L1 == [] or L2 == []:
        return(L1+L2)
    if L1[0] <= L2[0]:
        L = [L1[0]]
        L = L + fusion1(L1[1:len(L1)],L2)
    else :
        L = [L2[0]]
        L = L + fusion1(L1,L2[1:len(L2)])
    return(L)



def fusion3(L1,L2):
    i1,i2,n1,n2=0,0,len(L1),len(L2)
    L=[]
    while i1<n1 and i2<n2:
        if L1[i1]<L2[i2]:
            L.append(L1[i1])
            i1+=1
        else:
            L.append(L2[i2])
            i2+=1
    if i1==n1:
        L = L + L2[i2:]
    else:
        L = L + L1[i1:]
    return L



def trifusion1(L):
    n = len(L)
    if n <=1:
        return L[:]
    else :
        n1 = n//2
        return(fusion3(trifusion1(L[:n1]),trifusion1(L[n1:])))
        

print(L1+L2,fusion2(L1,L2),sep = '\n')
print(trifusion1(L1+L2))


from time import clock
plt.figure('Complexite')
T = []
for n in range(2,900,20):
   tau = 0
   for i in range(100):
       L = listalea(0,n,n)
       t1 = clock()
       trifusion1(L)
       t2 = clock()
       tau = tau+(t2-t1)/15
   T.append(tau)

plt.plot([T[i]/i for i in range(2,len(T)-2)])
plt.show()

# Lineaire

## Tri Rapide :


def partage1(L,p):
    L1 = []
    L2 = []
    for i in L:
        if i < p :
            L1.append(i)
        else :
            L2.append(i)
    return(L1,L2)

def partage2(L):
    p = L[0]
    k = 0
    for i in range(1,len(L)):
        if L[i]<=p:
            if i == k+1:
                L[i],L[k] = L[k],L[i]
            else :
                L[k],L[k+1],L[i] = L[i],L[k],L[k+1]
            k = k+1
    return(L)


def estrie(L):
    if len(L) <= 1:
        return True
    else :
        if L[0]<=L[-1]:
            return estrie(L[1:])
    return False

def trirapide1(L):
    if len(L) <=1 :
        return L
    else :
        return(trirapide1(partage1(L[1:],L[0])[0]) +[L[0]] + trirapide1(partage1(L[1:],L[0])[1]))


##from time import clock
##plt.figure('Complexite')
##T = [[],[]]
##for n in range(2,900):
##    L = listalea(0,n,n)
##    t1 = clock()
##    trifusion1(L)
##    t2 = clock()
##    T[0].append(t2-t1)
##    t1 = clock()
##    trirapide1(L)
##    t2 = clock()
##    T[1].append(t2-t1)
##
##plt.plot([T[0][i]/(i+2) for i in range(2,len(T[0])-2)])
##plt.plot([T[1][i]/(i+2) for i in range(2,len(T[0])-2)], label = 'Tri Rapide')
##plt.legend()
##plt.show()


def comparaison(F):
    """F une liste de noms de fonctions"""
    from time import clock
    plt.figure("Comparaison " + str(F))
    T = [[]]*len(F)
    for i in range(len(F)):
        for n in range(2,900,10):
            tau = 0
            for j in range(12):
                L = listalea(0,n,n)
                t1 = clock()
                F[i](L)
                t2 = clock()
                tau = tau+(t2-t1)/12
            T[i].append(tau)
        plt.plot([T[i][k]/(k+2) for k in range(2,len(T[i])-2)],label = str(F[i]))
        print(len(T[i]))
    plt.legend()
    plt.show()

#comparaison([trifusion1,trirapide1])





##plt.figure('trifusion1')
##plt.plot(L)
##plt.plot(trifusion1(L))
##plt.show()