Diviser pour régner et tri fusion : exercices corrigés de Terminale

Diviser : [5, 2, 9, 1] donne [5, 2] et [9, 1].

Les moitiés sont à leur tour divisées : [5], [2], [9], [1]. Ces tableaux d'un seul élément sont triés, c'est le cas de base.

Régner : on trie chaque moitié en appelant le tri fusion sur elle, ce qui revient ici à descendre jusqu'aux tableaux d'un élément.

Combiner : on fusionne [5] et [2] en [2, 5], puis [9] et [1] en [1, 9].

Dernière combinaison : on fusionne [2, 5] et [1, 9] en [1, 2, 5, 9].

Compare 1 et 2 : on prend 1. Résultat : [1]. Comparaison n°1.

Compare 4 et 2 : on prend 2. Résultat : [1, 2]. Comparaison n°2.

Compare 4 et 3 : on prend 3. Résultat : [1, 2, 3]. Comparaison n°3.

Compare 4 et 9 : on prend 4. Comparaison n°4. Compare 7 et 9 : on prend 7. Comparaison n°5. Résultat : [1, 2, 3, 4, 7].

La liste A est épuisée. On recopie le reste de B, c'est-à-dire 9, sans comparaison. Résultat : [1, 2, 3, 4, 7, 9].

On compte 5 comparaisons, soit $3+3-1$.

Les tailles successives sont 16, 8, 4, 2, 1.

Entre 16 et 1, il y a quatre divisions par 2 : $16\to8\to4\to2\to1$.

On a donc $2^4=16$, ce qui s'écrit $\log_2 16=4$.

Il y a 4 niveaux de découpage pour 16 éléments.

Première division : [38, 27, 43] et [3, 9, 82, 10].

Côté gauche : [38, 27, 43] donne [38] et [27, 43] ; puis [27, 43] donne [27] et [43].

Côté droit : [3, 9, 82, 10] donne [3, 9] et [82, 10] ; puis [3, 9] donne [3] et [9], et [82, 10] donne [82] et [10].

Fusions à gauche : [27] et [43] donnent [27, 43] ; puis [38] et [27, 43] donnent [27, 38, 43].

Fusions à droite : [3] et [9] donnent [3, 9] ; [82] et [10] donnent [10, 82] ; puis [3, 9] et [10, 82] donnent [3, 9, 10, 82].

Fusion finale : [27, 38, 43] et [3, 9, 10, 82] donnent [3, 9, 10, 27, 38, 43, 82].

On compte 2 fusions à gauche, 3 à droite et 1 finale : 6 fusions en tout.

La boucle continue tant que les deux listes ont encore des éléments : while i < len(g) and j < len(d):.

Dans le else, c'est l'élément de d qui est le plus petit : res.append(d[j]).

À la sortie de la boucle, au moins une des deux listes est épuisée. Le reste de l'autre est déjà trié et se recopie à la fin : return res + g[i:] + d[j:]. Une des deux tranches est vide.

Le tri récursif : si len(t) <= 1, on renvoie t (cas de base). Sinon milieu = len(t) // 2, puis return fusion(tri_fusion(t[:milieu]), tri_fusion(t[milieu:])).

Avec <=, quand deux valeurs sont égales, on prend d'abord celle de la liste de gauche. Les éléments égaux gardent alors leur ordre d'origine : le tri est dit stable. Avec <, le résultat resterait trié, mais l'ordre relatif des égaux pourrait changer.

Comme $1024=2^{10}$, il y a $\log_2 1024=10$ niveaux de découpage.

À chaque niveau, les fusions rangent en tout 1024 éléments : un niveau coûte de l'ordre de $n=1024$ placements.

Total estimé : $10\times1024=10\,240$ placements.

Pour la méthode naïve : $n^2=1024^2=1\,048\,576$.

Rapport : $1\,048\,576/10\,240\approx102$. La méthode naïve fait de l'ordre de cent fois plus d'opérations.

Le terme $2T(n/2)$ est le coût des deux appels récursifs sur des moitiés de taille $n/2$ (régner). Le terme $n$ est le coût de la fusion, qui place $n$ éléments (combiner).

$T(2)=2T(1)+2=2$.

$T(4)=2T(2)+4=8$ ; $T(8)=2T(4)+8=24$.

$T(16)=2T(8)+16=64$ ; $T(32)=2T(16)+32=160$.

On observe : $T(2)=2\times1$, $T(4)=4\times2$, $T(8)=8\times3$, $T(16)=16\times4$, $T(32)=32\times5$. Conjecture : $T(2^k)=k\cdot2^k$.

Initialisation : pour $k=0$, $T(1)=0=0\times2^0$.

Hérédité : on suppose $T(2^k)=k\cdot2^k$. Alors $T(2^{k+1})=2T(2^k)+2^{k+1}=2k\cdot2^k+2^{k+1}=(k+1)\cdot2^{k+1}$. La propriété passe au rang $k+1$.

Conclusion : pour tout entier $k\geq0$, $T(2^k)=k\cdot2^k$, soit $T(n)=n\log_2 n$.

$252=2\times105+42$, donc $\text{pgcd}(252,105)=\text{pgcd}(105,42)$.

$105=2\times42+21$, donc $\text{pgcd}(105,42)=\text{pgcd}(42,21)$.

$42=2\times21+0$, donc $\text{pgcd}(42,21)=\text{pgcd}(21,0)=21$.

Fonction : def pgcd(a, b): puis if b == 0: return a puis return pgcd(b, a % b).

Comparaison : à chaque étape il n'y a qu'un seul sous-problème, et non deux comme dans le tri fusion. Il n'y a pas de combinaison : la réponse du sous-problème est renvoyée telle quelle.

Algorithme : si le tableau a un élément, on le renvoie. Sinon on coupe en deux, on calcule le maximum de chaque moitié par un appel récursif, et on renvoie le plus grand des deux.

Division : [7, 3, 12, 5] et [9, 1, 8, 4], puis [7, 3], [12, 5], [9, 1], [8, 4].

Combinaisons de niveau le plus bas : max(7, 3) = 7 ; max(12, 5) = 12 ; max(9, 1) = 9 ; max(8, 4) = 8. Soit 4 comparaisons.

Niveau suivant : max(7, 12) = 12 ; max(9, 8) = 9. Soit 2 comparaisons.

Dernière combinaison : max(12, 9) = 12. Soit 1 comparaison.

Total : $4+2+1=7$ comparaisons, c'est-à-dire $8-1$.