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

.128013l(9 _4:;=vm26-uS8w.s3/]+fr7gàebhE[pPicé05qa,onkyd1x)t050X0E0#0R0L0b0u0e0M0b0R0u0u0j010#0L0J010406050u0p0l0l0R0A0W040q0T0b0p0_0T0U050w101214160~0J04051m1f1p0w1m0~0X0L0k0.0:0=0@0:0U0C0p0R0C0E0o0J0W0#0G1d0e0G0L0C0G0b1R0G0#0|050)0F0b0E1y0;0?011Q1S1U1S0#1!1$1Y0#0A1n1M0.190u0J0R0U0@0m011(1A010z0+0E0U0R0l0E1Y1}1 241*271$2a2c0|0a0e0K0A0T0J0T0u0L1c0U0e0%1{0A0A0E0M2x1f2f0U1n0w1M2K1@1_1^1Z0X2h1B0L0U292u1Y1v1x0/1)2U2W0U0T2!1Y0J2D1n2I2K2;0 1~2y2$252*0A130b1Y0R1P2D0z0@030f0f0M2+0E1U2)0T0o0Y3f0|0e0Y1f0R2=2^0}2@2g2`1*2|2~30320E340136383a3c2X3f0o22040e0m3l3n1 3p2I2T013u0R2 1n310G333537390%3E2*3G0v3i0v3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0g3i0g3.1g3:3q2_1z3t0T2}3U3w3Y3y3!3C3%403)3g0P3i0P462;3;2^3R3^4g3|3B3$3b4m3e3g0n3i0n4s483=4b3@4d3v3W3x3z4A3 3d3G0B3i0B4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0r3i0r4!2J4$4a2%4)4e3_3{4i3}4k4C4;0o0d3i0d4_3P4v3?4~4P3`4R4j4B3(4E3f0O0|0Y0O5b4{4w4*505i535k4D3G0Y0Y5p3k0w3m3/4#495u4 4y524T4:413f3I0Y3L5G3N4`5K5e4x4,4z4/555R0Y3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560Y4G5-4I6c4t5:626h5$5O5(673g0Y4X5-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!2N0X1_2S5e4B2Z1w1n2.0E2:7R751n4B7+2g0L0X0@372I5B3w7=7@6/5*232l0E7}6k7 2K5H7G010V0|0%0z5 7:4|250s3i8e6s2{0z0|0z0p2v1d8k880{040c8t7i3@0|0b5F2?8u0|0S8e0e8l3t8B5V8E8z018v0!0h8e0~7-5K7|017^2^3G3I5h8Y7K6:802b828Z7~6 1Y5~888i3J0e8`8y7u1*0u0X0|020Q0p0T0#0i92949698950i8U8|2y8)0f7_3g5,8(7?8/846Z3+0e81837c3*8=878P8 3i8`2p0A0N390U1v2x0e0h0e8C0e0(9M0m0e0u1d0#2z0E0p0Z9M0L0u0#0E0-1@0L0N9(9e8W3Q9h9j0o5{9m9u7z3G439s8-9_7n5m9@8?9z908_8`0K2u0#9G9I0L1O9L0:0e0z1d2Fad2y2D0U0k0T0L1%0p2W9!9$1%9*9,1{0U9$2w0paz2Aag8p8r2y9.8O7;9n8!1 3G699^9o9v4o8,2c9 6y0oaSa38}0@9Aa69W9M0Y9O9V0b8N489/4v9;8#4F7{aO8:5m4G9}aYaU9`a{868f3Ra*9C0e0H0Z0E0l0J1$9KaL7R9:a}9=6BaT8*5R4Xb18.bq6Zboa%8g8~a5baaIal0c0I0m0S0e0vbI0PbI0r0x0S0I0YbI0g0x0!0eanapar0ebRbIbHbJbLbN0xbj3O8Xbma`0o6Obpa~3G4?btaZ7Lb?byb8bB9C9b9a939cc39d7-8VaM9gb:aQ3g6#b@9p5m58b{b3a03Gcg5Wcabka^cd0U5B6=chaV5naXbub^6zcx5Wba8K8A040U8D3o8J880T0|0j8IcI3S0F8B299f3R8v8xa@a(3S8BcMb.8F040!b-2Jb/7}9=5Ca|b|6l5Dclbv5mc^b6cH880U0|0Ua=3OcO8PcQ04cS7-d9c(0UcW042kcZ5ec#dl5;8Mdo4}8Rc:b7a_ce5Sc_cma!5UcBc`5*8%cG9CcUd4dj9$cTcPcRdN8P8v0Ib,decU0M71030e2V2w0L3U9#0R9JaG31bD1OaGa.9Pa;8Jc9cZdwcv6z9l319hci5B9r9tdA7L5+9xa+dJ0|0Lc+2Jdfbz0@dbdd2;ee3R0l0L0|5rdV88dX0|dZ2V1v0M1%930L9S0E0A9V0D0e1~0A390p0A0L0Aa-duc=8/c@9@d~a}e06z9|e3c~5Ba23md28PdK0Ld7edcUehdQc(emeoe:ef01es04eu9H0Lex0eezeBeD0eeFeHeJeLeNa;ePblc?b;0YaSeUdE6ZffdDe46la$e%dI888a040s1Q1$e@4weaec3Je.910b96fx5!d5fAek5e0T8^1 0XfGdp04e+fQ4}db02fEc8eje9cKe,fBc-8Td^c%ccfddx6mdze!6zb0eZcD3f6n3Mbae(c(fs0L8deqe)c*dr25dSg68LfSfAcU8vdUf!dO04fXfFg3dgdqf,c!0|0Ig9cJfTgodm0|0xf*6rgod`5Bbofhfm5*bsf^eW3fbxfpf}f}f#0,0#gs01db0tgTdK0R0J0J29fPgv4(dng(62g5g+g7gqgXfzgTgec/f+cbd!cu5Bb?gFf=3fb`gJcz0Yb~gNgOfqg4gbfU25e/gle^e*fJfC040yhc1*e=5-fbctf.d{6!f;f_0Yckh3b4hud1h8cUfs3b0u0Ehm0@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~gG7oe7hZiJ042D0#eK1eisfRgRiPdbiriMhggnh?g)h{j3g,imiW0hgfhNcsi2izdx7CiCi7eYi,iae$e8friKiPe*inhj0jiSd8iUh~dR0|iY5Yi!i3hQfgi(i-7d4piFiDfoa+f~e^fsi?i^jr8BdMi`iphkjVdjgcc-grh|c)hbj*hLjbiZ2?0w7/7S7*7U7%1f0#7Xj{2Q2L0R1#j^0w7V8V0%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

