## TP S7 Tris(1)
from copy import deepcopy
from random import randint
from time import perf_counter
import matplotlib.pyplot as plt


## Q1

def generer_liste(n,mini, maxi):
    '''
    génère une liste de n entiers entre min et maxi
    '''
    assert mini < maxi
    return [randint(mini,maxi) for i in range(n)]

## Q2
def tri_selection(liste_a_trier):
    '''
    trie la liste_a_trier dans l'ordre croissant
    '''
    n = len(liste_a_trier)
    for i in range(n-1):
        imin = i
        for j in range(i+1, n): # selection indice mini
            if liste_a_trier[j] < liste_a_trier[imin]:
                imin = j
        if imin != i: # echange elt liste
            liste_a_trier[imin], liste_a_trier[i] = liste_a_trier[i], liste_a_trier[imin]
    #print(liste_a_trier)

##Q3
def tri_insertion(liste_a_trier):
    '''
    trie la liste_a_trier dans l'ordre croissant
    '''
    n = len(liste_a_trier)
    for i in range(n):
        a_placer = liste_a_trier[i]
        j = i-1
        while (j >= 0) and liste_a_trier[j] > a_placer:
        # déplacer les elts plus grand que a_placer
            liste_a_trier[j+1] = liste_a_trier[j]
            j = j-1
        # insérer a_placer
        liste_a_trier[j+1] = a_placer
    #print(liste_a_trier)

## Q4
def perf_algo(f_tri, taille, val_max, n_tests):
    # génère des listes aléatoires
    somme_perf = 0
    for i in range(n_tests):
        start = perf_counter()
        liste_a = generer_liste(taille, 0, val_max)
        f_tri(liste_a)
        perf = perf_counter() - start
        somme_perf += perf
    return somme_perf/n_tests


## Q5
def mesure_complexite(fonction, l_tailles, val_max, n_tests):
    '''
    renvoie la liste des perf moy en tps
    '''
    liste_perf = []
    for i in range(len(l_tailles)):
        liste_perf.append(perf_algo(fonction, l_tailles[i], val_max, n_tests))
    return liste_perf


##Q7
def Tri_bulle(liste_a_trier):
    '''
    trie la liste_a_trier dans l'ordre croissant
    '''
    n = len(liste_a_trier)
    for i in range(n-1):
        for j in range(n-1,i,-1): #[n-1, n-2, ..., i+1]
            if liste_a_trier[j] < liste_a_trier[j-1]:
                # permuter
                liste_a_trier[j], liste_a_trier[j-1] = liste_a_trier[j-1], liste_a_trier[j]


## Post-processing
#Tracés Perf
liste_test_tailles = [i for i in range(11)] + [15] + [10*k for k in range(2, 31)]

n_tests, val_max = 500, 200

liste_perf_TriBulle = mesure_complexite(Tri_bulle,liste_test_tailles,val_max,n_tests)

liste_perf_TriIns = mesure_complexite(tri_insertion,liste_test_tailles,val_max,n_tests)

liste_perf_TriSel = mesure_complexite(tri_selection,liste_test_tailles,val_max,n_tests)

# Tracé
plt.figure(1)
plt.plot(liste_test_tailles,liste_perf_TriIns, label='Tri par insertion')
plt.plot(liste_test_tailles,liste_perf_TriSel, label='Tri par selection')
plt.plot(liste_test_tailles,liste_perf_TriBulle, label='Tri à bulles')
plt.legend()
plt.grid()
plt.show()