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

## Question 1


## Question 2


## Question 3
def generateur(n):
    return [rd.randint(1,n) for k in range(n)]

## Question 4
def fusion(lst1, lst2):
    if lst1 == []:
        return ...
    elif ... == []:
        return ...
    else:
        x1 = lst1[...]
        x2 = ...
        if x1 < x2:
            return [...] + fusion(..., ...)
        else:
            return ... + fusion(..., ...)


def fusion2(lst1, lst2):
    i1, i2 = 0, 0
    n1, n2 = len(lst1), len(lst2)
    lst = []
    while i1 + i2 < n1 + n2:
        if i1 == n1:
            return lst + lst2[i2:]
        elif i2 == n2:
            return lst + lst1[i1:]
        elif lst1[i1] < lst2[i2]:
            lst.append(lst1[i1])
            i1 += 1
        else:
            lst.append(lst2[i2])
            i2 += 1
    return lst

## Question 5



## Question 6
sys.setrecursionlimit(40000)

# temps pour tri_fusion
for k in ...:
    n = ...
    print("n=",n)
    liste = generateur(n)
    t0 = t.time()
    ...
    t1 = t.time()
    print(...)

# idem pour tri_fusion 2

## Question 7


## Question 8


## Question 9


## Question 10


## Question 11


## Question 12
def tri_insertion(tab):
    n = len(tab)
    for i in range(..., ...):
        x = tab[i]
        j = i - 1
        while j >= ... and ... :
            tab[...] = tab[...]
            j = ...
        tab[...] = ...


## Question 13


## Question 14
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 15


## Question 16
longueurs = list(range(100,...,...))
liste_algos = [tri_selection,tri_insertion,tri_bulle,tri_fusion,tri_rapide]
temps = [[] for k in range(5)]
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()