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

.1280137àw4xh)1(+5-,_s3uE:/S[ bqn=éve08im.tP]69p2drg;ylckfao050R0E0K0!0H0W0p0x0X0W0!0p0p0B010K0H0P010406050p0r0I0I0!0S0V040v0#0W0r0_0#0A050u101214160~0P04051m1f1p0u1m0~0R0H0D0.0:0=0@0:0A0T0r0!0T0E0m0P0V0K0g1d0x0g0H0T0g0W1R0g0K0|050)0y0W0E1y0;0?011Q1S1U1S0K1!1$1Y0K0S1n1M0.190p0P0!0A0@0Q011(1A010Z0+0E0A0!0I0E1Y1}1 241*271$2a2c0|0a0x0L0S0#0P0#0p0H1c0A0x0%1{0S0S0E0X2x1f2f0A1n0u1M2K1@1_1^1Z0R2h1B0H0A292u1Y1v1x0/1)2U2W0A0#2!1Y0P2D1n2I2K2;0 1~2y2$252*0S130W1Y0!1P2D0Z0@030o0o0X2+0E1U2)0#0m0i3f0|0x0i1f0!2=2^0}2@2g2`1*2|2~30320E340136383a3c2X3f0m22040x0Q3l3n1 3p2I2T013u0!2 1n310g333537390%3E2*3G0q3i0q3M2H3o0~3Q3s0@3T3V053X3Z3A3#3D2V3F3g0e3i0e3.1g3:3q2_1z3t0#2}3U3w3Y3y3!3C3%403)3g0l3i0l462;3;2^3R3^4g3|3B3$3b4m3e3g0N3i0N4s483=4b3@4d3v3W3x3z4A3 3d3G0b3i0b4J3O4u3r4M3S4O4f4Q4h4S3~4l4V3g0G3i0G4!2J4$4a2%4)4e3_3{4i3}4k4C4;0m0O3i0O4_3P4v3?4~4P3`4R4j4B3(4E3f0F0|0i0F5b4{4w4*505i535k4D3G0i0i5p3k0u3m3/4#495u4 4y524T4:413f3I0i3L5G3N4`5K5e4x4,4z4/555R0i3+045+5s5Z4(5#5h4-5j4U5*435-455W5I5Y4L4}5=514.545l5B4p5-4r5~475J612{5v5N655z560i4G5-4I6c4t5:626h5$5O5(673g0i4X5-4Z6q4K5d5;6u5?5%665A6z4?5-4^6E6e6G6t5M6v6j5_4n3f585-5a6R606T6g6V6J6w6L560Q5o046;5/6f4c6,645^5Q6Z0Q5D6?5F5H6d6)4%6U5g6|5y6Y5m0Q3I7e6^6*6`795x5P5)6 5,0Q3-6(5c776+7k5@7b6~7d5{0Q5}746r6_4N6{7l6x6M3H690Q6b7E3o1q2/1f2!2N0R1_2S5e4B2Z1w1n2.0E2:7R751n4B7+2g0H0R0@372I5B3w7=7@6/5*232l0E7}6k7 2K5H7G010Y0|0%0Z5 7:4|250d3i8e6s2{0Z0|0Z0r2v1d8k880{040j8t7i3@0|0W5F2?8u0|0n8e0x8l3t8B5V8E8z018v0h0t8e0~7-5K7|017^2^3G3I5h8Y7K6:802b828Z7~6 1Y5~888i3J0x8`8y7u1*0p0R0|01928U8|2y8)0o7_3g5,8(7?8/846Z3+0x81837c3*8=878P8 3i8`2p0S0C390A1v2x0x0t0x8C0x0(9C0Q0x0p1d0K2z0E0r0f9C0H0p0K0E0-1@0H0C9U948W3Q97990m5{9c9k7z3G439i8-9,7n5m9*8?9p908_8`0L2u0K9w9y0H1O9B0:0x0Z1d2Fa32y2D0A0D0#0H1%0r2W9Q9S1%9W9Y1{0A9S2w0rap2Aa68p8r2y9!8O7;9d8!1 3G699+9e9l4o8,2c9=6y0maI9_8}0@9q9|9M9C0i9E9L0W8N489#4v9%8#4F7{aE8:5m4G9:aOaK9-a.868f3RaW9s0x0s0f0E0I0P1$9AaB7R9$a:9(6BaJ8*5R4Xa@8.bg6ZbeaT8g8~9{b0ayab0j0w0Q0n0x0qby0lby0G0M0n0w0iby0e0M0h0xadafah0xbHbybxbzbBbD0Mb93O8Xbca-0m6Obfa;3G4?bjaP7Lb)boa~br9s9201bZ2Jb#7}9(6#b*9f5m58b.a_9?3Gc05W8VaC96b$aG6z6=c1aL5naNbkb+cg9naX8K8A040A8D3o8J880#0|0B8Icr3S0y8B29953R8v8xa*aU3S8Bcvb!8F040hb{a}a,cf3f71cia`cZclb/6lc!5Wb0cD0A0|0Aa(3Ocx8Pcz04cB7-c@cN0AcF042kcI5ecKd35;8Md64}8RcVb}8/9(5Ua/c)5*22c5bl5mdga|c-88c/d19ScCcycAdv8P8v0wbYc|cD0X71030x2V2w0H3U9R0!9zaw31bt1Oawa!9Fa%8J7-cbbaa+ce0A5B9b3197c2d)c(c6aQ5+cpdq8Pds0HcQ2Jc}bp0@c_c{2;d}3R0I0H0|5rdD88dF0|dH2V1v0X1%0z0r0H9I0E0S9L0c0x1~0S390r0S0H0SaZdcbbb~b%0i9*d+a:d-6z9/9jd:7LeDd?9sc.0|0Hc=d|cDe0dycNe5e7eXd~01eb04ed9x0Heg0xeiek0pemeoeq14etevexa%ezd$eBcY0iaIeFdi6Zf1d/dm68eO8{888a040d1Q1$e#4weRd{3JeV0|020W0K0Ufi5!c:fle35e0#8^1 0Rftd704eSfD4}c_fpfrfH2{c:eTfmcS8TdZcIcXd(6z6nc#c7fXf7cn3ffYc,b0ePfceR8de9d^cPd925dAf?8LfFflcD8vdCe2fn04fKfsf:c~d8cMe$f^g8fjfFfPf}0|0MfS6rgbfV5Bbef3eL6lbieKf86zbn3mf+gxfxfE0,0Kf_d 0|0JgDcO040!0P0P29fCgbd40|cLccgc8CgHgagTfuf{gWggcUfTgkd%5Bb)gogt3fb-gsf%0ib;gwgyd@g6g!g5e$eWg}gcd`fM1*c_0kh30@eZ5-e}aDe fW6!dhgp5*c4g;eHhfdpgycDfd3be;h78Q0|gia)gTgl3g6;hgg.hBdlf%hBhng_fbf;dtgCgP4(c_gGhO620|gKgM9xg#8wgHdse|hSf@0|0wh!eRgecSbLhbcdhd8$c!g-hG5DhFhl70fahJeQgdhtg g0drh,i20|h6h05eh9fld!cRe~deb%7ehChGdkhkcjijhIgz4}fd0Hf/i4hLh2iahPcAe1cwi0cuhYhw5Jg)h=hAd*dIeGio9hinc$7qh~g`e$fd2D0Keu1eizhThMi704i9iwg{h$gY4(gXd#g{fGh%1*8v0tf hxi=h;ihcY7Cikh|eJ9;hh6 9^g^hKcNitiviDi5i1i$25e0iCc?iEh-dzhvh:iNiK7Mj3io4ph{jwiUf,8PiX0(i!hth#dujih4i8jGf=i^0@i;ifi?f|fRi|iI2?0u7/7S7*7U7%1f0K7Xj(2Q2L0!1#j#0u7V8V0%0)0+0p04.

😥 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

.1280137àw4xh)1(+5-,_s3uE:/S[ bqn=éve08im.tP]69p2drg;ylckfao050R0E0K0!0H0W0p0x0X0W0!0p0p0B010K0H0P010406050p0r0I0I0!0S0V040v0#0W0r0_0#0A050u101214160~0P04051m1f1p0u1m0~0R0H0D0.0:0=0@0:0A0T0r0!0T0E0m0P0V0K0g1d0x0g0H0T0g0W1R0g0K0|050)0y0W0E1y0;0?011Q1S1U1S0K1!1$1Y0K0S1n1M0.190p0P0!0A0@0Q011(1A010Z0+0E0A0!0I0E1Y1}1 241*271$2a2c0|0a0x0L0S0#0P0#0p0H1c0A0x0%1{0S0S0E0X2x1f2f0A1n0u1M2K1@1_1^1Z0R2h1B0H0A292u1Y1v1x0/1)2U2W0A0#2!1Y0P2D1n2I2K2;0 1~2y2$252*0S130W1Y0!1P2D0Z0@030o0o0X2+0E1U2)0#0m0Q0m0i0|0x0i1f0!2=2^0}2@2g2`1*2|2~30320E340136383a3c2X3f3f3j0Q3m3o1 3q2I2T013v0!2 1n310g333537390%3F2*3H0q3j0q3L2H3p0~3P3t0@3S3U053W3Y3B3!3E2V3G3g0e3j0e3-1g3/3r2_1z3u0#2}3T3x3X3z3Z3D3$3 3(3g0l3j0l452;3:2^3Q3@4f3{3C3#3b4l3e3g0N3j0N4r473;4a3?4c3w3V3y3A4z3~3d3H0b3j0b4I3N4t3s4L3R4N4e4P4g4R3}4k4U3g0G3j0G4Z2J4#492%4(4d3^3`4h3|4j4B4:0m0O3j0O4^3O4u3=4}4O3_4Q4i4A3%4D3h0F0|0i0F5a4`4v4)4 5h525j4C3H0i3i045B5r485t4~4x514S4/403h225D3K0u3n3.4!5G5d4w4+4y4.545N0i3*5D3,5S3M4_5W4%5Y5g4,5i4T5%425D445,5U5.4K4|5;504-535k5A4o5D4q5}465V602{5u5J645y550i4F5D4H6b4s5/616g5Z5K5#663g0i4W5D4Y6p4J5c5:6t5=5!655z6y4=5D4@6D6d6F6s5I6u6i5^4m3h575D596Q5 6S6f6U6I6v6K550Q5n046:5F6e4b6+635@5M6Y0Q5C6 6@6)6_5f6{5x6X5l0Q5P7a724$6T755w5L5$6~5)0Q5+5T6c6(7e6*7g5?776}795`0Q5|7o6q6^4M6`7h6w6L3f680Q6a7B6E7r744*6,6W7w3H0Q6m7W7d4{7s7R767i6x3f6A0Q6C7N6R7P7E7t6J6j5N0Q6N7_5a1q2/1f2!2N0R1_2S5d4A2Z1w1n2.0E2:3p5~1n4A8c2g0H0R0@372I5A3x8j8l6.5%232l0E8r7@6Y5C3-7D010Y0|0%0Z8e6r250d3j8I8C0A0Z0|0Z0r2v1d5R2?8C0{040j8N733?0|0W3l7p8h7!1*8Z0n8$7:3R8)8W8d8Y0|0h0t8e0~8,5G8q018m2^7V8p8k948s6~8u2b8w9a8y791Y5}8C8L040x9o0x8=8.0@0p0R0|019x8 9r0x93951 3)988x789F0x8v9H7U3g5)8B8%019u3j9p2q0C390A1v2x0x0t0x8*0x0(9(0Q0x0p1d0K2z0E0r0f9(0H0p0K0E0-1@0H0C9}9z913P9C0o8n419G9g9Ia99K9e9M7j5l5`9Q8?9T9n9V2u0K9Y9!0H1O9%0:0x0Z1d2Fat2y2D0A0D0#0H1%0r2W9_9{1%9 a11{0A9{2w0raP2Aaw8S8U2ya38X4ua6a80m685ga69h3H4oae2cag7)a+9k9Ram9p9=9(0i9*9;0W8_5Va4a%999D0A3H6ma,b79b5l4Fa;9f7H55bba_al9van9o0s0f0E0I0P1$9$a#8`b68ra)6Abca?7I4WbhbF55bDbm9s9Sboa|aYaB0j0w0Q0n0x0qbW0lbW0G0MbW0w0ibW0e0M0h0xaDaFaH0xb)bWbVbXbZb#0Mby3N92bda)6NbEab9N0m4=bIc5ah3Hc3bM3Qa{9p9x01b~2Jc0bB963g6!c4bj5N57c9cs6Ycq5,a|8J3u0|0A8+2;9q8C0#0|0B8ecH9R0A0y8)299A5d8Z8#b58?0A8)cFbz8?8Z0hck8-9Bc1co5maacw5l5p9da=ca7)c?2K3ncA8OcDb32JcN8?cJ04cL8,d3bNcPcR1ecXbNcVcT5:8^dh4|c(c*cm9aa)5Bc:be5A3icvdt6y8Acz9pcB8(040,0KcMdC01d5d7cGdI8Z0wb}d8dI0X5C039B0A2w0H3T9`0!9#aW31bR1OaWa 9+b29q8,90a$8ic-9E6y5Pcrdx5Oc@bid}0id{dA9odIcZ040Hc#3Nd93QdKdH8C0I0H0|5qdR8CdT0|dV2V1v0X1%0z0r0H9.0E0S9;0c0x1~0S390r0S0H0Sa~dna5d^b96y9P31a-ac3h3*dwa.eP9jc}dBc e8d19ndIeeel9Rehejef9Ren04ep9Z0Hes0xeuew0peyeAeC14eFeHeJb2eLbAdpc.0iajeRbdeX3h42eWeTfbeZbpec5d8E040d1Q1$e:cY0|e9fubNd5020W0K0Ufy4vcDead2e*9m1 0RfF5Xfwe(fn4%fAfCfEe,fv040AfRdN0|8~d;9Aa(faa+fdbJ5%a:9Lc_7I0ia^e!a|e58Cfp0H8HfXdac!dk25dOg4cCe8fIc+cU0|dQdMcI0|fBfDfOdidEe(f$040wg7dD0Hgn8{040Mf(6qdec,cnd_3hbbf.f?6kbgf=c;5Ablf`f{c~cO8)9{grdJ0|0JgUe70!0P0P29fNgAgc8!gYg3g)4%g6g.61fwgagob-f7d@gCeO3hbDgGgL6ybHgKe1bLgOgPf|gRg9gk4|e+gfhafxg1ed0|0khc25e.5Dg`2yf+gD0ic3h0e1c8h4ffhuflh8fS4|fp3be~hm8/f%hqgBf9htcqhwhAcuhzfjcyh7h8e6gSdGg;25d5gXh$g8g!g$9ZgUdgh*dDf6h;01g:d?g2e%h/gdc)f)gAhsg}6:dsffi4fic6i4c|fmhDhZh|hi5dhe3phE2{fQhJ0@d5hlig4%hogad=c$hreN7V8AhReT6 d f/6~dzgOdIf~g0hffYhhiMfzcKdLijiecEh}04gy47i1iy3g7ai5iC22i8cbi$e3hXh98?fpay0Sin8@e8i^0#9m2Vi^db040S1 1HiWcWh`fGifj7g*8;irg=fZgu9Rc(iYb4j7i27VeQhNh13feVhUi99Pe4hDikg8dFgUh(g,04h,g%j5jDh?jag/0|gqh@e70HiWg_i0jli#3ffcjpd}7ziEgH7^ajjwgQi;0|2D0KeGddiPj8jAd8ivb eMg|7Vf-jYi6f;afj$6~f_fmiJfwiLiTe$gti{iRi d0iWjj5.i!j{i$gFj~iCgJk1jq7WhChYf}8R4ckei`jdh%i}j:k9cOcQj1j30EjHjOg?iWjcj;fPfZg@gv8}hMjmi$g kni9h3kqjZh6ickuhaj?jKhdgWjDjFh.h@h:k-ildEkSjhjMjDjQk?h~kVjV7_i(i9hyk$i6cdi/jy0@fpj-j/kyk,iZ2?0u8g7}8b7 881f0K82lr2Q2L0!1#lo0u80900%0)0+0p04.

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

.1280137w4h)1(5-,_s3u:/S[ bqn=éve08imtP]69p2drg;ylckfao050M0A0F0V0D0R0m0t0S0R0V0m0m0x010F0D0K010406050m0o0E0E0V0N0Q040r0W0R0o0;0W0w050q0{0}0 110_0K04051h1a1k0q1h0_0M0D0z0)0+0-0/0+0w0O0o0V0O0A0j0K0Q0F0e180t0e0D0O0e0R1M0e0F0@050!0u0R0A1t0,0.011L1N1P1N0F1V1X1T0F0N1i1H0)140m0K0V0w0/0L011Z1v010U0$0A0w0V0E0A1T1^1`1 1#221X25270@0a0t0G0N0W0K0W0m0D170w0t0Y1?0N0N0A0S2s1a2a0w1i0q1H2F1/1;1:1U0M2c1w0D0w242p1T1q1s0*1!2P2R0w0W2V1T0K2y1i2D2F2,0`1_2t2X202#0N0~0R1T0V1K2y0U0/030l0l0S2$0A1P2!0W0j0n0j0g0@0t0g1a0V2-2:0^2/2b2=1#2@2_2{2}0A2 01313335372S3a0j1}040t0L3h3j1`3l2D2O013q0V2`1i2|0e2~3032340Y3A2#3C0n3e0n3I2C3k0_3M3o0/3P3R053T3V3w3X3z2Q3B3b0d3e0d3*1b3,3m2;1u3p0W2^3Q3s3U3u3W3y3Z3|3#3b0i3e0i422,3-2:3N3;4c3^3x3Y364i393b0I3e0I4o443.473:493r3S3t3v4w3{383C0b3e0b4F3K4q3n4I3O4K4b4M4d4O3`4h4R3b0C3e0C4W2E4Y462Y4#4a3=3@4e3_4g4y4-0j0J3e0J4=3L4r3/4`4L3?4N4f4x3!4A3c0B0@0g0B574@4s4$4|5e4 5g4z3C0g3d045y5o455q4{4u4~4P4,3}3c3E0g3H0q3i3+3K1l2*1a2V2I0M1;2N5a4x2U1r1i2)0A2+3k5R2E054x5,2b0D0M0/322D5x3s5@5_505h5|0t2g0A5 5v525z3*4H4_0T0@0Y0U5.5=4^200c3e6h5D5a0w0U0@1/0D0l0U0o2q186n6b200?040h6A594!0w0@0%0F6G4Z4_6D0f0p6h0_435S3M5~015`2:3C3E5d6Y4+515K1}6326656Z605w3b6%5P6i3N6l3F0t6~6N6j1#0m0M0@01766T700t6)0l5{3b3%4M7b675K3%6.27664Q7j1T6_6o4!733e6~2k0N0y340w1q2s0t0p0t6L0t0A0m0F0t0o2R7G0D7K0A786V5/6X5^6;7d0j3 7g7X6*613~1~647n5J4j7!7q5Q6B72746}6~0G2p0F7A7C0D1J7F0+0t0U182A802t2y0w0z0W0D1Y7N1Y1P7R0t0v0o0D7I7K7G2|8i0F1Y6t0y7S7U3l8y5D7b7Z4l7$7-6+7/4l7l6:7(6?0j8E3I6U2.7W5 7Z4C8F6;7i7/4C8K8G7)0j8W6a6H4_7u7_0t76017T8S4r8C6#3b4T8X8M524T8$8Y7o7/8|3I7w0t7s4_6J04198y987?0/0W0@0x6h9f8,2?0u6K24795a6D6F8A9g3O6K7K9s4!6Q8?5-8T7Y8`0j4/8}6=524/918~5K9K967w99206d040D6g9e9V3p0@9d2,9m6O209i04020R0F0P9k9#9x0E0D5l9B6P0@6S8y8R9F8^7%7c9I549L8Z5i549P9M5Ka89T976 9x9X2y0F0o0N9)3k9+713:9z6Ma1798_1`5x5ka9935i5m7+6/8%8NaG2F3i979$0/9X360m8x9*aP016Da04paya57Z5y5}a5aa5x3dada+3ba(aM8/aO9x9b0E9laW9.9@aVa^9(a{9x9.0q0qb29n1#9`0@5Oa!9wa48U9I5Na)aJ686-7,927.aF6^aNaiajb8aQ0@amaoaq3Kas4s0@6w6ybA7VbvaX0@9v8@9,9%046t6v6x889}6CbLbVbP6LbY0/6D0saZa3bOau04a`beb+bK040H0f0kb7b:9bbRbFbUb/atb;bMb*c09bb!b 3Nb%b#9yb-caaYb?0f9E5S0q5;5T5+5V5(1a0F5Ycp2L2G0V1Wcm0q5W6U0Y0!0$0m04.

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