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

.128013fdq6nmi7é4=]3y_ 9pàu08ts5[/v1b(P)l;goEw-ah:+rxS2cek,.050c0Y0x0P0h0I0y0q0X0I0P0y0y0l010x0h0s010406050y0u0g0g0P0T0o040V0L0I0u0_0L0f050B101214160~0s04051m1f1p0B1m0~0c0h0C0.0:0=0@0:0f0K0u0P0K0Y0O0s0o0x0Q1d0q0Q0h0K0Q0I1R0Q0x0|050)0E0I0Y1y0;0?011Q1S1U1S0x1!1$1Y0x0T1n1M0.190y0s0P0f0@0W011(1A010b0+0Y0f0P0g0Y1Y1}1 241*271$2a2c0|0a0q0G0T0L0s0L0y0h1c0f0q0%1{0T0T0Y0X2x1f2f0f1n0B1M2K1@1_1^1Z0c2h1B0h0f292u1Y1v1x0/1)2U2W0f0L2!1Y0s2D1n2I2K2;0 1~2y2$252*0T130I1Y0P1P2D0b0@030p0p0X2+0Y1U2)0L0O0D3f0|0q0D1f0P2=2^0}2@2g2`1*2|2~30320Y340136383a3c2X3f0O22040q0W3l3n1 3p2I2T013u0P2 1n310Q333537390%3E2*3G0n3i0n3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0k3i0k3.1g3:3q2_1z3t0L2}3U3w3Y3y3!3C3%403)3g0z3i0z462;3;2^3R3^4g3|3B3$3b4m3e3g0e3i0e4s483=4b3@4d3v3W3x3z4A3 3d3G0i3i0i4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0w3i0w4!2J4$4a2%4)4e3_3{4i3}4k4C4;0O0r3i0r4_3P4v3?4~4P3`4R4j4B3(4E3f0v0|0D0v5b4{4w4*505i535k4D3G0D0D5p3k0B3m3/4#495u4 4y524T4:413f3I0D3L5G3N4`5K5e4x4,4z4/555R0D3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560D4G5-4I6c4t5:626h5$5O5(673g0D4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560W5o046;5/6f4c6,645^5Q6Z0W5D6?5F5H6d6)4%6U5g6|5y6Y5m0W3I7e6^6*6`795x5P5)6 5,0W3-6(5c776+7k5@7b6~7d5{0W5}746r6_4N6{7l6x6M3H690W6b7E3o1q2/1f2!2N0c1_2S5e4B2Z1w1n2.0Y2:7R751n4B7+2g0h0c0@372I5B3w7=7@6/5*232l0Y7}6k7 2K5H7G010Z0|0%0b5 7:4|250N3i8e6s2{0b0|0b0u2v1d8k880{040F8t7i3@0|0I5F2?8u0|0!8e0q8l3t8B5V8E8z018v0H0R8e0~7-5K7|017^2^3G3I5h8Y7K6:802b828Z7~6 1Y5~888i3J0q8`8y7u1*0y0c0|020d0u0L0x0J92949698950J8U8|2y8)0p7_3g5,8(7?8/846Z3+0q81837c3*8=878P8 3i8`2p0T0j390f1v2x0q0R0q8C0q0(9M0W0q0y1d0x2z0Y0u0U9M0h0y0x0Y0-1@0h0j9(9e8W3Q9h9j0O5{9m9u7z3G439s8-9_7n5m9@8?9z908_8`0G2u0x9G9I0h1O9L0:0q0b1d2Fad2y2D0f0C0L0h1%0u2W9!9$1%9*9,1{0f9$2w0uaz2Aag8p8r2y9.8O7;9n8!1 3G699^9o9v4o8,2c9 6y0OaSa38}0@9Aa69W9M0D9O9V0I8N489/4v9;8#4F7{aO8:5m4G9}aYaU9`a{868f3Ra*9C0q0M0U0Y0g0s1$9KaL7R9:a}9=6BaT8*5R4Xb18.bq6Zboa%8g8~a5baaIal0F0A0W0!0q0nbI0zbI0w0m0!0A0DbI0k0m0H0qanapar0qbRbIbHbJbLbN0mbj3O8Xbma`0O6Obpa~3G4?btaZ7Lb?byb8bB9C9b9a939cc39d7-8VaM9gb:aQ3g6#b@9p5m58b{b3a03Gcg5Wcabka^cd0f5B6=chaV5naXbub^6zcx5Wba8K8A040f8D3o8J880L0|0l8IcI3S0E8B299f3R8v8xa@a(3S8BcMb.8F040Hb-2Jb/7}9=5Ca|b|6l5Dclbv5mc^b6cH880f0|0fa=3OcO8PcQ04cS7-d9c(0fcW042kcZ5ec#dl5;8Mdo4}8Rc:b7a_ce5Sc_cma!5UcBc`5*8%cG9CcUd4dj9$cTcPcRdN8P8v0Ab,decU0X71030q2V2w0h3U9#0P9JaG31bD1OaGa.9Pa;8Jc9cZdwcv6z9l319hci5B9r9tdA7L5+9xa+dJ0|0hc+2Jdfbz0@dbdd2;ee3R0g0h0|5rdV88dX0|dZ2V1v0X1%930h9S0Y0T9V0t0q1~0T390u0T0h0Ta-duc=8/c@9@d~a}e06z9|e3c~5Ba23md28PdK0hd7edcUehdQc(emeoe:ef01es04eu9H0hex0qezeBeD0qeFeHeJeLeNa;ePblc?b;0DaSeUdE6ZffdDe46la$e%dI888a040N1Q1$e@4weaec3Je.910I96fx5!d5fAek5e0L8^1 0cfGdp04e+fQ4}db02fEc8eje9cKe,fBc-8Td^c%ccfddx6mdze!6zb0eZcD3f6n3Mbae(c(fs0h8deqe)c*dr25dSg68LfSfAcU8vdUf!dO04fXfFg3dgdqf,c!0|0Ag9cJfTgodm0|0mf*6rgod`5Bbofhfm5*bsf^eW3fbxfpf}f}f#0,0xgs01db0#gTdK0P0s0s29fPgv4(dng(62g5g+g7gqgXfzgTgec/f+cbd!cu5Bb?gFf=3fb`gJcz0Db~gNgOfqg4gbfU25e/gle^e*fJfC040Shc1*e=5-fbctf.d{6!f;f_0Dckh3b4hud1h8cUfs3b0y0Yhm0@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,imiW0RgfhNcsi2izdx7CiCi7eYi,iae$e8friKiPe*inhj0liSd8iUh~dR0|iY5Yi!i3hQfgi(i-7d4piFiDfoa+f~e^fsi?i^jr8BdMi`iphkjVdjgcc-grh|c)hbj*hLjbiZ2?0B7/7S7*7U7%1f0x7Xj{2Q2L0P1#j^0B7V8V0%0)0+0y04.

😥 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

.128013fdq6nmi7é4=]3y_ 9pàu08ts5[/v1b(P)l;goEw-ah:+rxS2cek,.050c0Y0x0P0h0I0y0q0X0I0P0y0y0l010x0h0s010406050y0u0g0g0P0T0o040V0L0I0u0_0L0f050B101214160~0s04051m1f1p0B1m0~0c0h0C0.0:0=0@0:0f0K0u0P0K0Y0O0s0o0x0Q1d0q0Q0h0K0Q0I1R0Q0x0|050)0E0I0Y1y0;0?011Q1S1U1S0x1!1$1Y0x0T1n1M0.190y0s0P0f0@0W011(1A010b0+0Y0f0P0g0Y1Y1}1 241*271$2a2c0|0a0q0G0T0L0s0L0y0h1c0f0q0%1{0T0T0Y0X2x1f2f0f1n0B1M2K1@1_1^1Z0c2h1B0h0f292u1Y1v1x0/1)2U2W0f0L2!1Y0s2D1n2I2K2;0 1~2y2$252*0T130I1Y0P1P2D0b0@030p0p0X2+0Y1U2)0L0O0W0O0D0|0q0D1f0P2=2^0}2@2g2`1*2|2~30320Y340136383a3c2X3f3f3j0W3m3o1 3q2I2T013v0P2 1n310Q333537390%3F2*3H0n3j0n3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0k3j0k3-1g3/3r2_1z3u0L2}3T3x3X3z3Z3D3$3 3(3g0z3j0z452;3:2^3Q3@4f3{3C3#3b4l3e3g0e3j0e4r473;4a3?4c3w3V3y3A4z3~3d3H0i3j0i4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0w3j0w4Z2J4#492%4(4d3^3`4h3|4j4B4:0O0r3j0r4^3O4u3=4}4O3_4Q4i4A3%4D3h0v0|0D0v5a4`4v4)4 5h525j4C3H0D3i045B5r485t4~4x514S4/403h225D3K0B3n3.4!5G5d4w4+4y4.545N0D3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602{5u5J645y550D4F5D4H6b4s5/616g5Z5K5#663g0D4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3h575D596Q5 6S6f6U6I6v6K550W5n046:5F6e4b6+635@5M6Y0W5C6 6@6)6_5f6{5x6X5l0W5P7a724$6T755w5L5$6~5)0W5+5T6c6(7e6*7g5?776}795`0W5|7o6q6^4M6`7h6w6L3f680W6a7B6E7r744*6,6W7w3H0W6m7W7d4{7s7R767i6x3f6A0W6C7N6R7P7E7t6J6j5N0W6N7_5a1q2/1f2!2N0c1_2S5d4A2Z1w1n2.0Y2:3p5~1n4A8c2g0h0c0@372I5A3x8j8l6.5%232l0Y8r7@6Y5C3-7D010Z0|0%0b8e6r250N3j8I8C0f0b0|0b0u2v1d5R2?8C0{040F8N733?0|0I3l7p8h7!1*8Z0!8$7:3R8)8W8d8Y0|0H0R8e0~8,5G8q018m2^7V8p8k948s6~8u2b8w9a8y791Y5}8C8L040q9o0q8=8.0@0y0c0|020d0u0L0x0J9x9z9B9D9A0J8 9r0q93951 3)988x789P0q8v9R7U3g5)8B8%019u3j9p2q0j390f1v2x0q0R0q8*0q0(9=0W0q0y1d0x2z0Y0u0U9=0h0y0x0Y0-1@0h0ja79J913P9M0p8n419Q9g9Saj9U9e9W7j5l5`9!8?9%9n9)2u0x9,9.0h1O9;0:0q0b1d2FaD2y2D0f0C0L0h1%0u2Wa3a51%a9ab1{0fa52w0uaZ2AaG8S8U2yad8X4uagai0O685gag9h3H4oao2caq7)a^9k9#aw9p9 9=0D9@9~0I8_5Vaea;999N0f3H6ma_bh9b5l4Fa~9f7H55blb3av9vax9o0M0U0Y0g0s1$9:a/8`bg8ra?6Abmb07I4WbrbP55bNbw9s9$byb6a,aL0F0A0W0!0q0nb*0zb*0w0mb*0A0Db*0k0m0H0qaNaPaR0qb?b*b)b+b-b/0mbI3N92bna?6NbOal9X0O4=bScfar3HcdbW3Qb59p9G9F9y9Hcs9I8,90a:8icb963g6!cebt5N57cjcH6YcF5,b68J3u0|0f8+2;9q8C0L0|0l8ecW9#0f0E8)299K5d8Z8#bf8?0f8)cUbJ8?8Z0Hc82JcabLcD5makcL5l5p9da ck7)d52K3ncP8OcSbd2Jc$8?cY04c!8,dibXc(c*1ec:bXc.c,5:8^dw4|c`c|8-9LcC9O6y8A31a`am3h3icKbo5A8AcO9pcQ8(040,0xc#dU01dkdmcVd!8Z0Ac7dnd!0X5C039L0f2w0h3Ta40P9/a*31b#1Oa*b99^bc9qcy9Ka=d00D5PcGdP6y22dOa{ee9jdcdTde040hc@3Ndo3Qd$dZ8C0g0h0|5qd-8Cd/0|d;2V1v0X1%9y0h9{0Y0T9~0t0q1~0T390u0T0h0Tb8dCc~9aa?5(d2ed3h3*egdLe%dbbzer5X0|0hdg9nd!eteA9#eweyeu9#eC04eE9-0heH0qeJeLeN0qePeReTeVeXbceZafdFbj6yatdJbneh3h42e,cg0DatdS9od!8E040N1Q1$f0c;e?epdhe`9w0I9BfGdpcSfJe_cX9m1 0cfP4ve?e^e;4%dk02fNcxd(em0ff#d)0|8~e6dtdEc dG3ha^fpbT5%a}9Vd87I0Db2ekb6fz8CfB0h8He|fHdWfSf:040Adz2{fIgk8/0|d,f,9#f(f*fYe=dWe^ghgjf@gwe@gn0@8Z0mf=6qf@e8f`6le(frgNfucl6ybvg6g7ddc%8)a5gEd#0|0#g#c=040P0s0s29fXgB4%dvg;61c?g#d*g)gmg@25gGc{f?cA2ygLfm3hbNf}g26kbRg1d35AbVgVgWg8gYenfSf$4|e{grgeeogvf%0|0Sht4|e~5DfjbKe#e9cdh9he6Md6bse)0Dcnhhel9#fB3b0y0Yhxg f;hBcBf_h60DcFhGhLcJhdh)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/iX04aI0Ti%g*0hi%0L9m2Vj5c)040T1 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?0B8g7}8b7 881f0x82lH2Q2L0P1#lE0B80900%0)0+0y04.

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

