Aller au contenu

10) 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

.128013bE];=wlSd[f-:431(gnah.p/+uerovm)q6 x72i,y9éc8s_Ptàk05050j0B0X0u0N0h0U0J0S0h0u0U0U0f010X0N0x010406050U0A0F0F0u0C0P040i0D0h0A0_0D0t050y101214160~0x04051m1f1p0y1m0~0j0N0E0.0:0=0@0:0t0s0A0u0s0B0m0x0P0X0v1d0J0v0N0s0v0h1R0v0X0|050)0b0h0B1y0;0?011Q1S1U1S0X1!1$1Y0X0C1n1M0.190U0x0u0t0@0M011(1A010l0+0B0t0u0F0B1Y1}1 241*271$2a2c0|0a0J0W0C0D0x0D0U0N1c0t0J0%1{0C0C0B0S2x1f2f0t1n0y1M2K1@1_1^1Z0j2h1B0N0t292u1Y1v1x0/1)2U2W0t0D2!1Y0x2D1n2I2K2;0 1~2y2$252*0C130h1Y0u1P2D0l0@030V0V0S2+0B1U2)0D0m0q3f0|0J0q1f0u2=2^0}2@2g2`1*2|2~30320B340136383a3c2X3f0m22040J0M3l3n1 3p2I2T013u0u2 1n310v333537390%3E2*3G0p3i0p3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0o3i0o3.1g3:3q2_1z3t0D2}3U3w3Y3y3!3C3%403)3g0#3i0#462;3;2^3R3^4g3|3B3$3b4m3e3g0I3i0I4s483=4b3@4d3v3W3x3z4A3 3d3G0L3i0L4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0T3i0T4!2J4$4a2%4)4e3_3{4i3}4k4C4;0m0Q3i0Q4_3P4v3?4~4P3`4R4j4B3(4E3f0!0|0q0!5b4{4w4*505i535k4D3G0q0q5p3k0y3m3/4#495u4 4y524T4:413f3I0q3L5G3N4`5K5e4x4,4z4/555R0q3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560q4G5-4I6c4t5:626h5$5O5(673g0q4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560M5o046;5/6f4c6,645^5Q6Z0M5D6?5F5H6d6)4%6U5g6|5y6Y5m0M3I7e6^6*6`795x5P5)6 5,0M3-6(5c776+7k5@7b6~7d5{0M5}746r6_4N6{7l6x6M3H690M6b7E3o1q2/1f2!2N0j1_2S5e4B2Z1w1n2.0B2:7R751n4B7+2g0N0j0@372I5B3w7=7@6/5*232l0B7}6k7 2K5H7G010Z0|0%0l5 7:4|250g3i8e6s2{0l0|0l0A2v1d8k880{040r8t7i3@0|0h5F2?8u0|0O8e0J8l3t8B5V8E8z018v0G0n8e0~7-5K7|017^2^3G3I5h8Y7K6:802b828Z7~6 1Y5~888i3J0J8`8y7u1*0U0j0|020H0A0D0X0e92949698950e8U8|2y8)0V7_3g5,8(7?8/846Z3+0J81837c3*8=878P8 3i8`2p0C0R390t1v2x0J0n0J8C0J0(9M0M0J0U1d0X2z0B0A0K9M0N0U0X0B0-1@0N0R9(9e8W3Q9h9j0m5{9m9u7z3G439s8-9_7n5m9@8?9z908_8`0W2u0X9G9I0N1O9L0:0J0l1d2Fad2y2D0t0E0D0N1%0A2W9!9$1%9*9,1{0t9$2w0Aaz2Aag8p8r2y9.8O7;9n8!1 3G699^9o9v4o8,2c9 6y0maSa38}0@9Aa69W9M0q9O9V0h8N489/4v9;8#4F7{aO8:5m4G9}aYaU9`a{868f3Ra*9C0J0c0K0B0F0x1$9KaL7R9:a}9=6BaT8*5R4Xb18.bq6Zboa%8g8~a5baaIal0r0k0M0O0J0pbI0#bI0T0d0O0k0qbI0o0d0G0Janapar0JbRbIbHbJbLbN0dbj3O8Xbma`0m6Obpa~3G4?btaZ7Lb?byb8bB9C9b9a939cc39d7-8VaM9gb:aQ3g6#b@9p5m58b{b3a03Gcg5Wcabka^cd0t5B6=chaV5naXbub^6zcx5Wba8K8A040t8D3o8J880D0|0f8IcI3S0b8B299f3R8v8xa@a(3S8BcMb.8F040Gb-2Jb/7}9=5Ca|b|6l5Dclbv5mc^b6cH880t0|0ta=3OcO8PcQ04cS7-d9c(0tcW042kcZ5ec#dl5;8Mdo4}8Rc:b7a_ce5Sc_cma!5UcBc`5*8%cG9CcUd4dj9$cTcPcRdN8P8v0kb,decU0S71030J2V2w0N3U9#0u9JaG31bD1OaGa.9Pa;8Jc9cZdwcv6z9l319hci5B9r9tdA7L5+9xa+dJ0|0Nc+2Jdfbz0@dbdd2;ee3R0F0N0|5rdV88dX0|dZ2V1v0S1%930N9S0B0C9V0Y0J1~0C390A0C0N0Ca-duc=8/c@9@d~a}e06z9|e3c~5Ba23md28PdK0Nd7edcUehdQc(emeoe:ef01es04eu9H0Nex0JezeBeD0JeFeHeJeLeNa;ePblc?b;0qaSeUdE6ZffdDe46la$e%dI888a040g1Q1$e@4weaec3Je.910h96fx5!d5fAek5e0D8^1 0jfGdp04e+fQ4}db02fEc8eje9cKe,fBc-8Td^c%ccfddx6mdze!6zb0eZcD3f6n3Mbae(c(fs0N8deqe)c*dr25dSg68LfSfAcU8vdUf!dO04fXfFg3dgdqf,c!0|0kg9cJfTgodm0|0df*6rgod`5Bbofhfm5*bsf^eW3fbxfpf}f}f#0,0Xgs01db0wgTdK0u0x0x29fPgv4(dng(62g5g+g7gqgXfzgTgec/f+cbd!cu5Bb?gFf=3fb`gJcz0qb~gNgOfqg4gbfU25e/gle^e*fJfC040zhc1*e=5-fbctf.d{6!f;f_0qckh3b4hud1h8cUfs3b0U0Bhm0@8vgza?g`gC3g6;hvgKhRc}f_hRhCh8h9gmdLgSg.1*gVg;04gZg#9Hg?0|c$g`fHdjf%gdg:h(gth_c-bVhqaNhs8$71cyhA70flh0i8hYhZfKfRguggdadPhffyfSf%iefV0|hlik5ehofAcrc,hreRb;7ehScziBhVhTdGh7hEeag2ihh#ebhJgUcReicNf#cLh:04hM5JgBg|hQd}g{fi7de29~gG7oe7hZiJ042D0XeK1eisfRgRiPdbiriMhggnh?g)h{j3g,imiW0ngfhNcsi2izdx7CiCi7eYi,iae$e8friKiPe*inhj0fiSd8iUh~dR0|iY5Yi!i3hQfgi(i-7d4piFiDfoa+f~e^fsi?i^jr8BdMi`iphkjVdjgcc-grh|c)hbj*hLjbiZ2?0y7/7S7*7U7%1f0X7Xj{2Q2L0u1#j^0y7V8V0%0)0+0U04.

😥 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

.128013bE];=wlSd[f-:431(gnah.p/+uerovm)q6 x72i,y9éc8s_Ptàk05050j0B0X0u0N0h0U0J0S0h0u0U0U0f010X0N0x010406050U0A0F0F0u0C0P040i0D0h0A0_0D0t050y101214160~0x04051m1f1p0y1m0~0j0N0E0.0:0=0@0:0t0s0A0u0s0B0m0x0P0X0v1d0J0v0N0s0v0h1R0v0X0|050)0b0h0B1y0;0?011Q1S1U1S0X1!1$1Y0X0C1n1M0.190U0x0u0t0@0M011(1A010l0+0B0t0u0F0B1Y1}1 241*271$2a2c0|0a0J0W0C0D0x0D0U0N1c0t0J0%1{0C0C0B0S2x1f2f0t1n0y1M2K1@1_1^1Z0j2h1B0N0t292u1Y1v1x0/1)2U2W0t0D2!1Y0x2D1n2I2K2;0 1~2y2$252*0C130h1Y0u1P2D0l0@030V0V0S2+0B1U2)0D0m0M0m0q0|0J0q1f0u2=2^0}2@2g2`1*2|2~30320B340136383a3c2X3f3f3j0M3m3o1 3q2I2T013v0u2 1n310v333537390%3F2*3H0p3j0p3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0o3j0o3-1g3/3r2_1z3u0D2}3T3x3X3z3Z3D3$3 3(3g0#3j0#452;3:2^3Q3@4f3{3C3#3b4l3e3g0I3j0I4r473;4a3?4c3w3V3y3A4z3~3d3H0L3j0L4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0T3j0T4Z2J4#492%4(4d3^3`4h3|4j4B4:0m0Q3j0Q4^3O4u3=4}4O3_4Q4i4A3%4D3h0!0|0q0!5a4`4v4)4 5h525j4C3H0q3i045B5r485t4~4x514S4/403h225D3K0y3n3.4!5G5d4w4+4y4.545N0q3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602{5u5J645y550q4F5D4H6b4s5/616g5Z5K5#663g0q4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3h575D596Q5 6S6f6U6I6v6K550M5n046:5F6e4b6+635@5M6Y0M5C6 6@6)6_5f6{5x6X5l0M5P7a724$6T755w5L5$6~5)0M5+5T6c6(7e6*7g5?776}795`0M5|7o6q6^4M6`7h6w6L3f680M6a7B6E7r744*6,6W7w3H0M6m7W7d4{7s7R767i6x3f6A0M6C7N6R7P7E7t6J6j5N0M6N7_5a1q2/1f2!2N0j1_2S5d4A2Z1w1n2.0B2:3p5~1n4A8c2g0N0j0@372I5A3x8j8l6.5%232l0B8r7@6Y5C3-7D010Z0|0%0l8e6r250g3j8I8C0t0l0|0l0A2v1d5R2?8C0{040r8N733?0|0h3l7p8h7!1*8Z0O8$7:3R8)8W8d8Y0|0G0n8e0~8,5G8q018m2^7V8p8k948s6~8u2b8w9a8y791Y5}8C8L040J9o0J8=8.0@0U0j0|020H0A0D0X0e9x9z9B9D9A0e8 9r0J93951 3)988x789P0J8v9R7U3g5)8B8%019u3j9p2q0R390t1v2x0J0n0J8*0J0(9=0M0J0U1d0X2z0B0A0K9=0N0U0X0B0-1@0N0Ra79J913P9M0V8n419Q9g9Saj9U9e9W7j5l5`9!8?9%9n9)2u0X9,9.0N1O9;0:0J0l1d2FaD2y2D0t0E0D0N1%0A2Wa3a51%a9ab1{0ta52w0AaZ2AaG8S8U2yad8X4uagai0m685gag9h3H4oao2caq7)a^9k9#aw9p9 9=0q9@9~0h8_5Vaea;999N0t3H6ma_bh9b5l4Fa~9f7H55blb3av9vax9o0c0K0B0F0x1$9:a/8`bg8ra?6Abmb07I4WbrbP55bNbw9s9$byb6a,aL0r0k0M0O0J0pb*0#b*0T0db*0k0qb*0o0d0G0JaNaPaR0Jb?b*b)b+b-b/0dbI3N92bna?6NbOal9X0m4=bScfar3HcdbW3Qb59p9G9F9y9Hcs9I8,90a:8icb963g6!cebt5N57cjcH6YcF5,b68J3u0|0t8+2;9q8C0D0|0f8ecW9#0t0b8)299K5d8Z8#bf8?0t8)cUbJ8?8Z0Gc82JcabLcD5makcL5l5p9da ck7)d52K3ncP8OcSbd2Jc$8?cY04c!8,dibXc(c*1ec:bXc.c,5:8^dw4|c`c|8-9LcC9O6y8A31a`am3h3icKbo5A8AcO9pcQ8(040,0Xc#dU01dkdmcVd!8Z0kc7dnd!0S5C039L0t2w0N3Ta40u9/a*31b#1Oa*b99^bc9qcy9Ka=d00q5PcGdP6y22dOa{ee9jdcdTde040Nc@3Ndo3Qd$dZ8C0F0N0|5qd-8Cd/0|d;2V1v0S1%9y0N9{0B0C9~0Y0J1~0C390A0C0N0Cb8dCc~9aa?5(d2ed3h3*egdLe%dbbzer5X0|0Ndg9nd!eteA9#eweyeu9#eC04eE9-0NeH0JeJeLeN0JePeReTeVeXbceZafdFbj6yatdJbneh3h42e,cg0qatdS9od!8E040g1Q1$f0c;e?epdhe`9w0h9BfGdpcSfJe_cX9m1 0jfP4ve?e^e;4%dk02fNcxd(em0tf#d)0|8~e6dtdEc dG3ha^fpbT5%a}9Vd87I0qb2ekb6fz8CfB0N8He|fHdWfSf:040kdz2{fIgk8/0|d,f,9#f(f*fYe=dWe^ghgjf@gwe@gn0@8Z0df=6qf@e8f`6le(frgNfucl6ybvg6g7ddc%8)a5gEd#0|0wg#c=040u0x0x29fXgB4%dvg;61c?g#d*g)gmg@25gGc{f?cA2ygLfm3hbNf}g26kbRg1d35AbVgVgWg8gYenfSf$4|e{grgeeogvf%0|0zht4|e~5DfjbKe#e9cdh9he6Md6bse)0qcnhhel9#fB3b0U0Bhxg f;hBcBf_h60qcFhGhLcJhdh)eje:hihngldWg!g~1*dkg(h@dVg,g.9-g`0|c/h3fZgxi0gig|engy8{04b`hYh4fl7V6;ecfr6:hJf~6~iifyh/h:cRi9hVh^cZivdVgDgdbXdkhwiB3QhzfSczc^ifh!7VdIf^ha7^dNh+ikdRgVfAe?gchqfQhliyg$dld%3pisdVcTi6gI47gKig3g7agOdLi^gR7)i^e/h/iX04aI0Ci%g*0Ni%0D9m2Vj5c)040C1 1Hi6i2iKi4iAi3c-0|8;iFgwf.i68}ieiPbi7V9Zh(ike+iTi`9Ziqj0emdXg#h_i8h}g/jii8fih{01g{jTj6i6idh2jkh57Vfojxe)7zimiQ6~fxhOhj8?fB2D0XeUdsi!i4jKdniJc9fkiMi@f|j)ikg0apj-79g5e:j1gbj5f!j8cZi*eqd!g*jtjT8Zi:bei3j$i@bljBi`bqjEcg7Wh-jIhQ8R4ckfenj8jaj`i+kljdjf1DhUkoi1i8hskS04jqj{jsggibjvj!k0hCjyi@h8k5i`hck8hH7*kCirj;i#j}jnhu04h`k|g^g+g-jPkWjjk)ge8*i6gAl0h;j7kWjZgJksi?3fhFk.kAcikzgSlkk@gWj1j@j_kHk{i;2?0y8g7}8b7 881f0X82lH2Q2L0u1#lE0y80900%0)0+0U04.

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

