import random as rd
import matplotlib.pyplot as plt
import time as t

## Question 1 (générateur)


## Question 2 (minimum)


## Question 3 (tri par sélection - à trous)
def tri_selection(liste):
    n = len(liste)
    for i in range(...):
        i_min = ...
        for j in range(..., ...):
            if liste[j] < liste[...]:
                i_min = ...
        liste[i], liste[i_min] = ..., ...


## Question 4 (temps - sélection)


## Question 5 (tri par insertion - à trous)
def tri_insertion(tab):
    n = len(tab)
    for i in range(..., ...):
        x = tab[i]
        j = i - 1
        while j >= ... and ... :
            j = ...
        tab[... : ...] = tab[... : ..]
        tab[...]= x

## Question 6 (temps - insertion)


## Question 7 - BONUS pour les plus rapides (insertion dichotomique)


## Question 8 (tri bulle - à lire, code donné)
def tri_bulle(liste):
    n = len(liste)
    for i in range(n):
        for j in range(n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]


## Question 9 (tri bulle amélioré - à trous)
def tri_bulle_ameliore(liste):
    n = len(liste)
    trie = ...
    i = 0
    while not trie:
        trie = ...
        for j in range(n-i-1):
            if liste[j] > liste[j+1]:
                liste[j], liste[j+1] = liste[j+1], liste[j]
                trie = ...
        i = ...


## Question 10 (temps - bulle / bulle amélioré)


## Question 11 (stabilité)
liste_test = [(3,0),(1,1),(3,2),(2,3),(1,4),(3,5)]


## Question 12 (comparaison graphique)
longueurs = list(range(100,...,...))
liste_algos = [tri_selection,tri_insertion,tri_bulle]
temps = [[] for k in range(3)]
for n in longueurs:
    N = 10
    for k in range(...):
        tps = 0
        for i in range(N):
            liste = ...
            algo = liste_algos[k]
            t0 = ...
            algo(...)
            t1 = ...
            tps += ...
        temps[...].append(tps/N)
for k in range(...):
    algo = liste_algos[k]
    plt.plot(...,...,label=algo.__name__)
plt.legend(loc = "best")
plt.show()