.128013l(9 _4:;=vm26-uS8w.s3/]+fr7gàebhE[pPicé05qa,onkyd1x)t050X0E0#0R0L0b0u0e0M0b0R0u0u0j010#0L0J010406050u0p0l0l0R0A0W040q0T0b0p0_0T0U050w101214160~0J04051m1f1p0w1m0~0X0L0k0.0:0=0@0:0U0C0p0R0C0E0o0J0W0#0G1d0e0G0L0C0G0b1R0G0#0|050)0F0b0E1y0;0?011Q1S1U1S0#1!1$1Y0#0A1n1M0.190u0J0R0U0@0m011(1A010z0+0E0U0R0l0E1Y1}1 241*271$2a2c0|0a0e0K0A0T0J0T0u0L1c0U0e0%1{0A0A0E0M2x1f2f0U1n0w1M2K1@1_1^1Z0X2h1B0L0U292u1Y1v1x0/1)2U2W0U0T2!1Y0J2D1n2I2K2;0 1~2y2$252*0A130b1Y0R1P2D0z0@030f0f0M2+0E1U2)0T0o0m0o0Y0|0e0Y1f0R2=2^0}2@2g2`1*2|2~30320E340136383a3c2X3f3f3j0m3m3o1 3q2I2T013v0R2 1n310G333537390%3F2*3H0v3j0v3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0g3j0g3-1g3/3r2_1z3u0T2}3T3x3X3z3Z3D3$3 3(3g0P3j0P452;3:2^3Q3@4f3{3C3#3b4l3e3g0n3j0n4r473;4a3?4c3w3V3y3A4z3~3d3H0B3j0B4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0r3j0r4Z2J4#492%4(4d3^3`4h3|4j4B4:0o0d3j0d4^3O4u3=4}4O3_4Q4i4A3%4D3h0O0|0Y0O5a4`4v4)4 5h525j4C3H0Y3i045B5r485t4~4x514S4/403h225D3K0w3n3.4!5G5d4w4+4y4.545N0Y3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602{5u5J645y550Y4F5D4H6b4s5/616g5Z5K5#663g0Y4W5D4Y6p4J5c5: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!2N0X1_2S5d4A2Z1w1n2.0E2:3p5~1n4A8c2g0L0X0@372I5A3x8j8l6.5%232l0E8r7@6Y5C3-7D010V0|0%0z8e6r250s3j8I8C0U0z0|0z0p2v1d5R2?8C0{040c8N733?0|0b3l7p8h7!1*8Z0S8$7:3R8)8W8d8Y0|0!0h8e0~8,5G8q018m2^7V8p8k948s6~8u2b8w9a8y791Y5}8C8L040e9o0e8=8.0@0u0X0|020Q0p0T0#0i9x9z9B9D9A0i8 9r0e93951 3)988x789P0e8v9R7U3g5)8B8%019u3j9p2q0N390U1v2x0e0h0e8*0e0(9=0m0e0u1d0#2z0E0p0Z9=0L0u0#0E0-1@0L0Na79J913P9M0f8n419Q9g9Saj9U9e9W7j5l5`9!8?9%9n9)2u0#9,9.0L1O9;0:0e0z1d2FaD2y2D0U0k0T0L1%0p2Wa3a51%a9ab1{0Ua52w0paZ2AaG8S8U2yad8X4uagai0o685gag9h3H4oao2caq7)a^9k9#aw9p9 9=0Y9@9~0b8_5Vaea;999N0U3H6ma_bh9b5l4Fa~9f7H55blb3av9vax9o0H0Z0E0l0J1$9:a/8`bg8ra?6Abmb07I4WbrbP55bNbw9s9$byb6a,aL0c0I0m0S0e0vb*0Pb*0r0xb*0I0Yb*0g0x0!0eaNaPaR0eb?b*b)b+b-b/0xbI3N92bna?6NbOal9X0o4=bScfar3HcdbW3Qb59p9G9F9y9Hcs9I8,90a:8icb963g6!cebt5N57cjcH6YcF5,b68J3u0|0U8+2;9q8C0T0|0j8ecW9#0U0F8)299K5d8Z8#bf8?0U8)cUbJ8?8Z0!c82JcabLcD5makcL5l5p9da ck7)d52K3ncP8OcSbd2Jc$8?cY04c!8,dibXc(c*1ec:bXc.c,5:8^dw4|c`c|8-9LcC9O6y8A31a`am3h3icKbo5A8AcO9pcQ8(040,0#c#dU01dkdmcVd!8Z0Ic7dnd!0M5C039L0U2w0L3Ta40R9/a*31b#1Oa*b99^bc9qcy9Ka=d00Y5PcGdP6y22dOa{ee9jdcdTde040Lc@3Ndo3Qd$dZ8C0l0L0|5qd-8Cd/0|d;2V1v0M1%9y0L9{0E0A9~0D0e1~0A390p0A0L0Ab8dCc~9aa?5(d2ed3h3*egdLe%dbbzer5X0|0Ldg9nd!eteA9#eweyeu9#eC04eE9-0LeH0eeJeLeN0eePeReTeVeXbceZafdFbj6yatdJbneh3h42e,cg0YatdS9od!8E040s1Q1$f0c;e?epdhe`9w0b9BfGdpcSfJe_cX9m1 0XfP4ve?e^e;4%dk02fNcxd(em0Uf#d)0|8~e6dtdEc dG3ha^fpbT5%a}9Vd87I0Yb2ekb6fz8CfB0L8He|fHdWfSf:040Idz2{fIgk8/0|d,f,9#f(f*fYe=dWe^ghgjf@gwe@gn0@8Z0xf=6qf@e8f`6le(frgNfucl6ybvg6g7ddc%8)a5gEd#0|0tg#c=040R0J0J29fXgB4%dvg;61c?g#d*g)gmg@25gGc{f?cA2ygLfm3hbNf}g26kbRg1d35AbVgVgWg8gYenfSf$4|e{grgeeogvf%0|0yht4|e~5DfjbKe#e9cdh9he6Md6bse)0Ycnhhel9#fB3b0u0Ehxg f;hBcBf_h60YcFhGhLcJhdh)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/iX04aI0Ai%g*0Li%0T9m2Vj5c)040A1 1Hi6i2iKi4iAi3c-0|8;iFgwf.i68}ieiPbi7V9Zh(ike+iTi`9Ziqj0emdXg#h_i8h}g/jii8fih{01g{jTj6i6idh2jkh57Vfojxe)7zimiQ6~fxhOhj8?fB2D0#eUdsi!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?0w8g7}8b7 881f0#82lH2Q2L0R1#lE0w80900%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

