Les algorithmes de tri

Selection (on souligne la partie definitive) :

init : 5 2 8 1 9 3
i=0  : [1] 2 8 5 9 3        min = 1, echange avec 5
i=1  : [1 2] 8 5 9 3        2 est deja le min
i=2  : [1 2 3] 5 9 8        min = 3, echange avec 8
i=3  : [1 2 3 5] 9 8        5 est deja le min
i=4  : [1 2 3 5 8] 9        min = 8, echange avec 9
final: 1 2 3 5 8 9

Comparaisons : \(5+4+3+2+1 = 15 = \frac{6\cdot5}{2}\).

Insertion :

init : [5] 2 8 1 9 3
i=1  : [2 5] 8 1 9 3        insere 2
i=2  : [2 5 8] 1 9 3        insere 8, aucun decalage
i=3  : [1 2 5 8] 9 3        insere 1, trois decalages
i=4  : [1 2 5 8 9] 3        insere 9, aucun decalage
i=5  : [1 2 3 5 8 9]        insere 3, trois decalages
final: 1 2 3 5 8 9

Comparaisons : \(1 + 1 + 4 + 1 + 4 = 11\). Moins que la selection sur cette entree.

Bulles :

init    : 5 2 8 1 9 3
passe 1 : 2 5 1 8 3 [9]     9 est remonte
passe 2 : 2 1 5 3 [8 9]
passe 3 : 1 2 3 [5 8 9]
passe 4 : 1 2 [3 5 8 9]     aucun echange -> arret
final   : 1 2 3 5 8 9

Comparaisons : \(5+4+3+2 = 14\) (le drapeau evite le dernier passage).

Le nombre d'echanges du tri a bulles vaut exactement le nombre d'inversions de la liste initiale, ici 7.

import random

def tri_selection(t):
    n, nc, ne = len(t), 0, 0
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            nc += 1
            if t[j] < t[imin]:
                imin = j
        if imin != i:
            t[i], t[imin] = t[imin], t[i]; ne += 1
    return nc, ne

def tri_insertion(t):
    nc, ne = 0, 0
    for i in range(1, len(t)):
        x, j = t[i], i - 1
        while j >= 0 and t[j] > x:
            nc += 1
            t[j + 1] = t[j]; ne += 1
            j -= 1
        if j >= 0:
            nc += 1
        t[j + 1] = x
    return nc, ne

def tri_bulles(t):
    n, nc, ne = len(t), 0, 0
    for i in range(n - 1, 0, -1):
        echange = False
        for j in range(i):
            nc += 1
            if t[j] > t[j + 1]:
                t[j], t[j + 1] = t[j + 1], t[j]; ne += 1; echange = True
        if not echange:
            break
    return nc, ne

# validation
for _ in range(300):
    u = [random.randint(0, 50) for _ in range(random.randint(0, 20))]
    for tri in (tri_selection, tri_insertion, tri_bulles):
        v = u[:]; tri(v)
        assert v == sorted(u)

# comparaison
n = 200
jeux = {"aleatoire": [random.randint(0, 1000) for _ in range(n)],
        "triee":     list(range(n)),
        "inversee":  list(range(n, 0, -1))}

print(f"{'jeu':<12}{'tri':<12}{'comparaisons':>14}{'echanges':>12}")
for nom, base in jeux.items():
    for tri in (tri_selection, tri_insertion, tri_bulles):
        u = base[:]
        nc, ne = tri(u)
        print(f"{nom:<12}{tri.__name__:<12}{nc:>14}{ne:>12}")

jeu         tri           comparaisons    echanges
aleatoire   selection            19900         195
aleatoire   insertion             9877        9683
aleatoire   bulles               19701        9683
triee       selection            19900           0
triee       insertion              199           0
triee       bulles                 199           0
inversee    selection            19900         100
inversee    insertion            19900       19900
inversee    bulles               19900       19900

4. Conclusion.

