import random
import time
import matplotlib.pyplot as plt

# Pour tester
def genere_tableau(n):
    return [random.random() for _ in range(n)]

# Exercice 1
def echange(tab, i, j):
    tmp = tab[i]
    tab[...] = tab[...]
    tab[...] = ...

# Exercice 2
def est_trie(tab):
    for i in range(len(tab)-1): # On s'arrête sur l'avant dernier élément
        if ...:
            return False
    return True

# Exercice 3
# Décommenter les lignes suivantes une fois que l'exercice 2 est fait
#assert not est_trie([4, 1, 2])
#assert est_trie([1, 2, 4])

# Exercices 4 et 6
def tri_bulles(tab):
    n = len(tab)
    #nb_tests = 0  # Pour plus tard
    #nb_echanges = 0  # Pour plus tard
    for i in range(...): # On va jusqu'à l'avant dernier
        for j in range(..., i, -1): # On va du dernier à i+1
            if ...:
                echange(tab, j-1, j)
    #print(tab)  # Pour tester, si on veut
    #return nb_tests, nb_echanges # Pour plus tard

# Exercice 5
def test_tri_bulles(n, k):
    for i in range(...):
        tab = genere_tableau(...)
        tri_bulles(...)
        if not ...:
            return False
    return True

# Exercices 7 et 9
def tri_selection(tab):
    n = len(tab)
    #nb_tests = 0
    #nb_echanges = 0
    for i in range(...):
        k = ...
        for j in range(..., n):
            if tab[j] < tab[k]:
                k = ...
        if i != k:
            echange(tab, ..., ...)
    #print(tab)  # Pour tester, si on veut
    #return nb_tests, nb_echanges

# Exercice 8
def test_tri_selection(n, k):
    ...

# Exercices 10 et 12
def tri_insertion(tab):
    n = len(tab)
    #nb_tests = 0
    #nb_echanges = 0
    for i in range(..., n):
        j = ...
        while j > ... and tab[...] > tab[...]:
            echange(tab, j-1, j)
            j = ...
    #print(tab)  # Pour tester, si on veut
    #return nb_tests, nb_echanges

# Exercice 11
def test_tri_insertion(n, k):
    ...
    
# Exercice 13
def comparaison(tab):
    t1 = tab.copy()
    nb_t, nb_e = tri_bulles(t1)
    print(f"Tri a bulles :      {nb_t:2} tests et {nb_e:2} échanges")
    t1 = tab.copy()
    nb_t, nb_e = tri_selection(t1)
    print(f"Tri par sélection : {nb_t:2} tests et {nb_e:2} échanges")
    t1 = tab.copy()
    nb_t, nb_e = tri_insertion(t1)
    print(f"Tri pas insertion : {nb_t:2} tests et {nb_e:2} échanges")

# Exercice 14
def moyenne(liste):
    ...

# Exercice 15
def temps_tri(tab, algo_tri):
    debut = time.time()
    algo_tri(tab)
    return time.time()-debut

def comparaison_temps(n, k):
    t_bulles = []
    t_selection = []
    t_insertion = []
    for i in range(k):
        tab = genere_tableau(n)
        t_bulles.append(temps_tri(tab.copy(), tri_bulles))
        t_selection.append(temps_tri(tab.copy(), tri_selection))
        t_insertion.append(temps_tri(tab.copy(), tri_insertion))
    print(f"Tri à bulles : {moyenne(t_bulles):.4}")
    print(f"Tri par sélection : {moyenne(t_selection):.4}")
    print(f"Tri par insertion : {moyenne(t_insertion):.4}")

# Exercice 16
def graphique_temps(n_max, k, points=10):
    t_taille = [] # pour les abscisses
    t_bulles = [] # Tableaux des ordonnées pour les 3 algos
    t_selection = []
    t_insertion = []
    pas = n_max//points # distance entre les abscisses des points
    n = pas
    for _ in range(points):
        t_taille.append(n)
        temps_bulles = 0         # somme des temps de calcul
        temps_selection = 0      # pour des listes de taille n
        temps_insertion = 0      # pour les 3 algos
        for _ in range(k):
            tab = genere_tableau(n)
            temps_bulles += temps_tri(tab.copy(), tri_bulles)
            temps_selection += temps_tri(tab.copy(), tri_selection)
            temps_insertion += temps_tri(tab.copy(), tri_insertion)
        # On rajoute les temps moyens aux listes des ordonnées
        t_bulles.append(temps_bulles/k)
        t_selection.append(temps_selection/k)
        t_insertion.append(temps_insertion/k)
        n = n + pas
    # affichage des courbes
    plt.plot(t_taille, t_bulles, label="bulles")
    plt.plot(t_taille, t_selection, label="selection")
    plt.plot(t_taille, t_insertion, label="insertion")
    plt.legend()
    plt.show()

def genere_tableau_presque_trie(n, k=20):
    tab = list(range(n))
    for _ in range(k):
        # on fait k échanges au hasard
        echange(tab, random.randint(0, n-1), random.randint(0, n-1))
    return tab