import time
import random


import matplotlib.pyplot as plt


def tri_selection(tab):
    N = len(tab)
    for k in range(N - 1):  # Parcourir jusqu'à l'avant-dernier élément
        imin = k  # Initialiser l'indice du minimum à k
        for i in range(k + 1, N):  # Parcourir les éléments non triés
            if tab[i] < tab[imin]:  # Trouver le minimum
                imin = i
        tab[k], tab[imin] = tab[imin], tab[k]  # Échanger les éléments








def tri_insertion(tab):
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[i]  # On prend l'élément à insérer
        j = i  # On commence à comparer à partir de l'élément précédent
        # Tant qu'on n'a pas trouvé la place de l'élément à insérer
        # et que l'élément précédent est plus grand que l'élément à insérer
        while j > 0 and valeur_insertion < tab[j - 1]:
            tab[j] = tab[j - 1]  # On décale l'élément plus grand vers la droite
            j = j - 1  # On déplace le pointeur vers la gauche
        tab[j] = valeur_insertion  # On insère la valeur au bon endroit



def fusion(liste1,liste2):
    '''
    fusion prend deux listes triées et retourne une grand liste triée contenant les éléments des deux autres.
    '''
    final=[]   #liste qui sera retournée
    curseur1=0 #curseur de la liste1
    curseur2=0 #curseur de la liste2
    while curseur1<len(liste1) and curseur2<len(liste2)  : #tant que il reste des éléments non traités dans une des deux listes
        if liste1[curseur1]<liste2[curseur2]   : #le plus petit élément est dans la liste 1
            final.append(liste1[curseur1])
            curseur1+=1
        else: #le plus petit élément est celui de la liste 2
            final.append(liste2[curseur2])
            curseur2+=1

    if curseur1==len(liste1) : #il reste des éléments dans la liste 2 à traiter
        for i in range(curseur2,len(liste2)):
            final.append(liste2[i])
    else : #il reste des éléments dans la liste 1 à traiter
        for i in range(curseur1,len(liste1)):
            final.append(liste1[i])
    return final



listeA=[2,5,7,8,9,11,13,15,19,21,25,29,35,38,39,40,52,69,78,89]
listeB=[3,4,5,7,12,14,15,18,23,30,32,33,34,42,53]



def tri_fusion(liste):
    if len(liste)<=1 : # Il y a un élément dans la liste ou moins.
        return liste
    else:
        moitie=len(liste)//2  # indice correspondant au milieu de la liste
        gauche=tri_fusion(liste[:moitie])
        droite=tri_fusion(liste[moitie:])
        return fusion(gauche,droite)







def genere(n):
    '''
    genere une liste aléatoire de n nombres
    '''
    liste=[]
    for i in range(n):
        liste.append(random.randint(1,100000000000))
    return liste


def temps(tri,n :int):
    '''
    retourne le nombre de secondes pour trier une liste de taille n avec l'algorithme tri
    '''
    liste=genere(n)
    t1=time.time()
    tri(liste)
    return time.time()-t1


def tracer(tri,v_max,pas):

    # Série de points (exemple)
    points_x = []
    points_y = []
    x=0
    while x<=v_max:
        print(f"{x}->",end=' ')
        points_x.append(x)
        t=temps(tri,x)
        print(f"{t} secondes")
        points_y.append(t)
        x+=pas

    # Tracer les points et les relier
    plt.figure(figsize=(5,10))
    plt.plot(points_x, points_y, marker='o', linestyle='-', label="Mesure effectuée")

    # Ajouter des labels, une grille, et une légende
    plt.title(tri.__name__)
    plt.xlabel("taille de la liste")
    plt.ylabel("temps du tri en seconde")
    plt.grid(True)
    plt.legend()

    # Afficher le tracé
    plt.savefig(f'{tri.__name__}.png')

tracer(tri_fusion,300000,1000)