• Selection : nombre de comparaisons constant \(\frac{n(n-1)}{2}\), mais tres peu d'echanges. A choisir si ecrire est beaucoup plus couteux que comparer (elements volumineux, memoire flash a ecriture limitee).
• Insertion : le meilleur des trois sur des donnees aleatoires (deux fois moins de comparaisons) et imbattable sur des donnees presque triees. C'est le tri quadratique a retenir.
• Bulles : jamais meilleur que l'insertion. Interet purement pedagogique.

Noter que le nombre d'echanges de l'insertion et des bulles est identique : c'est dans les deux cas le nombre d'inversions de la liste.

1. Invariant. Notons \(t^{(0)}\) la liste initiale. Au debut de l'iteration d'indice \(i\) de la boucle externe :

\(t[0..i-1]\) est triee par ordre croissant et contient exactement les elements \(t^{(0)}[0..i-1]\) (avec multiplicites), et \(t[i..n-1] = t^{(0)}[i..n-1]\).

2. Demonstration.

• Initialisation (\(i = 1\)) : \(t[0..0]\) est un singleton, donc trie, et rien n'a ete modifie. Vrai.
• Conservation : supposons l'invariant vrai au debut de l'iteration \(i\). Le corps sauvegarde \(x = t[i]\), puis decale vers la droite tous les elements de \(t[0..i-1]\) strictement superieurs a \(x\). Comme \(t[0..i-1]\) est triee, ces elements forment un suffixe \(t[j+1..i-1]\) de la partie triee. Apres decalage, la case \(j+1\) est libre et l'on y place \(x\). Or \(t[j] \le x\) (sinon la boucle aurait continue) et \(x < t[j+2]\) (ancien \(t[j+1]\)) : la liste \(t[0..i]\) est donc triee. De plus aucun element n'a ete perdu (seulement deplace) et \(x\) y figure : c'est bien l'ensemble \(t^{(0)}[0..i]\). L'invariant vaut au debut de l'iteration \(i+1\).
• Conclusion : a la sortie, \(i = n\). L'invariant donne : \(t[0..n-1]\) est triee et contient exactement les elements initiaux. C'est la specification du tri.

3. Terminaison de la boucle interne. Variant : \(v = j + 1\). C'est un entier naturel tant que la condition \(j \ge 0\) est vraie, et il decroit strictement de 1 a chaque tour (j -= 1). Il ne peut donc y avoir qu'un nombre fini de tours. La boucle externe, elle, est un for sur un range fini : elle termine trivialement.

4. Decalages et inversions. Une inversion est un couple \((k,l)\) avec \(k < l\) et \(t^{(0)}[k] > t^{(0)}[l]\). A l'iteration \(i\), chaque decalage deplace un element \(t[j]\) avec \(j < i\) et \(t[j] > x = t^{(0)}[i]\) : le couple \((j, i)\) est donc une inversion de la liste initiale, et chaque inversion \((k,i)\) est traitee exactement une fois (a l'iteration \(i\)). Le nombre total de decalages est donc exactement le nombre \(k\) d'inversions.

Consequence : la complexite du tri par insertion est \(\Theta(n + k)\). Comme \(0 \le k \le \binom n2\), on retrouve \(\Theta(n)\) au meilleur cas et \(\Theta(n^2)\) au pire. Sur une liste dont chaque element est a distance \(\le d\) de sa position finale, \(k \le nd\) et le tri est en \(\Theta(nd)\) : quasi lineaire pour \(d\) petit.

def inversions(t):
    """Nombre de paires (i, j) avec i < j et t[i] > t[j]."""
    return sum(1 for i in range(len(t)) for j in range(i+1, len(t)) if t[i] > t[j])

def tri_insertion(t):
    """Trie t en place ; renvoie (comparaisons, decalages)."""
    nc, ne = 0, 0
    for i in range(1, len(t)):
        x, j = t[i], i - 1
        while j >= 0 and t[j] > x:
            nc += 1
            t[j+1] = t[j]; ne += 1
            j -= 1
        if j >= 0:
            nc += 1
        t[j+1] = x
    return nc, ne

import random
for _ in range(200):
    u = [random.randint(0, 20) for _ in range(random.randint(0, 15))]
    k = inversions(u)
    v = u[:]
    _, decalages = tri_insertion(v)
    assert decalages == k

import random, time

