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.

Laboratoire visuel : diviser pour régner

Algorithme

Changer de tri conserve la liste appliquée et reprend au début.

Au plus 15 entiers entre −999 et 999. Écrivez [] pour la liste vide.

Essayer :

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

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.

À cette étape

Comparaisons de valeurs0
Copies de valeurs0
Appels lancés0
Pile actuelle / max.0 / 0

Résultat final

—

Pile d’appels

    Comparer sur la même entrée

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

    Bilans complets des tris
    TriComparaisonsCopiesAppelsPile 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.

    NiveauAppelsTaillesTailles > 1ComparaisonsCopies
    Que comptent les compteurs ?

    L’arbre et les compteurs d’appels suivent tri_fusion outri_rapide, appel initial compris. Les fonctionsfusionet 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 parNonesont 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

    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)