.128013b];=wlSd[f-:431(gnahp/uerovm)q6 72i,y9éc8s_Ptk05050i0y0T0t0J0g0Q0G0O0g0t0Q0Q0e010T0J0v010406050Q0x0C0C0t0z0L040h0A0g0x0;0A0s050w0{0}0 110_0v04051h1a1k0w1h0_0i0J0B0)0+0-0/0+0s0r0x0t0r0y0l0v0L0T0u180G0u0J0r0u0g1M0u0T0@050!0b0g0y1t0,0.011L1N1P1N0T1V1X1T0T0z1i1H0)140Q0v0t0s0/0I011Z1v010k0$0y0s0t0C0y1T1^1`1 1#221X25270@0a0G0S0z0A0v0A0Q0J170s0G0Y1?0z0z0y0O2s1a2a0s1i0w1H2F1/1;1:1U0i2c1w0J0s242p1T1q1s0*1!2P2R0s0A2V1T0v2y1i2D2F2,0`1_2t2X202#0z0~0g1T0t1K2y0k0/030R0R0O2$0y1P2!0A0l0o0l0p0@0G0p1a0t2-2:0^2/2b2=1#2@2_2{2}0y2 01313335372S3a0l1}040G0I3h3j1`3l2D2O013q0t2`1i2|0u2~3032340Y3A2#3C0o3e0o3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0n3e0n3*1b3,3m2;1u3p0A2^3Q3s3U3u3W3y3Z3|3#3b0W3e0W422,3-2:3N3;4c3^3x3Y364i393b0F3e0F4o443.473:493r3S3t3v4w3{383C0H3e0H4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0P3e0P4W2E4Y462Y4#4a3=3@4e3_4g4y4-0l0M3e0M4=3L4r3/4`4L3?4N4f4x3!4A3c0V0@0p0V574@4s4$4|5e4 5g4z3C0p3d045y5o455q4{4u4~4P4,3}3c3E0p3H0w3i3+3K1l2*1a2V2I0i1;2N5a4x2U1r1i2)0y2+3k5R2E054x5,2b0J0i0/322D5x3s5@5_505h5|0G2g0y5 5v525z3*4H4_0U0@0Y0k5.5=4^200f3e6h5D5a0s0k0@1/0J0R0k0x2q186n6b200?040q6A594!0s0@0%0T6G4Z4_6D0D0m6h0_435S3M5~015`2:3C3E5d6Y4+515K1}6326656Z605w3b6%5P6i3N6l3F0G6~6N6j1#0Q0i0@020E0x0A0T0d76787a7c790d6T700G6)0R5{3b3%4M7l675K3%6.27664Q7t1T6_6o4!733e6~2k0z0N340s1q2s0G0m0G6L0G0y0Q0T0G0x2R7Q0J7U0y7i6V5/6X5^6;7n0l3 7q7+6*613~1~647x5J4j7.7A5Q6B72746}6~0S2p0T7K7M0J1J7P0+0G0k182A8a2t2y0s0B0A0J1Y7X1Y1P7#0G770J7S7U7Q2|8s0T1Y6t0N7$7(3l8H5D7l7-4l7:7`6+7|4l7v6:7=6?0l8N3I6U2.7*5 7-4C8O6;7s7|4C8T8P7?0l8)6a6H4_7E830G7f7e777g8}7h8H8!5-8$7,6#3b4T8*8V524T8/8+7y7|9a3I7G0G7C4_6J04198H9m800/0A0@0e6h9t8^2?0b6K247j5a6D6F8J9u3O6K7U9G4!6Q7%8#4r8L980l4/9b6=524/9f9c5K9Y9k7G9n206d040J6g9s9-3p0@9r2,9A6O209w04020g7a9y9?9L0C0J5l9P6P0@6S937j9V1`3C549Z8,5i549%9!5Kaj9+9l6 9L9/2y0T0x0z9`3k9|713:9N6Mae9K9U7;7m9W5m5}aLal5x5kaoaR3baO2F3i9l9@0/9/360Q8G9{a#016Dad4pafaL7-5yaP8:8Wa@aU9h5ia@aY8{a!9L9p0C9za,9 a4a+b39_b69L9 0w0wbd9B1#a70@5Oa:aJ5?a=aN6%2|7ra}5x6-7_9g7{a~6^aZataubja$0@axazaB3KaD4s0@6w6ybM7)bHa-0@9J9T9}9^046t6v6x8iaa6CbXb+b#6Lb.0/6D0ja/95bVb4b;bW040c0D0Kbib!aFb$0z6ubRb*bpaEb}bYb_c39M04b:ca3Nb?b|b{cj9Hacb 0D9S5-0w5;5T5+5V5(1a0T5YcB2L2G0t1Wcy0w5W6U0Y0!0$0Q04.

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:]))