# Tri par selection

L = [10, 3, 5, 6, 8, 12, 4, 7]

def indice_minimum(L, i):
    imin = i
    for k in range(i+1, len(L)):
        if L[k]<L[imin]:
            imin = k
    return imin

def tri_selection(L):
    n = len(L)
    for i in range(0,n-1):
        imin = indice_minimum(L,i)
        L[i], L[imin] = L[imin], L[i]

#pas stable, en place, comparatif, pire cas quadratique

# Tri par insertion

def tri_insertion(L):
    n = len(L)
    for i in range(1,n):
        j = i
        while j>0 and L[j-1] > L[j]:
            L[j-1], L[j] = L[j], L[j-1]
            j = j-1

#Version légèrement optimisée (on stocke la valeur de l'élément à insérer, on décale tous les éléments supérieurs à sa gauche et on le met dans le trou créé) :

def tri_insertion(L):
    n = len(L)
    for i in range(1,n):
        j = i
        x = L[j]
        while j>0 and L[j-1] > x:
            L[j] = L[j-1]
            j = j-1
        L[j] = x

#stable, en place, comparatif, pire cas quadratique

# Tri par partition-fusion

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

def tri_fusion(L):
    n = len(L)
    if n <=1:
        return L
    else:
       m = n//2
       L1 = tri_fusion(L[0:m])
       L2 = tri_fusion(L[m:n])
    return fusion(L1,L2)

#stable, pas en place, comparatif

# Tri rapide

def repartition(L):
    G = []
    M = []
    D = []
    n = len(L)
    pivot = L[n-1]
    for i in range(len(L)):
        x = L[i]
        if x < pivot:
            G.append(x)
        elif x > pivot:
            D.append(x)
        else:
            M.append(x)
    return G, M, D

def tri_rapide(L):
    if len(L) <= 1:
        return L
    G, M, D = repartition(L)
    return tri_rapide(G) + M + tri_rapide(D)

#stable, pas en place, comparatif

# Tri par comptage

def tri_comptage(L, p):
    n = len(L)
    D = [0]*(p+1)
    for i in range(n):
        D[L[i]]+=1
    L_triee = []
    for i in range(p+1):
        #Il faut ajouter D[i] fois i à L_triee
        for j in range(D[i]):
                L_triee.append(i)
    return L_triee

#pas stable, pas en place, pas comparatif



# Tri rapide en place :

def repartition_en_place(L, a, b):
    pivot = L[b]
    ind_p = a
    for i in range(a,b):
        if L[i]<=pivot:
            L[i], L[ind_p] = L[ind_p], L[i]
            ind_p +=1
    L[b], L[ind_p] = L[ind_p], L[b]
    return ind_p

def tri_sous_liste(L, a, b):
    if b > a:
        ind_p = repartition_en_place(L,a,b)
        tri_sous_liste(L, a, ind_p-1)
        tri_sous_liste(L, ind_p+1, b)
    # si a=b (liste a un element), ou b<a (liste vide) la sous-liste est triee : condition d'arret.


def tri_rapide_en_place(L):
    tri_sous_liste(L,0,len(L)-1)

#stable, en place, comparatif


from time import *
from timeit import default_timer as time
import matplotlib.pyplot as plt
from random import *

def mesure_temps(k,n,p,d):
    X = [d*(i+1) for i in range(n)]
    Yselection = []
    Yinsertion = []
    Yfusion = []
    Yrapide = []
    Yrapideplace = []
    Ycomptage = []
    for i in range(n):
        print(i)
        start = time()
        for _ in range(k):
            tri_selection([randint(0,p) for _ in range(X[i])])
        Yselection.append(time() - start)

        start = time()
        for _ in range(k):
            tri_insertion([randint(0,p) for _ in range(X[i])])
        Yinsertion.append(time() - start)

        start = time()
        for _ in range(k):
            tri_fusion([randint(0,p) for _ in range(X[i])])
        Yfusion.append(time() - start)

        start = time()
        for _ in range(k):
            tri_rapide([randint(0,p) for _ in range(X[i])])
        Yrapide.append(time() - start)

        start = time()
        for _ in range(k):
            tri_comptage([randint(0,p) for _ in range(X[i])], p)
        Ycomptage.append(time() - start)

        start = time()
        for _ in range(k):
            tri_rapide_en_place([randint(0,p) for _ in range(X[i])])
        Yrapideplace.append(time() - start)
    plt.plot(X, Yselection,"r-", label = "Tri sélection")
    plt.plot(X, Yinsertion,"r--", label = "Tri insertion")
    plt.plot(X, Yfusion, "b-",label = "Tri fusion")
    plt.plot(X, Yrapide ,"b--",  label = "Tri rapide")
    plt.plot(X, Ycomptage,"y-", label = "Tri comptage")
    plt.plot(X, Yrapideplace , "y--",label = "Tri rapide en place")
    plt.legend()
    plt.show()

mesure_temps(100,100,1000,2)