def fusion(g, d):
    """Fusionne deux listes triees. Theta(n + m). STABLE grace au <=."""
    res, i, j = [], 0, 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            res.append(g[i]); i += 1
        else:
            res.append(d[j]); j += 1
    res.extend(g[i:]); res.extend(d[j:])
    return res

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

def tri_fusion_iteratif(t):
    """Fusion ascendante : blocs de taille 1, 2, 4, ... Theta(n log n)."""
    u = t[:]
    n, largeur = len(u), 1
    while largeur < n:
        v = []
        for debut in range(0, n, 2 * largeur):
            g = u[debut:debut + largeur]
            d = u[debut + largeur:debut + 2 * largeur]
            v.extend(fusion(g, d))
        u = v
        largeur *= 2
    return u

for _ in range(300):
    v = [random.randint(0, 50) for _ in range(random.randint(0, 30))]
    assert tri_fusion(v) == sorted(v)
    assert tri_fusion_iteratif(v) == sorted(v)

2. Correction de fusion. Invariant : au debut de chaque tour, res est triee, contient exactement \(g[0..i-1]\) et \(d[0..j-1]\), et tous ses elements sont \(\le\) tous ceux de \(g[i..]\) et \(d[j..]\).

• Initialisation : res vide, \(i=j=0\). Vrai.
• Conservation : on ajoute \(\min(g_i, d_j)\), qui est superieur ou egal a tout element de res (par l'invariant) et inferieur ou egal a tous les elements restants (car \(g\) et \(d\) sont triees). L'invariant est preserve.
• Conclusion : a la sortie, l'une des deux listes est epuisee ; les extend ajoutent le reste de l'autre, qui est trie et superieur a tout ce qui precede.

Stabilite : en cas d'egalite \(g_i = d_j\), le test g[i] <= d[j] prend l'element de \(g\), c'est-a-dire celui de gauche, donc le plus a gauche dans la liste initiale. Remplacer <= par < detruirait la stabilite.

def tri_insertion(t):
    for i in range(1, len(t)):
        x, j = t[i], i - 1
        while j >= 0 and t[j] > x:
            t[j+1] = t[j]; j -= 1
        t[j+1] = x
    return t

print(f"{'n':>7}{'insertion (s)':>16}{'fusion (s)':>14}")
for n in (10, 100, 1000, 10000):
    base = [random.random() for _ in range(n)]
    a = base[:]; t0 = time.perf_counter(); tri_insertion(a); t1 = time.perf_counter()
    b = base[:]; t2 = time.perf_counter(); tri_fusion(b);    t3 = time.perf_counter()
    print(f"{n:>7}{t1-t0:>16.5f}{t3-t2:>14.5f}")

      n   insertion (s)    fusion (s)
     10         0.00001       0.00002
    100         0.00048       0.00021
   1000         0.04600       0.00270
  10000         4.71000       0.03300

4. Le croisement se situe vers \(n \approx 40\text{-}80\) : en dessous, la constante de l'insertion (tres faible, pas d'allocation) l'emporte sur l'avantage asymptotique du tri fusion. A \(n = 10^4\), le rapport est deja de 140. C'est exactement pourquoi les implementations reelles (Timsort, introsort) basculent sur un tri par insertion pour les petites sous-listes.

import random

def inversions_naif(t):
    """Theta(n^2)."""
    return sum(1 for i in range(len(t)) for j in range(i+1, len(t)) if t[i] > t[j])

def fusion_compte(g, d):
    """Fusionne et compte les inversions entre les deux moities."""
    res, i, j, inv = [], 0, 0, 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            res.append(g[i]); i += 1
        else:
            # d[j] passe devant TOUS les elements restants de g : g[i..] sont
            # tous strictement superieurs a d[j], d'ou len(g) - i inversions.
            res.append(d[j]); j += 1
            inv += len(g) - i
    res.extend(g[i:]); res.extend(d[j:])
    return res, inv

def compte_inversions(t):
    """Renvoie (liste triee, nombre d'inversions). Theta(n log n)."""
    if len(t) <= 1:
        return t[:], 0
    m = len(t) // 2
    g, ig = compte_inversions(t[:m])
    d, id_ = compte_inversions(t[m:])
    f, im = fusion_compte(g, d)
    return f, ig + id_ + im

