# Projet 08 — La Course des Algorithmes
# Comparer les performances du tri par insertion et du tri par sélection

import random
import time

# -------------------------------------------------------
# Étape 1 : recopie ici tes deux fonctions de tri
# -------------------------------------------------------

def tri_insertion(tab):
    # TODO : recopier depuis le cours
    pass

def tri_selection(tab):
    # TODO : recopier depuis le cours
    pass

# -------------------------------------------------------
# Outils de mesure (déjà fournis)
# -------------------------------------------------------

def mesurer_temps(fonction, tab):
    """
    Mesure le temps d'exécution de fonction(tab) en millisecondes.
    Travaille sur une copie pour ne pas modifier l'original.
    """
    copie = tab[:]
    debut = time.time()
    fonction(copie)
    fin = time.time()
    return round((fin - debut) * 1000, 3)  # résultat en ms

def generer_liste(n, mode="aleatoire"):
    """
    Génère une liste de n entiers selon le mode :
    - "aleatoire" : ordre aléatoire
    - "trie"      : déjà triée (croissant)
    - "inverse"   : triée à l'envers (décroissant)
    """
    if mode == "aleatoire":
        return random.sample(range(n * 10), n)
    elif mode == "trie":
        return list(range(n))
    elif mode == "inverse":
        return list(range(n, 0, -1))

# -------------------------------------------------------
# Étape 3 : tableau comparatif selon la taille
# -------------------------------------------------------

def comparer_tailles():
    tailles = [100, 500, 1000, 2000, 5000]
    print("=== Comparaison par taille (liste aléatoire) ===\n")
    print(f"  {'n':>6}  {'Insertion (ms)':>16}  {'Sélection (ms)':>16}  {'Vainqueur':>10}")
    print("  " + "-" * 55)

    for n in tailles:
        liste = generer_liste(n, "aleatoire")
        t_insertion  = mesurer_temps(tri_insertion, liste)
        t_selection  = mesurer_temps(tri_selection, liste)
        vainqueur = "Insertion" if t_insertion < t_selection else "Sélection"
        print(f"  {n:>6}  {t_insertion:>16.3f}  {t_selection:>16.3f}  {vainqueur:>10}")
    print()

# -------------------------------------------------------
# Étape 4 : tableau comparatif selon le mode (n fixé)
# -------------------------------------------------------

def comparer_modes(n=1000):
    modes = ["aleatoire", "trie", "inverse"]
    print(f"=== Comparaison par configuration (n = {n}) ===\n")
    print(f"  {'Mode':<12}  {'Insertion (ms)':>16}  {'Sélection (ms)':>16}  {'Vainqueur':>10}")
    print("  " + "-" * 60)

    for mode in modes:
        liste = generer_liste(n, mode)
        t_insertion = mesurer_temps(tri_insertion, liste)
        t_selection = mesurer_temps(tri_selection, liste)
        vainqueur = "Insertion" if t_insertion < t_selection else "Sélection"
        print(f"  {mode:<12}  {t_insertion:>16.3f}  {t_selection:>16.3f}  {vainqueur:>10}")
    print()

# -------------------------------------------------------
# Programme principal
# -------------------------------------------------------

comparer_tailles()
comparer_modes(n=1000)

print("Conclusion :")
print("  TODO : écris tes observations ici")