Aller au contenu

Diviser/régner

Diviser pour régner


I. Présentation⚓︎

Vidéo Lumni

Diviser

👉 Découper un problème initial en sous problèmes.

Régner

👉 Résoudre les sous-problèmes (récursivement ou directement s'ils sont assez petits)

Combiner

👉 Trouver une solution au problème initial à partir des solutions des sous-problèmes.

II. Premiers exemples :⚓︎

Quelques exemples d'utilisation de "diviser pour régner" :

La correction est arrivée 😊

III. Une approche de la complexité⚓︎

Vidéo de Cédric Gerland

https://youtube.com/watch?v=UcT_4cWfnAs&si=EnSIkaIECMiOmarE

IV. Le tri fusion⚓︎

🤔 Comment fusionner deux listes triées pour obtenir une liste triée ?⚓︎

Nous donnons l1 = [2, 3, 5, 8] et l2 = [1, 4]

✏️ A vos crayons 1 :⚓︎

Voici un script Python :

Python
def mystere(l1, l2):
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    return lst

mystere([2, 3, 5, 8], [1, 4])

Recopier sur votre cahier le tableau suivant qui décrit le déroulement de l'exécution de :
mystere([2, 3, 5, 8],[1, 4]) et le compléter.

  • Il y a une ligne par tour de boucle.
  • Pour vous aider, nous avons rajouté une colonne pour l1 et une pour l2. Vous pourrez entourer à chaque étape, dans une de ces colonnes, l'élément qui sera ajouté à lst (en gras ici)
i1 i2 l1 l2 lst
0 0 [2, 3, 5, 8] [1, 4] [1]
0 1 [2, 3, 5, 8] [1, 4] [1, 2]
... ... ... ... ...
...
Solution
i1 i2 l1 l2 lst
0 0 [2, 3, 5, 8] [1, 4] [1]
0 1 [2, 3, 5, 8] [1, 4] [1, 2]
1 1 [2, 3, 5, 8] [1, 4] [1, 2, 3]
2 1 [2, 3, 5, 8] [1, 4] [1, 2, 3, 4]
2 2

😥 Nous observons que les deux listes n'ont pas été complètement fusionnées, car nous avons "épuisé" tous les éléments de l2.
👉 Par contre, il est certain que les éléments restants de l1 qui n'ont pas été fusionnés, sont triés, et plus grands que tous les éléments déjà présents dans lst.
🤗 Pour obtenir la liste complètement fusionnée, il suffit donc d'exécuter :
lst + [5, 8] c'est à dire lst + l1[i1:]

💻 A vous de jouer 1

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kEg[: r);Sé/q(.lo4y,6b=ac1x5+ud3t2à8_Pw7evp-fh09mn]is050F0P0H0y0!0q0#0g0z0q0y0#0#0x010H0!0R010406050#0E0X0X0y0h0t040k0r0q0E0_0r0Y050m101214160~0R04051m1f1p0m1m0~0F0!0Q0.0:0=0@0:0Y0d0E0y0d0P0S0R0t0H0U1d0g0U0!0d0U0q1R0U0H0|050)0w0q0P1y0;0?011Q1S1U1S0H1!1$1Y0H0h1n1M0.190#0R0y0Y0@0I011(1A010T0+0P0Y0y0X0P1Y1}1 241*271$2a2c0|0a0g0M0h0r0R0r0#0!1c0Y0g0%1{0h0h0P0z2x1f2f0Y1n0m1M2K1@1_1^1Z0F2h1B0!0Y292u1Y1v1x0/1)2U2W0Y0r2!1Y0R2D1n2I2K2;0 1~2y2$252*0h130q1Y0y1P2D0T0@030L0L0z2+0P1U2)0r0S0A3f0|0g0A1f0y2=2^0}2@2g2`1*2|2~30320P340136383a3c2X3f0S22040g0I3l3n1 3p2I2T013u0y2 1n310U333537390%3E2*3G0G3i0G3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0s3i0s3.1g3:3q2_1z3t0r2}3U3w3Y3y3!3C3%403)3g0C3i0C462;3;2^3R3^4g3|3B3$3b4m3e3g0v3i0v4s483=4b3@4d3v3W3x3z4A3 3d3G0O3i0O4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0K3i0K4!2J4$4a2%4)4e3_3{4i3}4k4C4;0S0W3i0W4_3P4v3?4~4P3`4R4j4B3(4E3f0V0|0A0V5b4{4w4*505i535k4D3G0A0A5p3k0m3m3/4#495u4 4y524T4:413f3I0A3L5G3N4`5K5e4x4,4z4/555R0A3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560A4G5-4I6c4t5:626h5$5O5(673g0A4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560I5o046;5/6f4c6,645^5Q6Z0I5D6?5F5H6d6)4%6U5g6|5y6Y5m0I3I7e6^6*6`795x5P5)6 5,0I3-6(5c776+7k5@7b6~7d5{0I5}746r6_4N6{7l6x6M3H690I6b7E3o1q2/1f2!2N0F1_2S5e4B2Z1w1n2.0P2:7R751n4B7+2g0!0F0@372I5B3w7=7@6/5*232l0P7}6k7 2K5H7G010b0|0%0T5 3J6s2{0T0|0T0E2v1d8e8g1*0{040o8o880Y0|0q5F2?888r0u8e0g8p3@8x5V8A7i0@8r0i0f8e0~7-5K7|017^2^3G3I5h8U7K6:802b828V7~6 1Y5~880N3i0g8?8u8L010#0F0|020n0E0r0H0j8~909294910j8Q8^7;7?8+7_3g5,8!9d8$5R3+0g81837c3*8.878_8{8=8?2q0l390Y1v2x0g0f0g8y0g0(9G0I0g0#1d0H2z0P0E0B9G0!0#0H0P0-1@0!0l9Y9a8S3Q8#0L9f0S5{9i9p7z3G439n8)9;7n5m9/8/9u8|3J8?2p2u0H9A9C0!1O9F0:0g0T1d2Fa82y2D0Y0Q0r0!1%0E2W9U9W1%9!9$1{0Y9W2w0Eau2Aab8k8m2y9(8K9c7}9-699:8+846Z4p9^2c9`6y0SaL9~7u1*9va18?aB0A9I9P0q8J489)4v9+9-6naM9k6Z4GaR8*a@5ma=aX4|25a!a20g0c0B0P0X0R1$9EaG7R9*9j9,8X3g6Ba?8,5m4Xa`aT7Lbja 3Rb2a2aDag0o0e0I0u0g0GbB0CbB0K0Z0u0e0AbB0s0Z0i0gaiakam0gbKbBbAbCbEbG0Zbc3O8Tbf9-6ObkaO5m4?boaN9q4=9s7:b0aZa0b397968 98b}997-8RaH2ya:bh577{bfb-3G58b:a|cdb@c4bda/b)c85qcabp6l5ocfbl5B6=3Mb38G3S0|0Y8z3o8F880r0|0x8Ecz0Y0w8x299bb_8M0|8ta.aY8H048ycQ3R8Nb$2Jb(aJcn71b,b=3f5Dctcc6zc,5Wcy8vcBa,3OcF8_cH04cJ7-c~cW3ScNcYcPcVcR018rcUc54w8Ic!5ec$c3c!c71 5B8Z319+c=5S8(aSb;9=6z8Zc^a2cL8x9WcKcGcIdG8_8r0eb#d3cz0z71030g2V2w0!3U9V0y9DaB31bw1Oa%a)9K8FdldadTcmdo6z9hdrcbc.5+dva{cud=b@c_8_8w040!cDc}czd0d22;d4db0X0!0|5rdO88dQ0|dS2V1v0z1%8 0!9M0P0h9P0J0g1~0h390E0h0!0h9Ge55Yd.dn0Y5B9/d@cq5`d{eO6Z0A9}3me0d5e20!c|2Jeb3Re8dJd5edefe)dbej04el9B0!eo0geqeseu0geweyeAeCeEa+c%b^d/c*d;3faLeNdx9{68eQfbaU0AaWeVdC888a040N1Q1$e-dge3eG8fdH04020q92fr5!cBfue$5e0r8;041 0FfB5;0|eZfM4}d0fyfAehe1c{fQ258r8Pd-dfeJ5Ba=facg6za_9off7L6md b3fk8_fm0!8dfVeX8xfuczdLdifNftg34}8rdNeae78}fzc2gac`cYe!f4dj0|0eg62{fOgig10|0Zf#6reId:eK6zbjf+d}3fbnf/f,gDf?f@f@dDcYdFd.fG0|0pgn3t0|0y0R0R29fLgO4(ddgScXcZg!g7glg%cAg5g*fZgs0if3c)9ecnb+gBdt0Ab/gFgCg~gIgJf^f~g/gfc dIf}dbeYfEgb040DfY1*e+5-g@bef6gy6!cpf:6lceh0g}6#cxh4czfm3b0#0PhicS04gua-f%gx8Ycwg|c.6;fegGhQ86a#h48@gg0,0Hg-d0gRg:gTfJgWgYg-g$h(g(gq8Bg,h/g.fPh@g8g?f$ckaIg_f770hrhSc:hvhPc@fjhWhXfWe3gifF4(e(hbfsh_h8d5d0hhii5ehkfucjb%hni0hp7ei3gCiyc;hPdAi9if4}f`f|ilhcfOhefw0xe9cEgLcCh-0|hI5Jgwho8Yd?f5hs5R7qhRiA9hdBgJhA0|2D0HeB1eipg4hZhF01ini{e2f2h`h?dffCidiUhHg9hJh~c6hL3g7CizdtjeiCdy3HeUhVi/e3iJiRggikjqh9d1iQe6gg0Yh;dKiVhmcliZjdf9i$hSaQi6jj7Oh3eWdbfmi;i?i~dEh!i^fR0|ioiKfsg)j3g#j2jaijg0h=j7g@0m7/7S7*7U7%1f0H7Xj`2Q2L0y1#j@0m7V8R0%0)0+0#04.

😥 Le problème, c'est que les "slices" ne sont pas vraiment au programme de NSI, et que leur utilisation n'est pas toujours efficace. Essayons une version qui n'utilise pas de "slices".

💻 A vous de jouer 2

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kEg[: r);Sé/q(.lo4y,6b=ac1x5+ud3t2à8_Pw7evp-fh09mn]is050F0P0H0y0!0q0#0g0z0q0y0#0#0x010H0!0R010406050#0E0X0X0y0h0t040k0r0q0E0_0r0Y050m101214160~0R04051m1f1p0m1m0~0F0!0Q0.0:0=0@0:0Y0d0E0y0d0P0S0R0t0H0U1d0g0U0!0d0U0q1R0U0H0|050)0w0q0P1y0;0?011Q1S1U1S0H1!1$1Y0H0h1n1M0.190#0R0y0Y0@0I011(1A010T0+0P0Y0y0X0P1Y1}1 241*271$2a2c0|0a0g0M0h0r0R0r0#0!1c0Y0g0%1{0h0h0P0z2x1f2f0Y1n0m1M2K1@1_1^1Z0F2h1B0!0Y292u1Y1v1x0/1)2U2W0Y0r2!1Y0R2D1n2I2K2;0 1~2y2$252*0h130q1Y0y1P2D0T0@030L0L0z2+0P1U2)0r0S0I0S0A0|0g0A1f0y2=2^0}2@2g2`1*2|2~30320P340136383a3c2X3f3f3j0I3m3o1 3q2I2T013v0y2 1n310U333537390%3F2*3H0G3j0G3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0s3j0s3-1g3/3r2_1z3u0r2}3T3x3X3z3Z3D3$3 3(3g0C3j0C452;3:2^3Q3@4f3{3C3#3b4l3e3g0v3j0v4r473;4a3?4c3w3V3y3A4z3~3d3H0O3j0O4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0K3j0K4Z2J4#492%4(4d3^3`4h3|4j4B4:0S0W3j0W4^3O4u3=4}4O3_4Q4i4A3%4D3h0V0|0A0V5a4`4v4)4 5h525j4C3H0A3i045B5r485t4~4x514S4/403h225D3K0m3n3.4!5G5d4w4+4y4.545N0A3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602{5u5J645y550A4F5D4H6b4s5/616g5Z5K5#663g0A4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3h575D596Q5 6S6f6U6I6v6K550I5n046:5F6e4b6+635@5M6Y0I5C6 6@6)6_5f6{5x6X5l0I5P7a724$6T755w5L5$6~5)0I5+5T6c6(7e6*7g5?776}795`0I5|7o6q6^4M6`7h6w6L3f680I6a7B6E7r744*6,6W7w3H0I6m7W7d4{7s7R767i6x3f6A0I6C7N6R7P7E7t6J6j5N0I6N7_5a1q2/1f2!2N0F1_2S5d4A2Z1w1n2.0P2:3p5~1n4A8c2g0!0F0@372I5A3x8j8l6.5%232l0P8r7@6Y5C3-7D010b0|0%0T8e0g6r2{0T0|0T0E2v1d5R2?8C0{040o8e8K3u0|0q3l7p8h7!1*8V0u8Y8C0Y8#8S8d8U0|0i0f8e0~8(5G8q018m2^7V8p8k908s6~8u2b8w968y791Y5}8C0N3j0g9k8.730@0#0F0|020n0E0r0H0j9s9u9w9y9v0j8{9m8i95911 3)948x789K0g8v9M7U3g5)8B9n019p9j9k2q0l390Y1v2x0g0f0g8$0g0(9-0I0g0#1d0H2z0P0E0B9-0!0#0H0P0-1@0!0la29E8}3P8 9I0Y3H5`5gab975l429P9a9R7jaj9f5T8C9Y049k9!2u0H9%9)0!1O9,0:0g0T1d2FaB2y2D0Y0Q0r0!1%0E2W9~a01%a4a61{0Ya02w0EaX2AaE8O8Q2ya88T4uah8n4n9L9c9Na=al2can7)689V7:9X9qauava(0A9/9_0q8=5Va9a/9H0La;0S6magbe9d3H4Fa`9b7H55bi9g9Watav0g0c0B0P0X0R1$9+a-8?bd8rbg6Abja|7I4WbobM55bKbtb0bvava*aJ0o0e0I0u0g0Gb$0Cb$0K0Zb$0e0Ab$0s0Z0i0gaLaNaP0gb/b$b#b%b)b+0ZbF3N8~bebg6NbLa@9S0S4=bPcbao3Hc9bT8*9ob2bw9B9A9t9Ccp9D8(8|a.9GbI923g6!cabq5N57cfcE6YcC5,bw8Z3?0|0Y8%2;8J8C0r0|0x8IcN3R0w8#299Fcl018V8Xbcb08:048$c(3Q8V0ic42Jc6cz9J6y6;cDai5A5ncHd1c~aqb39l8/cPba2JcT9WcV04cX8(dec.c#c:c%c-c)c+c=5X8;ds4%c@c_8)0ga:cA3h8A31ahbl6y3id4dHdDd7cMdac:a0cYcUcWdS9W8V0ec3djcZ0z5C03dA0Y2w0!3T9 0y9*a(31bX1Ob5b79;8Jcvc=dBc}5Oa?cI5l0A22dKa^e02K3ndO9Wc/0!cR3pdkc)dgdicScZ0X0!0|5qd!8Cd$0|d(2V1v0z1%9t0!9?0P0h9_0J0g1~0h390E0h0!0h9-efbbcx2yd~ad6y9UdFbke75(99a{cg7)e#e9d8eh4v0|0!dcaucZejdVb0enepe^c)et04ev9(0!ey0geAeCeE0geGeIeKeMeOb9dyc{96bg0AafeYbQ5_e$bpd53hafcLavcZ8E040N1Q1$e|e.04eefB5ddg020q9wfF5:cPeQdde?9i041 0FfL61e/e;e-fG9rfJcueldP0YfYcZ8V8`d|dpdAc7dC0Aa~fle(7If@fofm8za~ftbwd99Wfw0!8Herec8#fOdz5ddXdvfWfDgbf,0|dZf(dff#fKg8c.duf:gd0|0egf2{fXgx8+gkf.6qf:eU5Abif_e2gHf}f`6kbseag2gRcZc/0,0HgA0@dg0pgX3R0|0y0R0R29fUgtdw0|c,eSfCc;g-4|geg@gyghg#8Vb?ffaaf=d 6ze1fqh4e6cch4e+gRgSdPfEgqeidUhgfChfgmb0dg0DfV25e`5Dh0bHfhf?c9gJh6ce9QgN5%cjgQhdg40|3b0#0PhqgB04gD47gFh2eV6Zh5dL0AcGhCgK6ycKhGhcg3grdQgWg`1*gZg#c/g(g*9(g}g/h;gsg;gu04gwh.cOfDe;gj04g f/g;gG3g6:hWe7ich8chibc g1h)fZfMi3hNgYhihmc)edf+dT04hphj5dhsgbcwbGcyhwd 6 idcciIig7)iIhbfu8Cg5g7ishkgbim4|ejekeggTfNh_hPhuiFac7V5Pd0dL7agMh#3fi.ikebb0fwaG0hipg$fDi 0rfR2Vi 0Ydm0h1 1Hi(g:iEitgzi1c*0|8-izinf*i(8_i*eThT7VeXf;f~793*iM7I7mdNilh*jfh,g#h:jhh=g)g+jch{c:i48@h jO0!i(i7gEi9jsibfkjvhD6~akh!fq7zjChHi{0|2D0HeL1ejlgggV8IiDc5h1c|hU7LiJih7Ji=j+g0h(fve/iTi#heivgndhi!3NiXg{jnjhf-jqj$i,ibgIkpj+bnj*i:gPe,i`c)i|4cj6e/j2j4j@iU5Xj8jahMkmh`jJe/gijRjkkJjmkSdW8^hQeRjektbg7,k2iNbOkwiebSh(h)i$jGjhjIh}inh?jMkO8WjOg?k_g^gvjTjVc^i8k$ia3fhykti:hBamj%79hFkziQhI04j;j?kEk?jX8d0m8g7}8b7 881f0H82lz2Q2L0y1#lw0m808|0%0)0+0#04.

Cours détaillé⚓︎

Cours de Nicolas Revéret

Dans ce cours les tableaux sont des tableaux de taille fixe. La syntaxe .append n'est donc jamais utilisée.

⏳ Nous étudierons une autre présentation de ce tri avec le type list Python dans un second temps

Cours de Nicolas Revéret

➗ Diviser Pour Régner : le tri fusion 🤴⚓︎

😊 Nous allons maintenant implémenter une méthode de tri basée sur "diviser pour régner" : le tri fusion.

Observons cette animation :

Illustration animée (source wikipédia)

Nous disposons d'un tableau (type list de Python) de taille n.
Son premier rang est donc 0 et son dernier rang n-1.
On notera t[a -> b] la liste constituée des éléments de rang compris entre a et b (compris) de la liste t.
La fonction tri_fusion fait appel à la fonction fusion qui permet de fusionner deux listes triées en une liste triée. 


fonction tri_fusion(t)
      """
      entrée ː un tableau t
      sortie ː renvoie un autre tableau qui correspond au tableau t trié
      """
      n = longueur(t)
      si n ≤ 1
              renvoyer t
      sinon 
              m = n//2
              renvoyer fusion(tri_fusion(t[0 -> m-1]), tri_fusion(t[m -> n-1]))

La terminaison est justifiée par la décroissance stricte de n à chaque appel récursif.

💻 A vous de jouer 3

Compléter le script suivant :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013kg[: r);Sé/q(lo4y,6b=ac15ud3t28_Pw7evp-fh09mn]is050B0K0D0w0V0o0W0f0x0o0w0W0W0v010D0V0M010406050W0A0S0S0w0g0r040j0p0o0A0;0p0T050l0{0}0 110_0M04051h1a1k0l1h0_0B0V0L0)0+0-0/0+0T0c0A0w0c0K0N0M0r0D0P180f0P0V0c0P0o1M0P0D0@050!0u0o0K1t0,0.011L1N1P1N0D1V1X1T0D0g1i1H0)140W0M0w0T0/0E011Z1v010O0$0K0T0w0S0K1T1^1`1 1#221X25270@0a0f0H0g0p0M0p0W0V170T0f0Y1?0g0g0K0x2s1a2a0T1i0l1H2F1/1;1:1U0B2c1w0V0T242p1T1q1s0*1!2P2R0T0p2V1T0M2y1i2D2F2,0`1_2t2X202#0g0~0o1T0w1K2y0O0/030G0G0x2$0K1P2!0p0N0C0N0y0@0f0y1a0w2-2:0^2/2b2=1#2@2_2{2}0K2 01313335372S3a0N1}040f0E3h3j1`3l2D2O013q0w2`1i2|0P2~3032340Y3A2#3C0C3e0C3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0q3e0q3*1b3,3m2;1u3p0p2^3Q3s3U3u3W3y3Z3|3#3b0z3e0z422,3-2:3N3;4c3^3x3Y364i393b0t3e0t4o443.473:493r3S3t3v4w3{383C0J3e0J4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0F3e0F4W2E4Y462Y4#4a3=3@4e3_4g4y4-0N0R3e0R4=3L4r3/4`4L3?4N4f4x3!4A3c0Q0@0y0Q574@4s4$4|5e4 5g4z3C0y3d045y5o455q4{4u4~4P4,3}3c3E0y3H0l3i3+3K1l2*1a2V2I0B1;2N5a4x2U1r1i2)0K2+3k5R2E054x5,2b0V0B0/322D5x3s5@5_505h5|0f2g0K5 5v525z3*4H4_0b0@0Y0O5.3F5D5a0T0O0@1/0V0G0O0A2q186h6j4!0?040n6v6b2?0@0%0D6B596x0@0h0e6h0_435S3M5~015`2:3C3E5d6S4+515K1}6326656T605w3b6X5P5=4^200I3e0f6_6H4Z4_0W0B0@020m0A0p0D0i71737577740i6N6{2t6Z0G5{3b3%4M7g675K3%6(27664Q7o1T6:6w6}6 3F6_2k0g0k340T1q2s0f0e0f6F0f0K0W0D0f0A2R7L0V7P0K7d6P5/6R5^6+7i0N3 7l7$6!613~1~647s5J4j7)7v5Q6C1#6~6^6_0H2p0D7F7H0V1J7K0+0f0O182A852t2y0T0L0p0V1Y7S1Y1P7W0f720V7N7P7L2|8n0D1Y6o0k7X7Z3l8C5D7g7(4l7+7=6#7@4l7q6*7-6-0N8I3I6O2.7#5 7(4C8J6+7n7@4C8O8K7.0N8!6a6I7y7~0f7a79727b8@7c8C8V5-8X7%6V3b4T8#8Q524T8*8$7t7@943I7B0f7x6D04198C9g7{0/0p0@0v6h9m8:2?0u6E247e3N6y6A8E9n3O6E7P9z5a6y0h7Y8W4r8G920N4/956,524/99965K9S9e7B9h1#6d040V6g9l9%3:0@9k2,9t6|209p04020o759r9-9E0S0V5l9I6J046M8}9z9P1`3C549T8%5i549X9U5Kad9#9f6`9E9)2y0D0A0g9;3k9?6=3p9G6Ga89D9O7,7h9Q5m5}aFaf5x5kaiaL3baI2F3i9f9.019)360W8B9=aV6ya74pa9aF7(5yaJ8+8Ra-aO9b5ia-aS7Aanax4s0@0S9saV9_9~a#9E0T9:b09E9_0l0lb89u1#a10@5Oa)aD5?a+aH6X2|7ma?5x6%7;9a7?a@6/aTa{a|5aaq0Zatav3KbB4!b6046r6tbG7!be0/9Ba44_bK6o6q6s8dbT20bSbkay9/046Fb!1#6y0da(8 bQ9F04a b%9A0@0U0h0sbd9@az04bWbMbZb_9J0@9C9Nc0b)b+c6a50db,b)b^cab(01a%b|9LaC2.0l5;5T5+5V5(1a0D5Ycy2L2G0w1Wcv0l5W6O0Y0!0$0W04.

