Compter les inversions avec le tri fusion

Exercice de TD · niveau 3 (difficile) · NSI (terminale), chapitre 6 — Diviser pour régner

Énoncé

Compter les inversions avec le tri fusion.

Une inversion est un couple d'indices $(i, j)$ avec $i < j$ et $t ab [i] > t ab [j]$ . Adapter le tri fusion pour compter le nombre total d'inversions en $O (n lo g n)$ .

Corrigé

lors de la fusion, lorsqu'un élément de la moitié droite est recopié avant des éléments restants de la moitié gauche, ceux-ci forment autant d'inversions.


def fusion_compte(a, b):
    res, inv = [], 0
    i, j = 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i += 1
        else:
            res.append(b[j]); j += 1
            inv += len(a) - i      # tous les a[i:] > b[j]
    res.extend(a[i:]); res.extend(b[j:])
    return res, inv

def compte_inversions(tab):
    if len(tab) <= 1:
        return tab, 0
    m = len(tab) // 2
    g, ig = compte_inversions(tab[:m])
    d, idr = compte_inversions(tab[m:])
    f, ifu = fusion_compte(g, d)
    return f, ig + idr + ifu

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.