Terminale NSI · Algorithmique

Les tris, la complexité et la dichotomie

Comprendre, comparer, observer et s'entraîner.

← Retour à la rubrique NSI · Animations · QCM /20

Pourquoi trier ?

Trier facilite la lecture, la comparaison, les regroupements et certaines recherches. Une recherche dichotomique devient possible sur une liste triée. Mais trier a un coût : pour une recherche unique, un parcours linéaire peut être préférable à trier d'abord.

L'ordre de départ compte : une liste déjà triée ou presque triée favorise l'insertion ; une liste inversée le pénalise. Sélection effectue toujours O(n²) comparaisons. Fusion garantit O(n log n). Quicksort avec premier élément comme pivot peut dégénérer en O(n²) sur une liste déjà triée.

Complexité : O(1) constant, O(log n) logarithmique, O(n) linéaire, O(n log n) quasi linéaire, O(n²) quadratique. Il s'agit d'ordres de grandeur asymptotiques, pas de durées exactes.

Tableau comparatif

TriMeilleurMoyenPireStable
InsertionO(n)O(n²)O(n²)Oui
SélectionO(n²)O(n²)O(n²)Non
Bulles optimiséO(n)O(n²)O(n²)Oui
FusionO(n log n)O(n log n)O(n log n)Oui
Rapide (pivot initial)O(n log n)O(n log n)O(n²)Non, en général

Stable : conserve l'ordre relatif d'éléments ayant la même clé. En place : n'utilise qu'une petite mémoire auxiliaire. Les complexités mémoire dépendent de l'implémentation.

Insertion

Stable, en place, excellent sur une liste presque triée.

Meilleur : O(n) · Pire : O(n²) · Mémoire : O(1)
def tri_insertion(t):
    for i in range(1, len(t)):
        x = t[i]
        j = i - 1
        while j >= 0 and t[j] > x:
            t[j + 1] = t[j]
            j -= 1
        t[j + 1] = x
    return t

Sélection

Peu d'échanges, mais toujours beaucoup de comparaisons.

Meilleur : O(n²) · Pire : O(n²) · Mémoire : O(1)
def tri_selection(t):
    for i in range(len(t)):
        m = i
        for j in range(i + 1, len(t)):
            if t[j] < t[m]:
                m = j
        t[i], t[m] = t[m], t[i]
    return t

Bulles

Simple et stable, mais peu efficace sur de grandes listes.

Meilleur : O(n) · Pire : O(n²) · Mémoire : O(1)
def tri_bulles(t):
    for fin in range(len(t)-1, 0, -1):
        echange = False
        for j in range(fin):
            if t[j] > t[j+1]:
                t[j], t[j+1] = t[j+1], t[j]
                echange = True
        if not echange:
            break
    return t

Fusion

Stable, performance garantie ; nécessite de la mémoire supplémentaire.

Meilleur : O(n log n) · Pire : O(n log n) · Mémoire : O(n)
def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    a = tri_fusion(t[:m])
    b = tri_fusion(t[m:])
    r = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            r.append(a[i]); i += 1
        else:
            r.append(b[j]); j += 1
    return r + a[i:] + b[j:]

Rapide (quicksort)

Rapide en moyenne ; ici, premier élément comme pivot et listes auxiliaires. *Mémoire totale de cette version Python.

Meilleur : O(n log n) · Pire : O(n²) · Mémoire : O(n) à O(n²)*
def tri_rapide(t):
    if len(t) <= 1:
        return t
    pivot = t[0]
    petits = [x for x in t[1:] if x < pivot]
    grands = [x for x in t[1:] if x >= pivot]
    return tri_rapide(petits) + [pivot] + tri_rapide(grands)

Recherche dichotomique : pas un tri

On compare l'élément recherché au milieu d'une liste déjà triée, puis on élimine la moitié inutile. Temps O(log n), mémoire O(1) pour cette version itérative.

def dichotomie(t, cible):
    gauche, droite = 0, len(t) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if t[milieu] == cible:
            return milieu
        if t[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Supprimer un élément d'une liste Python par indice coûte généralement O(n), car les éléments suivants sont décalés ; supprimer le dernier élément est amorti O(1).

Laboratoire : les cinq tris sur la même liste

Observe les étapes en parallèle. Chaque animation démarre avec exactement les mêmes dix nombres. Les étapes représentent des comparaisons et échanges simplifiés, pas des millisecondes réelles.

Compteur : nombre d'étapes enregistrées par la simulation, pas un benchmark de vitesse. La visualisation montre les déplacements et la progression de chaque méthode.

QCM de révision — 20 questions /20

Une seule bonne réponse par question. Valide pour obtenir la note et la correction détaillée.