Laboratoire visuel : diviser pour régner

Le tri fusion découpe en deux moitiés, puis fusionne les résultats triés. Le tri rapide commence par répartir les valeurs autour d’un pivot, puis trie les deux parts. Suivez les appels et les copies pour comprendre où chacun travaille.

Vitesse

Avant le premier appel

Les indices sous les cases commencent à 0. L’étiquette #i garde la position dans la liste initiale, pour suivre les valeurs égales.

Arbre des appels

Vue d’ensemble

Rouge : dans la pile · vert : terminé · gris : cas de base. L’arbre défile vers l’appel actif ; cochez « Vue d’ensemble » pour comparer sa forme. Chaque nœud affiche l’entrée, sa taille et, après le retour, son résultat. Activez un nœud pour revenir au début de son appel.

Comparer sur la même entrée

Bilan complet des deux exécutions, indépendamment de l’étape affichée.

Tri	Comparaisons	Copies	Appels	Pile max.

Compter par niveau — Tri fusion

Racine au niveau 0. « Tailles » additionne les longueurs des listes reçues ; « tailles > 1 » ne compte que les appels qui découpent. Les opérations sont celles du niveau, hors appels descendants. Le bilan porte sur l’arbre complet.

Niveau	Appels	Tailles	Tailles > 1	Comparaisons	Copies

Que comptent les compteurs ?

L’arbre et les compteurs d’appels suivent tri_fusion ou tri_rapide, appel initial compris. Les fonctions fusion et partition sont détaillées dans l’opération courante.

Une comparaison est un test entre valeurs : A[i] < B[j] ou e <= x. Une copie est le placement d’un élément dans une nouvelle liste : tranches, ajouts de la partition, écritures de la fusion, création de [x] et chaque concaténation +.

La liste reste du tri rapide copie ses éléments deux fois : dans les tranches, puis dans leur concaténation. Au retour, tri_rapide(A) + [x] est calculé avant l’appel sur B ; la dernière concaténation recopie aussi ce préfixe.

Les tests de boucle, affectations de variables et initialisations par None sont exclus. Ces comptes ne mesurent ni le temps réel ni toutes les opérations Python ; ils illustrent le travail de comparaison et de copie. Une trace sur une entrée ne prouve pas une borne asymptotique.

À explorer

Sur « Fusion du cours », suivez une fusion : pourquoi suffit-il de comparer les deux têtes ?
Sur « Déjà triée », comparez les sommes des tailles par niveau. Où passent les pivots du tri rapide ?
Sur « Tous égaux », le pivot est une médiane. Pourquoi les parts du tri rapide sont-elles pourtant déséquilibrées ?
Avec « Milieu ≠ médiane », quelle est la différence entre l’indice du milieu et une valeur médiane ?

Les algorithmes suivis

Le pivot est toujours l’élément d’indice len(L) // 2. Il est retiré avant la partition ; les autres éléments égaux au pivot vont à gauche. La fusion prélève dans B en cas d’égalité, comme dans le code du cours.

Fusion

def fusion(A, B):
    n = len(A)
    m = len(B)
    C = [None] * (n + m)
    i = 0
    j = 0
    for k in range(n + m):
        if i >= n:
            C[k] = B[j]
            j = j + 1
        elif j >= m:
            C[k] = A[i]
            i = i + 1
        elif A[i] < B[j]:
            C[k] = A[i]
            i = i + 1
        else:
            C[k] = B[j]
            j = j + 1
    return C

Tri fusion

from fusion import fusion


def tri_fusion(L):
    n = len(L)
    if n <= 1:
        return L
    m = n // 2
    L1 = L[:m]
    L2 = L[m:]
    L1 = tri_fusion(L1)
    L2 = tri_fusion(L2)
    return fusion(L1, L2)

Partition

def partition(L, x):
    A = []
    B = []
    for e in L:
        if e <= x:
            A.append(e)
        else:
            B.append(e)
    return A, B

Tri rapide

from partition import partition


def tri_rapide(L):
    n = len(L)
    if n <= 1:
        return L
    m = n // 2
    x = L[m]
    reste = L[:m] + L[m + 1:]
    A, B = partition(reste, x)
    return tri_rapide(A) + [x] + tri_rapide(B)