.128013l(9 _4:;=vm26-uS8ws3/]fr7gebh[pPicé05qa,onkyd1)t050T0B0W0N0H0b0t0e0I0b0N0t0t0j010W0H0F010406050t0p0l0l0N0y0S040q0P0b0p0;0P0Q050v0{0}0 110_0F04051h1a1k0v1h0_0T0H0k0)0+0-0/0+0Q0A0p0N0A0B0o0F0S0W0D180e0D0H0A0D0b1M0D0W0@050!0C0b0B1t0,0.011L1N1P1N0W1V1X1T0W0y1i1H0)140t0F0N0Q0/0m011Z1v010x0$0B0Q0N0l0B1T1^1`1 1#221X25270@0a0e0G0y0P0F0P0t0H170Q0e0Y1?0y0y0B0I2s1a2a0Q1i0v1H2F1/1;1:1U0T2c1w0H0Q242p1T1q1s0*1!2P2R0Q0P2V1T0F2y1i2D2F2,0`1_2t2X202#0y0~0b1T0N1K2y0x0/030f0f0I2$0B1P2!0P0o0u0o0U0@0e0U1a0N2-2:0^2/2b2=1#2@2_2{2}0B2 01313335372S3a0o1}040e0m3h3j1`3l2D2O013q0N2`1i2|0D2~3032340Y3A2#3C0u3e0u3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0g3e0g3*1b3,3m2;1u3p0P2^3Q3s3U3u3W3y3Z3|3#3b0L3e0L422,3-2:3N3;4c3^3x3Y364i393b0n3e0n4o443.473:493r3S3t3v4w3{383C0z3e0z4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0r3e0r4W2E4Y462Y4#4a3=3@4e3_4g4y4-0o0d3e0d4=3L4r3/4`4L3?4N4f4x3!4A3c0K0@0U0K574@4s4$4|5e4 5g4z3C0U3d045y5o455q4{4u4~4P4,3}3c3E0U3H0v3i3+3K1l2*1a2V2I0T1;2N5a4x2U1r1i2)0B2+3k5R2E054x5,2b0H0T0/322D5x3s5@5_505h5|0e2g0B5 5v525z3*4H4_0R0@0Y0x5.5=4^200s3e6h5D5a0Q0x0@1/0H0f0x0p2q186n6b200?040c6A594!0Q0@0%0W6G4Z4_6D0V0h6h0_435S3M5~015`2:3C3E5d6Y4+515K1}6326656Z605w3b6%5P6i3N6l3F0e6~6N6j1#0t0T0@020M0p0P0W0i76787a7c790i6T700e6)0f5{3b3%4M7l675K3%6.27664Q7t1T6_6o4!733e6~2k0y0J340Q1q2s0e0h0e6L0e0B0t0W0e0p2R7Q0H7U0B7i6V5/6X5^6;7n0o3 7q7+6*613~1~647x5J4j7.7A5Q6B72746}6~0G2p0W7K7M0H1J7P0+0e0x182A8a2t2y0Q0k0P0H1Y7X1Y1P7#0e770H7S7U7Q2|8s0W1Y6t0J7$7(3l8H5D7l7-4l7:7`6+7|4l7v6:7=6?0o8N3I6U2.7*5 7-4C8O6;7s7|4C8T8P7?0o8)6a6H4_7E830e7f7e777g8}7h8H8!5-8$7,6#3b4T8*8V524T8/8+7y7|9a3I7G0e7C4_6J04198H9m800/0P0@0j6h9t8^2?0C6K247j5a6D6F8J9u3O6K7U9G4!6Q7%8#4r8L980o4/9b6=524/9f9c5K9Y9k7G9n206d040H6g9s9-3p0@9r2,9A6O209w04020b7a9y9?9L0l0H5l9P6P0@6S937j9V1`3C549Z8,5i549%9!5Kaj9+9l6 9L9/2y0W0p0y9`3k9|713:9N6Mae9K9U7;7m9W5m5}aLal5x5kaoaR3baO2F3i9l9@0/9/360t8G9{a#016Dad4pafaL7-5yaP8:8Wa@aU9h5ia@aY8{a!9L9p0l9za,9 a4a+b39_b69L9 0v0vbd9B1#a70@5Oa:aJ5?a=aN6%2|7ra}5x6-7_9g7{a~6^aZataubja$0@axazaB3KaD4s0@6w6ybM7)bHa-0@9J9T9}9^046t6v6x8iaa6CbXb+b#6Lb.0/6D0Ea/95bVb4b;bW040w0V0Obib!aFb$0y6ubRb*bpaEb}bYb_c39M04b:ca3Nb?b|b{cj9Hacb 0V9S5-0v5;5T5+5V5(1a0W5YcB2L2G0N1Wcy0v5W6U0Y0!0$0t04.

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