for _ in range(400):
    u = [random.randint(0, 30) for _ in range(random.randint(0, 25))]
    trie, inv = compte_inversions(u)
    assert trie == sorted(u)
    assert inv == inversions_naif(u)
print("comptage d'inversions valide")

print(compte_inversions([1, 2, 3, 4])[1])        # 0  : deja triee
print(compte_inversions([4, 3, 2, 1])[1])        # 6  : maximum = C(4,2)

2-3. Justification. Toute inversion \((k,l)\) de la liste est de l'un des trois types :

• \(k, l\) tous deux dans la moitie gauche : comptee par l'appel recursif gauche ;
• tous deux a droite : comptee par l'appel recursif droit ;
• \(k\) a gauche et \(l\) a droite : comptee lors de la fusion.

Ces trois familles sont disjointes et recouvrent toutes les inversions : la somme est donc exacte.

Pour le troisieme cas : lorsqu'on prend \(d_j\) alors qu'il reste \(g_i, \dots, g_{|g|-1}\), on a \(d_j < g_i \le g_{i+1} \le \cdots\) (car \(g\) est triee). Ainsi \(d_j\) forme une inversion avec chacun de ces \(|g| - i\) elements, et avec aucun de ceux deja sortis (qui lui etaient inferieurs ou egaux). L'incrementation de \(|g|-i\) est donc exacte, et chaque paire gauche-droite est comptee une seule fois puisqu'un element de droite n'est traite qu'une fois.

4. Le nombre d'inversions entre deux classements est la distance de Kendall-tau : c'est le nombre minimal de transpositions d'elements adjacents pour passer de l'un a l'autre. Normalisee par \(\binom n2\), elle donne un coefficient de correlation de rang entre \(-1\) et \(1\).

def kendall_tau(a, b):
    """Coefficient de correlation de rang entre deux classements des memes elements."""
    rang = {x: i for i, x in enumerate(b)}
    permutation = [rang[x] for x in a]
    _, inv = compte_inversions(permutation)
    n = len(a)
    return 1 - 4 * inv / (n * (n - 1))

assert abs(kendall_tau([1,2,3,4], [1,2,3,4]) - 1.0) < 1e-12
assert abs(kendall_tau([1,2,3,4], [4,3,2,1]) + 1.0) < 1e-12

1. Trier puis lire t[k] coute \(\Theta(n\log n)\). On peut faire mieux : le probleme est plus simple que le tri complet.

import random

def partition(t, g, d):
    """Partitionne t[g..d] autour d'un pivot aleatoire (schema de Lomuto).

    A la fin, t[g..p-1] <= t[p] < t[p+1..d]. Renvoie p. Theta(d - g).
    """
    r = random.randint(g, d)
    t[r], t[d] = t[d], t[r]           # le pivot est place en derniere position
    pivot = t[d]
    i = g                              # frontiere des elements <= pivot
    for j in range(g, d):
        if t[j] <= pivot:
            t[i], t[j] = t[j], t[i]
            i += 1
    t[i], t[d] = t[d], t[i]            # le pivot rejoint sa place definitive
    return i

def selection(t, k):
    """k-ieme plus petit element (k a partir de 0). Modifie t. Theta(n) en moyenne."""
    u = t[:]
    g, d = 0, len(u) - 1
    while True:
        if g == d:
            return u[g]
        p = partition(u, g, d)
        if k == p:
            return u[p]
        if k < p:
            d = p - 1                  # on ne garde QU'UN cote
        else:
            g = p + 1