Une approche de la complexité du tri fusion⚓︎

⏳ La correction viendra bientôt ...

Une vidéo de Cédric Gerland sur le tri fusion et sa complexité⚓︎

Complexité

Le tri fusion a un coût en \(n \log_2 n\)

Bilan⚓︎

Le tri fusion en entier

Python
def fusion(l1, l2):
    """
    Précondition : l1 et l2 sont deux listes triées
    Postcondition : la fonction renvoie une liste triée constituée de la fusion 
    de l1 et l2
    Exemple :
    fusion([2, 3, 5, 8],[1, 4]) renvoie [1, 2, 3, 4, 5, 8]
    """
    n1 = len(l1)
    n2 = len(l2)
    lst = [] # initialisation de la fusion de l1 et l2 
    i1 = 0 # indice qui sert à parcourir l1
    i2 = 0 # indice qui sert à parcourir l2
    while i1 < n1 and i2 < n2 :
        if l1[i1] < l2[i2]:
            lst.append(l1[i1])
            i1 = i1 + 1
        else :
            lst.append(l2[i2])
            i2 = i2 + 1
    if i1 == n1:
        return lst + l2[i2:]
    if i2 == n2:
        return lst + l1[i1:]

def tri_fusion(lst):
    """
    Précondition : lst est une liste
    Postcondition : la fonction renvoie une liste qui est la liste triée
    """
    n = len(lst)
    if n <= 1:
        return lst
    else :
        m = n // 2
        return fusion(tri_fusion(lst[:m]), tri_fusion(lst[m:]))