## Exercice 1
def tri_rapide(l):
    """
    >>> tri_rapide([5, 4, 3, 2, 1])
    [1, 2, 3, 4, 5]
    >>> tri_rapide([])
    []
    >>> tri_rapide([1, 1, 1, 1])
    [1, 1, 1, 1]
    >>> tri_rapide([1, 2, 3, 4, 5, 6])
    [1, 2, 3, 4, 5, 6]
    >>> tri_rapide([0, 8, 9, 0, 17, 2, 8, 5])
    [0, 0, 2, 5, 8, 8, 9, 17]
    """
    pass # TODO

## Exercice 2
from random import randint # Renvoie un entier aléatoire entre 2 bornes
def liste_alea(taille):
    pass # TODO

def liste_triee(taille):
    pass # TODO

def liste_meilleur_cas(taille_totale):
    pass # TODO

# Ci-dessous : code fourni, pour affiche_et_pente

from time import perf_counter_ns # Renvoie le nombre de nanosecondes écoulées
def une_mesure(tri, liste):
    """
    Fonction auxiliaire de n_mesures.

    Entrées
    -------
      - tri : une fonction de tri
      - liste : une liste à trier

    Sortie
    ------
      Le temps mis par la fonction tri
      pour trier liste (en nanosecondes)
    """
    debut = perf_counter_ns()
    tri(liste)
    fin = perf_counter_ns()
    return fin - debut

def n_mesures(tri, gen, taille, nb_echantillons):
    """
    Fonction auxiliaire de points_courbe.
    
    Entrées
    -------
      - tri : une fonction de tri
      - gen : une fonction de génération de listes
      - taille : un entier
      - nb_echantillons : un entier

    Sortie
    ------
      Fait la moyenne sur nb_echantillons mesures
      du temps mis par la fonction tri
      pour trier des listes de taille taille.
      La fonction gen est utilisée pour générer
      les listes qui sont ensuite triées par la fonction tri.
    """
    assert(nb_echantillons > 0)
    somme = 0
    for _ in range(nb_echantillons):
        liste = gen(taille)
        somme += une_mesure(tri, liste)
    return somme / nb_echantillons

def points_courbe(tri, gen):
    """
    Fonction auxiliaire de affiche_et_pente.

    Entrées
    --------
      - tri : une fonction de tri
      - gen : une fonction de génération de listes

    Sortie
    -------
      Renvoie deux listes x et y,
      décrivant une courbe du temps moyen mis par la fonction tri
      pour trier des listes de différentes tailles
      générées avec la fonction gen.
    """
    l_tailles = []
    l_temps   = []
    taille = 255
    temps = 0
    while temps < 10**8: # Tant que la dernière mesure a pris moins de 0.1 secondes
      temps = n_mesures(tri, gen, taille, 3)
      l_tailles.append(taille)
      l_temps.append(temps)
      taille = taille * 2 + 1
    return l_tailles, l_temps

from scipy.stats import linregress
def regression_lineaire(x, y):
    """
    Fonction auxiliaire de affiche_et_pente.

    Effectue une régression linéaire sur la courbe
    décrite par les listes x et y.
    """
    regression = linregress(x, y)
    pente = round(regression.slope, 2)
    print("Si les points donnés décrivent une droite,", end=" ")
    print("alors la pente de cette droite est de ", pente)

from math import log
import matplotlib.pyplot as plt

def affiche_et_pente(tri, gen):
    x, y = points_courbe(tri, gen)
    x_log = [log(t) for t in x]
    y_log = [log(t) for t in y]
    plt.plot(x_log, y_log)
    plt.show()
    regression_lineaire(x_log, y_log)

# Les deux lignes suivantes évitent
# d'avoir l'erreur RecursionDepthExceeded
# lorsqu'on teste une version récursive
# de tri_rapide dans le cas où sa complexité
# est quadratique, sur des tailles d'entrées allant jusqu'à 100000
from sys import setrecursionlimit
setrecursionlimit(100000)

## Décommentez la ligne suivante
## pour tester la complexité de votre tri sur des listes aléatoires:
# affiche_et_pente(tri_rapide, liste_alea)

## Décommentez la ligne suivante
## pour tester la complexité de votre tri sur des listes déjà triées:
# affiche_et_pente(tri_rapide, liste_triee)

## Décommentez la ligne suivante
## pour tester la complexité de votre tri sur des listes particulièrement
## bien adaptées au tri rapide:
# affiche_et_pente(tri_rapide, liste_meilleur_cas)

## Exercice 3 : en place
def rapide_en_place(l):
    pass # TODO

def test_rapide_en_place():
    liste = [5, 4, 3, 2, 1]
    rapide_en_place(liste)
    assert(liste == [1, 2, 3, 4, 5])
    liste = []
    rapide_en_place(liste)
    assert(liste == [])
    liste = [1, 1, 1, 1]
    rapide_en_place(liste)
    assert(liste == [1, 1, 1, 1])
    liste = [1, 2, 3, 4, 5, 6]
    rapide_en_place(liste)
    assert(liste == [1, 2, 3, 4, 5, 6])
    liste = [0, 8, 9, 0, 17, 2, 8, 5]
    rapide_en_place(liste)
    assert(liste == [0, 0, 2, 5, 8, 8, 9, 17])

test_rapide_en_place()

# affiche_et_pente(rapide_en_place, liste_alea)

#######################
import doctest
doctest.testmod()