import random as rd
import matplotlib.pyplot as plt
from numpy import log
L = [rd.randint(0,10) for i in range(10)]
L2 =[i for i in range(10)] + [rd.randint(0,8)+.5 for i in range(10)]
K = [0,1,2,3,4,5,6,7,8,9,0.5]
def permutalea2(n):
#complexite lineaire
    L = [i for i in range(n)]
    for i in range(n):
        a = rd.randint(0,n-i-1)
        L[a],L[n-1-i]=L[n-1-i],L[a]
    return(L)
P = permutalea2(10)
print(P)

def indmax(L):
    n = len(L)
    m = L[0]
    c = 0
    for i in range(n) :
        if m<L[i]:
            m = L[i]
            c = i
    return c
            
def Triselect(L):
    n = len(L)
    G = [i for i in L]
    for i in range(n):
        c = indmax(G)
        L[n-i-1]= G[c]
        del(G[c])

def chronometre1(f):
    from time import clock
    T = []
    N = []
    for i in range(50,3000,100):
        L = [rd.randint(0,1000) for k in range(i)]
        N.append(i)
        c = clock()
        f(L)
        d = clock()
        T.append(d-c)
    plt.plot(N[1:len(N)],[T[i]/N[i] for i in range(1,len(T))])
    plt.show()
    #donne une droite si quadratique

def TriS(L):
    n = len(L)
    G = [i for i in L]
    M = [0]*n
    for i in range(n):
        c = indmax(G)
        M[n-i-1]= G[c]
        del(G[c])
    return M

def insere(L,i):
    m = L[i]
    k = i
    while k >= 1 and L[k-1] >= m :
        L[k],L[k-1],k = L[k-1],L[k],k-1
    
def TriInsert(L):
    n = len(L)
    for i in range(n):
        insere(L,i)

#chronometre1(TriInsert)

def TriI(L) :
    G = [l for l in L]
    n = len(L)
    for i in range(n):
        insere(G,i)
    return G

def dicho(L,i):
    """Cherche l'indices tels que L[k-1] < L[i] < L[k] la liste est triee jusqu'a
    L[i-1]"""
    x = L[i]
    g = 0
    d = i
    m = (d+g)//2
    while (x > L[m] or x < L[m-1]) and g<d:
        if x >= L[m] :
            g = m+1
        if x < L[(m-1)*(m>0)] :
            d = m
        m = (d+g)//2
    return(m)

def insered(L,i):
    k = dicho(L,i)
    n = len(L)
    L[k],L[k+1:i+1] = L[i],L[k:i]

def TriInsertd(L):
    n = len(L)
    for i in range(1,n):
        insered(L,i)