def mediane(t):
    return selection(t, len(t) // 2)

for _ in range(400):
    v = [random.randint(0, 60) for _ in range(random.randint(1, 40))]
    k = random.randrange(len(v))
    assert selection(v, k) == sorted(v)[k]
print("quickselect valide")

3. Complexite. Contrairement au tri rapide, on ne recurse que d'un cote. Si le pivot est choisi uniformement au hasard, la taille du sous-probleme est en moyenne \(3n/4\) au plus, d'ou l'esperance \[ T(n) \le T\!\left(\tfrac{3n}{4}\right) + \Theta(n) \;\Longrightarrow\; T(n) = \Theta\!\left(n \sum_{i\ge0} (3/4)^i\right) = \Theta(n). \] La serie geometrique converge : le cout total est lineaire en moyenne, et non \(n\log n\).

Au pire (pivot toujours extremal), on obtient \(n + (n-1) + \cdots = \Theta(n^2)\), mais avec un pivot aleatoire la probabilite en est negligeable. L'algorithme mediane des medianes garantit \(\Theta(n)\) meme au pire, au prix d'une constante bien plus grande.

import random

def tri_peu_de_valeurs(t):
    """Theta(n + k log k) ou k est le nombre de valeurs distinctes."""
    compte = {}
    for x in t:                              # Theta(n)
        compte[x] = compte.get(x, 0) + 1
    res = []
    for v in sorted(compte):                 # Theta(k log k)
        res.extend([v] * compte[v])          # Theta(n) au total
    return res

def tri_binaire(t):
    """Trie en place une liste de 0 et 1. Un seul parcours, Theta(n), Theta(1)."""
    g, d = 0, len(t) - 1
    while g < d:
        if t[g] == 0:
            g += 1
        elif t[d] == 1:
            d -= 1
        else:
            t[g], t[d] = t[d], t[g]
            g += 1; d -= 1

def drapeau_hollandais(t):
    """Trie en place une liste de 0, 1, 2. Un seul parcours (Dijkstra)."""
    bas, i, haut = 0, 0, len(t) - 1
    while i <= haut:
        if t[i] == 0:
            t[bas], t[i] = t[i], t[bas]
            bas += 1; i += 1
        elif t[i] == 2:
            t[haut], t[i] = t[i], t[haut]
            haut -= 1                        # i n'avance PAS : t[i] est inconnu
        else:
            i += 1

for _ in range(500):
    u = [random.randint(0, 2) for _ in range(random.randint(0, 25))]
    v = u[:]; drapeau_hollandais(v)
    assert v == sorted(u)
    b = [random.randint(0, 1) for _ in range(random.randint(0, 25))]
    c = b[:]; tri_binaire(c)
    assert c == sorted(b)
print("drapeau hollandais valide")

4. Invariant du drapeau hollandais. La liste est decoupee en quatre zones :

\[ \underbrace{t[0..\text{bas}-1]}_{= 0}\; \underbrace{t[\text{bas}..i-1]}_{= 1}\; \underbrace{t[i..\text{haut}]}_{\text{inconnu}}\; \underbrace{t[\text{haut}+1..n-1]}_{= 2} \]

• Initialisation : \(\text{bas} = i = 0\) et \(\text{haut} = n-1\) : les trois zones connues sont vides, la zone inconnue est toute la liste. Vrai.
• Conservation, selon la valeur de \(t[i]\) :
  • \(t[i] = 0\) : on l'echange avec \(t[\text{bas}]\), qui vaut 1 (ou est \(t[i]\) lui-meme si \(\text{bas} = i\)). La zone des 0 s'agrandit d'un cran, celle des 1 se decale ; on incremente les deux indices. Invariant preserve.
  • \(t[i] = 1\) : il est deja a sa place, en fin de zone des 1. On incremente \(i\).
  • \(t[i] = 2\) : on l'echange avec \(t[\text{haut}]\), qui rejoint la zone des 2 ; on decremente \(\text{haut}\). On n'incremente pas \(i\) : l'element recu de \(t[\text{haut}]\) n'a jamais ete examine, il reste dans la zone inconnue.
• Terminaison : le variant \(\text{haut} - i + 1\) (taille de la zone inconnue) est un entier positif qui decroit strictement a chaque tour, dans les trois cas. La boucle s'arrete.
• Conclusion : a la sortie, \(i > \text{haut}\), la zone inconnue est vide, et l'invariant donne exactement la liste triee.

Complexite : \(\Theta(n)\) en temps (le variant decroit de 1 par tour) et \(\Theta(1)\) en memoire. Un seul parcours suffit, la ou un tri par denombrement en demanderait deux.

1. Un tas-max est un arbre binaire presque complet (tous les niveaux pleins sauf le dernier, rempli de gauche a droite) verifiant la propriete de tas : tout noeud est superieur ou egal a ses fils. La racine contient donc le maximum.

Il se represente sans pointeurs, dans un tableau, en numerotant les noeuds par niveaux :

\[ \text{fils gauche}(i) = 2i+1, \qquad \text{fils droit}(i) = 2i+2, \qquad \text{parent}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor. \]

Les feuilles sont les indices \(i \ge \lfloor n/2 \rfloor\). La hauteur est \(\lfloor \log_2 n\rfloor\).

import random

def tamise(t, i, n):
    """Retablit la propriete de tas en descendant t[i]. Theta(log n)."""
    while True:
        g, d, plus_grand = 2*i + 1, 2*i + 2, i
        if g < n and t[g] > t[plus_grand]:
            plus_grand = g
        if d < n and t[d] > t[plus_grand]:
            plus_grand = d
        if plus_grand == i:
            return                          # propriete retablie
        t[i], t[plus_grand] = t[plus_grand], t[i]
        i = plus_grand                      # on continue de descendre

def construit_tas(t):
    """Transforme t en tas-max. Theta(n) — voir la preuve."""
    n = len(t)
    for i in range(n // 2 - 1, -1, -1):     # des derniers noeuds internes vers la racine
        tamise(t, i, n)

def tri_par_tas(t):
    """Trie t en place. Theta(n log n) dans TOUS les cas, Theta(1) memoire."""
    n = len(t)
    construit_tas(t)
    for fin in range(n - 1, 0, -1):
        t[0], t[fin] = t[fin], t[0]         # le max rejoint sa place definitive
        tamise(t, 0, fin)                   # on retablit le tas sur t[0..fin-1]

for _ in range(400):
    u = [random.randint(-50, 50) for _ in range(random.randint(0, 40))]
    v = u[:]; tri_par_tas(v)
    assert v == sorted(u)
print("tri par tas valide")

2. tamise descend d'au moins un niveau par tour, donc effectue au plus \(\lfloor\log_2 n\rfloor\) tours, chacun en \(\Theta(1)\) : \(\Theta(\log n)\).

3. La construction est lineaire. L'analyse naive donne \(\frac n2 \times \Theta(\log n) = \Theta(n\log n)\), mais elle est trop grossiere : la plupart des noeuds sont pres des feuilles et coutent peu. Precisement, un tas de \(n\) noeuds a au plus \(\lceil n/2^{h+1}\rceil\) noeuds de hauteur \(h\), et un tamisage a la hauteur \(h\) coute \(O(h)\). D'ou

\[ T(n) \;=\; \sum_{h=0}^{\lfloor\log_2 n\rfloor} \left\lceil\frac{n}{2^{h+1}}\right\rceil O(h) \;=\; O\!\left(n \sum_{h=0}^{\infty} \frac{h}{2^{h}}\right). \]

Or \(\displaystyle\sum_{h\ge0} \frac{h}{2^h} = \frac{1/2}{(1-1/2)^2} = 2\) (serie geometrique derivee, convergente). Donc \(T(n) = O(n)\) : la construction du tas est lineaire.

4. La seconde phase effectue \(n-1\) tamisages en \(\Theta(\log n)\), soit \(\Theta(n\log n)\). Total : \(\Theta(n) + \Theta(n\log n) = \Theta(n\log n)\), garanti dans tous les cas — contrairement au tri rapide — et en place — contrairement au tri fusion. C'est le seul tri du programme a cumuler ces deux proprietes.

Il n'est pas stable : les echanges a distance (racine avec la derniere case) detruisent l'ordre relatif. Contre-exemple :

t = [(1, "a"), (1, "b"), (0, "c")]
# apres tri par tas sur la premiere composante, l'ordre de "a" et "b" peut etre inverse

En pratique, Python utilise Timsort (fusion adaptative, stable) et C++ std::sort utilise introsort (tri rapide qui bascule sur le tri par tas si la profondeur de recursion depasse \(2\log_2 n\), garantissant ainsi \(\Theta(n\log n)\) au pire).