.128013fdq6nmi7é4=]3y_ 9pu08ts5[/v1b(P)l;gow-ah:rS2cek,050c0U0w0N0h0H0x0q0T0H0N0x0x0l010w0h0s010406050x0t0g0g0N0Q0o040R0K0H0t0;0K0f050A0{0}0 110_0s04051h1a1k0A1h0_0c0h0B0)0+0-0/0+0f0J0t0N0J0U0M0s0o0w0O180q0O0h0J0O0H1M0O0w0@050!0D0H0U1t0,0.011L1N1P1N0w1V1X1T0w0Q1i1H0)140x0s0N0f0/0S011Z1v010b0$0U0f0N0g0U1T1^1`1 1#221X25270@0a0q0F0Q0K0s0K0x0h170f0q0Y1?0Q0Q0U0T2s1a2a0f1i0A1H2F1/1;1:1U0c2c1w0h0f242p1T1q1s0*1!2P2R0f0K2V1T0s2y1i2D2F2,0`1_2t2X202#0Q0~0H1T0N1K2y0b0/030p0p0T2$0U1P2!0K0M0n0M0C0@0q0C1a0N2-2:0^2/2b2=1#2@2_2{2}0U2 01313335372S3a0M1}040q0S3h3j1`3l2D2O013q0N2`1i2|0O2~3032340Y3A2#3C0n3e0n3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0k3e0k3*1b3,3m2;1u3p0K2^3Q3s3U3u3W3y3Z3|3#3b0y3e0y422,3-2:3N3;4c3^3x3Y364i393b0e3e0e4o443.473:493r3S3t3v4w3{383C0i3e0i4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0v3e0v4W2E4Y462Y4#4a3=3@4e3_4g4y4-0M0r3e0r4=3L4r3/4`4L3?4N4f4x3!4A3c0u0@0C0u574@4s4$4|5e4 5g4z3C0C3d045y5o455q4{4u4~4P4,3}3c3E0C3H0A3i3+3K1l2*1a2V2I0c1;2N5a4x2U1r1i2)0U2+3k5R2E054x5,2b0h0c0/322D5x3s5@5_505h5|0q2g0U5 5v525z3*4H4_0V0@0Y0b5.5=4^200L3e6h5D5a0f0b0@1/0h0p0b0t2q186n6b200?040E6A594!0f0@0%0w6G4Z4_6D0G0P6h0_435S3M5~015`2:3C3E5d6Y4+515K1}6326656Z605w3b6%5P6i3N6l3F0q6~6N6j1#0x0c0@020d0t0K0w0I76787a7c790I6T700q6)0p5{3b3%4M7l675K3%6.27664Q7t1T6_6o4!733e6~2k0Q0j340f1q2s0q0P0q6L0q0U0x0w0q0t2R7Q0h7U0U7i6V5/6X5^6;7n0M3 7q7+6*613~1~647x5J4j7.7A5Q6B72746}6~0F2p0w7K7M0h1J7P0+0q0b182A8a2t2y0f0B0K0h1Y7X1Y1P7#0q770h7S7U7Q2|8s0w1Y6t0j7$7(3l8H5D7l7-4l7:7`6+7|4l7v6:7=6?0M8N3I6U2.7*5 7-4C8O6;7s7|4C8T8P7?0M8)6a6H4_7E830q7f7e777g8}7h8H8!5-8$7,6#3b4T8*8V524T8/8+7y7|9a3I7G0q7C4_6J04198H9m800/0K0@0l6h9t8^2?0D6K247j5a6D6F8J9u3O6K7U9G4!6Q7%8#4r8L980M4/9b6=524/9f9c5K9Y9k7G9n206d040h6g9s9-3p0@9r2,9A6O209w04020H7a9y9?9L0g0h5l9P6P0@6S937j9V1`3C549Z8,5i549%9!5Kaj9+9l6 9L9/2y0w0t0Q9`3k9|713:9N6Mae9K9U7;7m9W5m5}aLal5x5kaoaR3baO2F3i9l9@0/9/360x8G9{a#016Dad4pafaL7-5yaP8:8Wa@aU9h5ia@aY8{a!9L9p0g9za,9 a4a+b39_b69L9 0A0Abd9B1#a70@5Oa:aJ5?a=aN6%2|7ra}5x6-7_9g7{a~6^aZataubja$0@axazaB3KaD4s0@6w6ybM7)bHa-0@9J9T9}9^046t6v6x8iaa6CbXb+b#6Lb.0/6D0za/95bVb4b;bW040m0G0Wbib!aFb$0Q6ubRb*bpaEb}bYb_c39M04b:ca3Nb?b|b{cj9Hacb 0G9S5-0A5;5T5+5V5(1a0w5YcB2L2G0N1Wcy0A5W6U0Y0!0$0x04.

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