Spécialité NSI - Terminale (Corrigé)

1. Analyse théorique des complexités

* **Tri par sélection :** Sa complexité temporelle dans le pire, le meilleur et le cas moyen est en O(n²). Deux boucles imbriquées parcourent la structure de données, ce qui génère un nombre d'opérations proportionnel à n².

* **Tri fusion :** Basé sur le principe "diviser pour régner", sa complexité temporelle est en O(n log n) dans tous les cas.

2. Mise en œuvre Python (Tri fusion)

def fusion(gauche, droite):
    resultat = []
    i = 0
    j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] < droite[j]:
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    return resultat + gauche[i:] + droite[j:]

def tri_fusion(t):
    if len(t) <= 1:
        return t
    milieu = len(t) // 2
    gauche = tri_fusion(t[:milieu])
    droite = tri_fusion(t[milieu:])
    return fusion(gauche, droite)

3. Évaluation énergétique et impact EDD

Pour n = 10 000 éléments :

• Le tri quadratique effectue environ 10⁸ opérations élémentaires.
• Le tri fusion effectue environ 10⁴ × log₂(10 000) ≈ 132 877 opérations.

Le rapport d'efficacité est de l'ordre de plusieurs centaines de fois moins d'instructions processeur. Multiplié par un million de requêtes quotidiennes, le choix d'un algorithme inadapté maintient des cœurs de processeurs à pleine charge de manière superflue, induisant une surconsommation électrique directe et inutile des serveurs. L'écoconception logicielle démontre ici que l'optimisation du code est un levier écologique aussi pertinent que l'efficacité matérielle.