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

## Rappel du TP précédent : générateur
def generateur(n):
    return [rd.randint(1,n) for k in range(n)]

## Question 1 (somme)



## Question 2 (palindrome)



## Question 3 (partition)



## Question 4 (tri_rapide)
def tri_rapide(lst):
    if len(lst) <= ...:
        return ...
    else:
        ... = partition(lst)
        return tri_rapide(...) + ... + tri_rapide(...)

## Question 5 (temps - tri_rapide)
for k in range(4,7):
    print("k=", ...)
    lst = generateur(...)
    t0 = ...
    ...
    t1 = ...
    print(...)


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


## Question 7 (tri_fusion)



## Question 8 (à lire et comprendre)
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 9 (tri_fusion2)


## Question 10 (temps - tri_fusion / tri_fusion2)
print("temps pour tri_fusion2")
for k in range(...):
    ...
    ...

sys.setrecursionlimit(40000)

print("temps poour tri_fusion")
for k in range(...):
    ...
    ...

## Question 11 (comparaison graphique des performances)

# Fonctions du TP précédent (tris itératifs), rappelées pour la comparaison
def tri_selection(liste):
    n = len(liste)
    for i in range(n-1):
        j_min = i
        for j in range(i+1,n):
            if liste[j] < liste[j_min]:
                j_min = j
        liste[i], liste[j_min] = liste[j_min], liste[i]

def tri_insertion(tab):
    n = len(tab)
    for i in range(1,n):
        x = tab[i]
        j = i - 1
        while j >= 0 and tab[j] > x:
            tab[j+1] = tab[j]
            j = j-1
        tab[j+1] = x

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]

# Comparaison des temps moyen d'exécution des 5 algorithmes de tri
longueurs = list(range(100, ..., ...))
liste_algos = [tri_selection,tri_insertion,tri_bulle,tri_fusion,tri_rapide]
temps = [[] for k in range(len(liste_algos))]
for n in longueurs:
    N = 20
    for k in range(...):
        tps = 0
        for i in range(N):
            lst = ...
            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()