Algorithmes - Les indispensables

Les indispensables

Les indispensables sont ... indispensables 😂

I. Recherche dichotomique⚓︎

Mon info

La recherche dichotomique permet de rechercher un entier dans une liste triée, ainsi que sa position.

Quel est le principe de la dichotomie ? réfléchir avant de cliquer 😊

Le principe de la recherche dichotomique d'un entier v dans une liste triée de n éléments est le suivant :

Si v est égal à l'élément se trouvant au milieu de la liste liste[milieu] , l'entier v est trouvé, et on renvoie sa position.
Sinon si v < liste[milieu], on recommence la recherche dans la première moitié de la liste : liste[0 -> milieu-1]
Sinon on recommence la recherche dans la seconde moitié de la liste : liste[milieu + 1 -> fin]

Exercice 1 : Appartenance par dichotomie

Compléter la fonction dichotomie qui prend en paramètre une liste Python nombres et un valeur cible. Cette fonction renvoie True si cible est dans nombres et False sinon.

Version sans code à trousVersion avec code à trous

Évaluations restantes : 5/5

.128013A8/olvnRxhO43{2;kw:S7g,I) N=6D+fèùà9êb-u_LyzPp^]T}am0irsF[é5q.À1edt(c050=0;0?0Z0$0f0(0A0^0f0Z0(0(0C010?0$0U010406050(0O0!0!0Z0%0R040u0e0f0O190e0h0A020Z0!0U0q0A0i0;1j0%0-0O0;0(050d1g1i1k1m1e0U04051R1K1U0d1R1e0=0$0g11131517130h0w0O0Z0w0;0N0U0R0?0k1t0A0k0$0w0k0f1}0k0?1c050|0M0f0;1%1416011|1~201~0?2628240?0%1S1^111p0(0U0Z0h170p012a1)010G0~0;0h1x0;242s2u2z2c2C282F0!2H040a0A0T0%0e0U0e0(0$1s1u0`2q0%0%0;0^2$1K2J0h1S0d1^2=2m2o2n250=2L1*0$0h2E2Z241!1$122b2 310h0e35240U2+1S2:2=3i1f2t1u372A3b0%1j0f240Z1{2+0G17030P0P0^3c0;203a0e0N0#0N0:1c0A0:1K0Z3j3m1d3l2K3o2c3q3s3u3w0;3y013A3C3E3G323J0N2x040A0p3Q3S2u3U2:2~013Z0Z3t1S3v0k3x3z3B3D0`3-3b3/0n3N0n3^2/3T1e3|3X173 410543453)473,303.3K0m3N0m4g1L4i3V3n1(3Y0e3r403#443%463+494v4b3K0,3N0,4B3i4j3m3}4n4L4r3*483F4R3I3K0D3N0D4X4D4k4G4m4I3!423$3(4)4u3H3/0v3N0v4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0c3N0c562;584F385b4J4o4q4N4s4P4+5j0N0K3N0K5o3{4!4l5t4{4p4}4O4*4a4-3L0#1c0:0#5G5q4#5c5v5N5y5P4,3/0:3M045+5X4E5Z5u4%5x4 5i4w3L3;0:3@0d3R4h3`1V3g1K352^0=2o2}5J4*341#1S3f0;3h3T612;054*6i2K0$0=173B2:5*3#6q6s5z5Q6v0A2P0;6y5(5B5,4g4@5s0r1c0`0G6k6o5r2A0s3N6Q5:5J0h0G6N0$0^1_0?0e0!0$0;6W6K2A1b040@6.5I5a0h1c3b0!0M2+1J4C626/2c6;0x6Q0A6X6_1c0^0$276-716l73176;0z0t6Q1e7g6R0A6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0A7M795s6`040`0M1r777O2A0e1c0C7V7i016+1c5W7p7o3k3|7z0P6u3K4d4|7/6G5`4d7E2Q7G5_4S0N7?3^7M7N7$7Q2C0h7#6^5s7Y047!7p78860M1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0z8a8n7X1c0N8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040s1|288I4#6N0;7T0?8^5J8d020f0?0q8f3i8-8E8t04888O5J6;7m7+8O7/7;0N4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200;0O8~5a8d953T978J018p9c7a9a309H8c1c0F9U3p8`8|9Q8o8B9$8F040d0d9)2c8L5~4Y9h9n9j4/9m9t8Y0N4/8!9{9p9}7J8+9y858.2c8:0$6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0*9.9B049D6,9G8r7$6;0W9f9=aE4!9i8T0N539`8$7H80539 aR7 5RaP9xa58,ad8:2+0?0O0%89aiau010r0^1c0X0%1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900w93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0(7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0)40c8b#0^5,030A2!0A1`0h003v2t102m0e0O0g0+cL6j0d6n636h656e1K0?68df2{2?0Z7e2=661Q7q5J2+0!0P0G0Z0r0;0P0k7?1C1E1G1I0Ace6l1X3U353}0Z0=0!1t2#0$1`300G8d1QdMdOdQ2$0N190?2k041C6%0;0%d,0A2t0%0A1!6%0e6)6+7f1Y1T040y0fc_c~0w2#d?000O1u400w4I2#0k2Q2L0$dE0.0A0Q292j0;0Z0Od:0%0$102Ed:1k1x0H2m290=0ee51fd21,040e271}0Z6)0$ds2E0?0A0LeA0A2m0$d61LeG0w040.1V3U1R0/110k0ZdE7r0?0+0%eMdS0h0xc{1uc8d?1D2u2(c`130A0g409Fd=0^eQe?280A1IeR0+0wf60A0J0Af36m3E04bhah6ndGe(1e0O0f3U2004c`d30$e`1`2+0h0geD290$1i0+1!eM1DeQ786na@a_d9fo1Kfz1efzc`3be_110{0?29fq29fec_eDeR7mfwfy0$fA0O0Ue=aC2+fjfl3vf528a+f)0h2mfi0t7re1dv1re,d-d,d=0=2u10f3d;19eB2W2#eBeqenep0A6?6n7Sge0C0Abxeq0F3O1K6n8C0dfZ05fzdUf}f729fkf3g3f7g6g8fcga0~0AgdeRghghd?gkg1ew0%go0Afh0Od/0=gtdl28gvgxfo880AgBgD0A0NgGfW0`04gJgL0df@7oh9hbd~0Q3v0S1teB292+g(0k290@0f000+0^1keRfa29fnh6cxfs0{fSfogz8}h56h0zc_hlfN0Oe5fk6%e.1He:e=e@1`gafB1u88e5d;0A0ZfIeOhEhA301v921AhGgHfoe`0^00f/e/fm6nf-h?h66Ch`0(eRd0g*0hglemg_eo0Oej0le|4IeR2(f30Md312f.eRfGh*hy6nc/0 7f6ne%dJ7odo0_1#dYdP0hdRdT6ZdW1TiEd!e^d$2#d)0B8vf 1j0jfL40e~eVd30%102(ilg=2870d}1R2V32i80Ae80Ahthve630d@fKiG19iYhz6hg~h3h=hI3=fgiYfkad1ked1jf+0j1c090@5V0V0K09gJ3ie`0@f90A1G0$fdi4jt1.0h2}0!0Lef2m0H100we?jA0ziyi-040Eg+fc0UeOhk10hu0(fE0Ig,f-i2f/i63f0+c8g70;fE1u0%0+40etemd3i9d1i#i%29i)in102Y15ag1IjM3Uhefz0beq6gd{d=6)a+j.h(i=1ui^g.fdfHeO1`2(jbes1^je0;jg04ji090Ge?0^0ojk0K0Y0o0p0Yjn6Qh^i3eRfk1!f kq7$jcktfPkwji0,0A09192Q10jk0ckK8rgKf_f!f_k9e~0OiW0HjEi#kg3vi?kkhwkn2W2%hykTkseekWjh0@kzkB0okZk#fLdFk)kGkIk+96h_f/kPjTcv5skUl6jfl80pldk$lg0#0V0vlkd8gLk830c`f1hOf+0A0.lNfYk.gMk:gtfG19k^j@kfe{khk}hukl0=h`l01`krjdl7kxl9kA0ZkCkEli0V0o0n0#0YkJjo9LlmjxlokRl)0gko1u0:iyhdfxdp0blHfDi710e82920i4hkeV0}0ffcl,kVlul/kElD3`e`evgv0U1qeul*1ul{i!a+101`0(0}eRf2hs0f0+2Qg7h,6hh j6jwi5j:j+0?k5iA6eiA0{mp0(04.

Évaluations restantes : 5/5

.128013A8/olvnRxhO43{2;kw:S7g,I) N=6D+fèùà9êb-u_LyzPp^]T}am0irsF[é5q.À1edt(c050=0;0?0Z0$0f0(0A0^0f0Z0(0(0C010?0$0U010406050(0O0!0!0Z0%0R040u0e0f0O190e0h0A020Z0!0U0q0A0i0;1j0%0-0O0;0(050d1g1i1k1m1e0U04051R1K1U0d1R1e0=0$0g11131517130h0w0O0Z0w0;0N0U0R0?0k1t0A0k0$0w0k0f1}0k0?1c050|0M0f0;1%1416011|1~201~0?2628240?0%1S1^111p0(0U0Z0h170p012a1)010G0~0;0h1x0;242s2u2z2c2C282F0!2H040a0A0T0%0e0U0e0(0$1s1u0`2q0%0%0;0^2$1K2J0h1S0d1^2=2m2o2n250=2L1*0$0h2E2Z241!1$122b2 310h0e35240U2+1S2:2=3i1f2t1u372A3b0%1j0f240Z1{2+0G17030P0P0^3c0;203a0e0N0:3J1c0A0:1K0Z3j3m1d3l2K3o2c3q3s3u3w0;3y013A3C3E3G323J0N2x040A0p3P3R2u3T2:2~013Y0Z3t1S3v0k3x3z3B3D0`3,3b3.0n3M0n3@2/3S1e3{3W173~400542443(463+303-3K0m3M0m4f1L4h3U3n1(3X0e3r3 3!433$453*484u4a3K0,3M0,4A3i4i3m3|4m4K4q3)473F4Q3I3K0D3M0D4W4C4j4F4l4H3Z413#3%4(4t3H3.0v3M0v4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0c3M0c552;574E385a4I4n4p4M4r4O4*5i0N0K3M0K5n3`4Z4k5s4`4o4|4N4)494,3J0#1c0:0#5F5p4!5b5u5M5x5O4+3.0:0:5T3O0d3Q4g564D5Y5t4$5w4~5h4v3J3:0:3?5.3^2;1V3g1K352^0=2o2}5I4)341#1S3f0;3h3S5:634)6j2K0$0=173B2:5)3!6q6s5y5P6v0A2P0;6y5%5A5+2=5/4?5r0r1c0`0G6l6o5q2A0s3M6R5=5I0h0G6O0$0^1_0?0e0!0$0;6X6L2A1b040@6/5H590h1c3b0!0M2+1J4B3_6Y596=0x6R0A745r6{040^0$276.72636:2c6=0z0t6R1e7i6S0A6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610A7N797k4l6O0;0M1r787a2A0e1c0C7W7Q016,1c5V7r7q3k3{7B0P6u3K4c4{7:6G5|4c7G2Q7I5{4R0N7@3@7O7P6_7b1c2C0h7$877Y7!8c587b0M1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0z8g8z177Z040N8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040s1|288J6Z7S7U0?8^598G020f0?0q7#7r868n8t048a8P5I6=7o7,8P7:7=0N4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200;0O8}5r8G943i968E016=8q7.8d989a958.018G0F9F3p8`7V8r7%7m9b8~1c0d0d9)5r8L608O9$4Z9h8U0N4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0$6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0*9.9Z049B6-9E9?au9M1c0W9e9=at1u9^2u518W9}9o0N528#aR5A528+a7a79U8:2+0?0O0%8bad9Q8/0^1c0X0%1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0w92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0(7hb?9c1cbF5;bHaN0h5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0$5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0ra:040)3 c8cN3k0d6n646i666f1K0?69c~2{2?0Z7g2=671Q7s5I2+0!0P0G0Z0r0;0P0k7@1C1E1G1I0Acd631X3T353|0Z0=0!1t2#0$1`300G8G1Qdvdxdz2$0N190?2k041C6(0;0%dR0A2t0%0A1!6(0e6*6,7h1Y1T040y0f0A0(001/2#dY000O1u3 0w4H2#0k2Q2L0$dn0.0A0Q292j0;0Z0OdV0%0$102EdV1k1x0H2m290=0ed=1f2m1t0w040e271}0Z6*0$db2E0?0A0Lek0A2m0$0+2/eq1,040.1V3T1R0/110k0Zdn7t0?0+0%exdB0h0x0A1`c8dY1D2u2(2!0A130A0g3 9DdX0^eBe!280A1IeC0+0we^0A0Je;3v056nbh7h6ndpeP1e0O0f3T2004e:0e0O0$e(1`2+0h0gen290$1i0+1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0?29fbe 0(eC0(eneC7ofhfj0$fl0O0UeZaC2+f5f7e?e^a*fR0h2mf40t7td-de1reTdSdRdX0=2u10e=dW19el2W2#eleae7e90A6@6nbZg00C0Ab+ea0F3N1K6n8C0dfL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0Af eCg3g3dYg6f;g96-0Af30OdU0=gfd428ghgjfJ8a0Agngp0A0NgsfI0`04gvgx0df%7qg|g~d*0Q3v0S1tel292+gS0k290@0f000+0^1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0zd.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0A0ZfuezfEhn1u9092e,b!hx04e(0^00f00AeWe=ht6ifbhpg_6Ch,fXeg10g50hg7e6g)e80Oe30l1ufZ0%eC2(e=0Mfn12290{0AfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0hdAdC6!dF1TixdJe$dL2#dO0Bbr291j0jfx3 e,eGfn0%h}29idg#2871d)1R2V32h 0Ad^0Ahghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0j1c090@5U0V0K09gv3ie(0@e{h.fofWeC2m0H100we!0h0=0ziri$040EgVe~0Uezh710hh0(fq0If;fV0hh`eC2t103f0+c8f_0;fq1u0%0+3 ede6fni0106*a*iW0AiYifjS2Z2!7g0(jy3Th1fk0bea6hd%dXj,0%jYhTi+1ui.i9e ftez1`2(j4ec1^j70;j904jb090Ge!0^0ojd0K0Y0o0p0Yjg6Rh*jPf:1!f/kf7%j5kifBkljb0,0A09192Q10jd0ckz8rgwf)fMf)j~e,0OiP0Hd k3k53vi,k9hjkc2W2%hlkHkhd~kKja0@kokq0okNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0pl1kQl40#0V0vl86kkXf(040b30e:e/hD290.lC1Kgxj}gffs19k)j(a*k,k7i-hhka0=h,k;1`kgj6k{kmk}kp0Zkrktl60V0o0n0#0Ykyjhamlah{lcjFd?2E0gkd1u0:irh0fid8lwh fpgUi*d^2920fXh7eG0}0fe~lWkJlilZktlr3_e(efgh0U1qeelU1ul,iTj-e)i70}fY0$e;hf0f0+2Qf_hXg_h?h(joebjUeBj`it6fit0{me0(04.

Exercice 2 : Appartenance et indice par dichotomie

Compléter la fonction indice qui prend en paramètre une liste Python tableau et une valeur cible. Cette fonction renvoie l'indice de cible dans tableau si cible est dans tableau et None sinon.

Version sans code à trousVersion avec code à trous

Évaluations restantes : 5/5

.1280138/olvnRxhO432;kw:S7g,I) N=6D+Efèà9b-u_LCyPp]Tam0irs[é*5q.î1edt(c050-0,0.0U0X0e0Z0y0:0e0U0Z0Z0A010.0X0R010406050Z0L0V0V0U0Y0P040s0d0e0L140d0g0y020U0V0R0o0y0h0,1e0Y0(0L0,0Z050c1b1d1f1h190R04051M1F1P0c1M190-0X0f0|0~10120~0g0u0L0U0u0,0K0R0P0.0j1o0y0j0X0u0j0e1^0j0.17050@0J0e0,1Y0 11011@1_1{1_0.21231 0.0Y1N1:0|1k0Z0R0U0g120n01251!010F0_0,0g1s0,1 2n2p2u272x232A0V2C040a0y0Q0Y0d0R0d0Z0X1n1p0=2l0Y0Y0,0:2X1F2E0g1N0c1:2-2h2j2i200-2G1#0X0g2z2U1 1V1X0}262`2|0g0d301 0R2$1N2+2-3d1a2o1p322v360Y1e0e1 0U1?2$0F12030M0M0:370,1{350d0K0n0K0+170y0+1F0U3e3h183g2F3j273l3n3p3r0,3t013v3x3z3B2}3E3E3I0n3L3N2p3P2+2_013U0U3o1N3q0j3s3u3w3y0=3(363*0m3I0m3.2*3O193=3S123^3`053|3~3!403%2{3)3F0l3I0l491G4b3Q3i1Z3T0d3m3_3W3}3Y3 3$424o443F0%3I0%4u3d4c3h3?4g4E4k3#413A4K3D3F0B3I0B4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0t3I0t4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0b3I0b4 2,514y33544C4h4j4G4l4I4!5c0K0I3I0I5h3;4T4e5m4;4i4?4H4Z434$3G0W170+0W5z5j4U555o5G5r5I4#3*0+3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0c3M4a3:1Q3b1F302:0-2j2^5C4Z2 1W1N3a0,3c3O5`2,054Z6b2F0X0-123w2+5Z3W6j6l5s5J6o0y2K0,6r5X5u5#494-5l0p170=0F6d6h5k2v0q3I6J5)5C0g0F172{1V0:0,6P6D2v16040/6Z5B530g172e0,0U0L6)525l6$0v6J0y6Q6+170:0X226Y4v5{6!276$0x0r6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040y7z6{754f6G0,0J1m6`6|5l0d170A7I7C010V0X175P7c3P7V5)7m0M6n3F464=7Z6z5:467r2L7t5/4L0K7%3.7A7B6*5l6,042x0g7O7`2v7L047N7V7_6?3k0J172J6=6L76176(7X7P7|6.6:8d3?77808827830K8q8e127R5N7a8n7Z7#0K4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040q1@238v4U7E7G0.8#5C83020e0.0o853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0,6;869l12838;3O8?8o8g8{6}040=8(8*53830D9G7{8_2{9B6@170x9K82170c0c9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0X6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0!9O3k9n0_0X9qan8f040S8~9$8i4T8C9*0K4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0K5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0U718mazaX01alataea$asbm8@6$aw8Abu0yaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0.0L0Y7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0Z72aibn8}byb~1pbB0g5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0+7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010p0:170z1ob}4w7X0c6g5|6a5~671F0.61c@2?2.bj232-5 1L6K3?2$0V0M0F0U0p0,0M0j7%1x1z1B1D0yax6c1S3P303?0U0-0V1o2W0X1=2{0F831Ldodqds2X0K140.2f041x0:0j0,0YdK246W1;0.0d7RdgbA0.0#0Y0U140f240r0y0H2l0g2A0*2h721T1O040w0e0y0Z001*2W0y2Z0ed{0e0u4B2W0j2Ld~242$dOdNdLd~0XdK0ddSdU1C2G0Xdg0)1Q7Wd00;1WdAdr0gdtdv6Sdy1OeudCduc5dFdH0N3qeadLecdP24e06VefdP0L0yb!epd10N240:3_0:0Ld^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0d0X0{dg0edg0{3y1d2z0@0X2$0Z0)0y0w6 0y1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10k0Y0vd~2pf0dMf40g0{flfn0{2Zfe0udZ1I2X2lf20y230y0Of,0~0yf40eg30=0{f3ar0Ygd0Z0.g20X7RdX0,f80OeZe#e%6{4Zfk2pfm1+1-0Pfq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0R9qgj2o0Ydxe{0y0,0i0:0#0=0Y0|0?0.e?0^gaeOgle=f80E1p3Y0F0?f,2Vg2dh0=0L0ibA0g6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0Z1ogjf|2p0-0Zg69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0yg?1md~0#2o10dMg23q0f3_h/gkgmgoeWd=0Cf.h40|0 fc3igsg3ePhreRe-eUcteT2z0y1maq0Z2pgjg70~0Y1+bUe8g2e*0gh60Yimh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0#b|iZh.ic2R220Ge72|d_242Tb|iciye!f+g}1p0Q1/1;0gh.gdiZgf0{0g00h(jMf_h70_iChbh6f80T0de^g{h-0y0s0XiX1=0Uimd}1eew0Re%0#e8j!dT0Jf60y0F0eeh0@iZf?jJjD0ejF24b|dZd}0U0Rg_eTf1e7g_g}0i1y0Rg38~d;dn5Cdpevexhf0i1skz2MdzkEdBewdDeG2M0Ekx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0O1oh%g30s1D2V1o6P696K3/6ec/cDb(7i0m3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0u6$020u8/ltlvlu1vbqaTi|jggLg,6T9!0)7Uj6gK0$0$fY5$0W0n48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0ol^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0:5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0-ig261yf3m!kp0Um%k4kcggiWg7h;2Ln37Ymjl80K9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040b0)0I0b0b0l0B0%0B0t0l0m5!0%0b0,0D0m0W4~lT3fjnc;1S5}0cerp4677bp50=g90Z04.

Évaluations restantes : 5/5

.1280138/olvnRxhO432;kw:S7g,I) N=6D+Efèà9b-u_LCyPp]Tam0irs[é*5q.î1edt(c050-0,0.0U0X0e0Z0y0:0e0U0Z0Z0A010.0X0R010406050Z0L0V0V0U0Y0P040s0d0e0L140d0g0y020U0V0R0o0y0h0,1e0Y0(0L0,0Z050c1b1d1f1h190R04051M1F1P0c1M190-0X0f0|0~10120~0g0u0L0U0u0,0K0R0P0.0j1o0y0j0X0u0j0e1^0j0.17050@0J0e0,1Y0 11011@1_1{1_0.21231 0.0Y1N1:0|1k0Z0R0U0g120n01251!010F0_0,0g1s0,1 2n2p2u272x232A0V2C040a0y0Q0Y0d0R0d0Z0X1n1p0=2l0Y0Y0,0:2X1F2E0g1N0c1:2-2h2j2i200-2G1#0X0g2z2U1 1V1X0}262`2|0g0d301 0R2$1N2+2-3d1a2o1p322v360Y1e0e1 0U1?2$0F12030M0M0:370,1{350d0K0l0K0+170y0+1F0U3e3h183g2F3j273l3n3p3r0,3t013v3x3z3B2}3E0K2s040y0n3L3N2p3P2+2_013U0U3o1N3q0j3s3u3w3y0=3(363*0m3I0m3:2*3O193@3S123`3|053~403!423%2{3)3F0l3I0l4b1G4d3Q3i1Z3T0d3m3{3W3 3Y413$444q463F0%3I0%4w3d4e3h3^4i4G4m3#433A4M3D3F0B3I0B4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0t3I0t4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0b3I0b512,534A33564E4j4l4I4n4K4$5e0K0I3I0I5j3?4V4g5o4?4k4^4J4#454(3G0W170+0W5B5l4W575q5I5t5K4%3*0+3H045$5S4z5U5p4Y5s4`5d4r3G3,0+3/0c3M4c3=1Q3b1F302:0-2j2^5E4#2 1W1N3a0,3c3O5|2,054#6d2F0X0-123w2+5#3W6l6n5u5L6q0y2K0,6t5Z5w5%4b4/5n0p170=0F6f6j5m2v0q3I6L5+5E0g0F172{1V0:0,6R6F2v16040/6#5D550g172e0,0U0L6+545n6(0v6L0y6S6-170:0X226!4x5}6$276(0x0r6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0y7B6~5n6.040=0J1m6|7D2v0d170A7K77120V0X175R7e3P7X5+7o0M6p3F484@7#6B5=487t2L7v5;4N0K7)3:7B7C7R3_172x0g7Q6,5n7N047P7X6}7|0g0J172J6@6N78176*7Z896/0U736=8e3^79816^7M170K8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040q1@238x4W6I0,7I0.8(5E84020e0.0o863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0,6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840D8.6 047 8 558r9N9J9z170c0c9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0X6K9Y8{4h70728%a69E8:8=0o9(3k8l8n9w9Ia79F170!9V7E179t0X9var6%170S929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0KaI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0K5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0.0L0Y80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0Z74bF8q17aB4ybubH0g5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0p0:170z1oc19Cb60:5%030y0s0X0y1=0g003q0Yav1p2h0d0L0f0#bE6e0c6i5~6c60691F0.63de2?2.8m232-611L6M3^2$0V0M0F0U0p0,0M0j7)1x1z1B1D0yc55}1S3P303^0U0-0V1o2W0X1=2{0F841LdLdNdP2X0K140.2f041x0:0j0,0Yd+246Y1;0.0d7TdD0y2W0#0Y0U140f240r0y0H2l0g2A0*2h741T1O040w0e0y0Zc|0u2W0y2Z0ec|0e0u4D2W0j2Lel242$d/d.d,el0Xd+0dd?d^1C2G0XdD0)1Q7Ydn0;1WdXdO0gdQdS6UdV1OeRdZdRc9d$d(0Nc}2%d,ezd:24en6XeCd:0L0yb(eMdo0N240:3{0:0Lefem00e;6Zele@b(e^d|2W24d?1m3Y0d0X0{dD0edD0{3y1d2z0@0X2$0Z0)0y0w71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe_cu8u85bg9Gax9K8+9Mc$cWcCfV9r9Ubu90170xcs9#9%f+a.049,d76ieLdIdo0k0Y0vel2pfnd-fr0g0{fIfK0{2ZfB0ud}1I2X2lfp0y230y0Og30~0yfr0egn0=0{fqav0Ygx0Z0.gm0X7T0.0#0,fv0Oe}e f16}4#fH2pfJ1+1-0PfN2a1|1~dpbmcwbyf=fXf^ao6)f!a87Gf$8-g+f*f(an7Ff-c2f/04f;g?f?cD8Af{dH6i0y0R9vgD2o0YdUfi0y0,0i0:0#0=0Y0|0?0.fd0^gue/gFfcfv0E1p3Y0F0?g32VgmdE0=0L0id`0g6YdEfF2Z5EfI1)gUfM291`gZfRg_cqf%f|3z3-0?gPfGhOgShQfLgWhTfPg!cpaXc#h!0=3-0Z1ogDgg2p0-0Zgq9vhlh{glhMe}55hPfKgVgXhU2chW9E7F9Lg=g^ad179Qg+g`aY3fd8h#h7h9el0#2o10d-gm3q0f3{i3gEgGgJe`ec0Cg5hm0|0 fziP0ef0gne:hJe=f7e^bx9vhf1p1mbx0Z2pgDgr0~0Y1+bZevgmf40gho0YiEhrdFh(hNi9h+ibhSfOhVg#b%i#cy3-b6ctilbvijg)iojeg}9HbAfS8}h@bkjca,iphYikjman9XjjcBh1g+cEh46gith_f~eb1MiMg9hDiP0{3a0#c0i_i2h72R220Geu2|eg242Tc0h7iQe~g2i%2P1/1;0gi2gxi_gz0{c{h|j)gdhp0_iVhthofv0Td2hohdi1c?c^en1=0UiEek1eeT0Rf10#evj_d@0Jft0y0F0eeE0@i_gaj$jW0ejY24c0d}ek0U0Rhbe@92ebdK5EdMeSeUhx0i1s0Rd(dWkMdYeTd!e%2M0E0i1ykTeadJeQh*1%h,gV3y1ph/j6b62I2z2B170Qj/1=0O1oh{gn0s1D2V1o6R6b6M3;6gd996b,7k0%3Gb/cR4|lh3Hb?bM46lm2t5a5Jce0Klrb`b60u6(020u8?lClElD1vg.7}g:crh0g*jz9)6Vf`0)7WlPfW0$0$h25P0W0n4acGc7a?99lhcKd`cMlvl,chb:3)l;5X5:b1lw3+7y5{7|lA17lF0om3m36}f.9Sg{9C7{f)7OcDlR0nlTg)lXlZ5(l#l%lV27g@c.7|cE3Kl(c2c8l|7^cLl?lq7@l=lkl@mEl_cjmH7^7zlzlBlHm5lHm7g|9SjglNjimsjnh?6|cA5nc:17c=0-iy261yfqi?e~2o71gHd676aEl*c9lh8S7nl/aLl|4tlocNn3ls4ZmKmDm mNm084dTm_7fm{lfl+lwljna3Dlh9gcQnol|9glt5Yl:nmlym0mPlGnDlIm86_8hlJiig;jhbgiqjpnijxf:g)f@mpf_jE7Ac/c;ixizc02Li_m;kF0Um@kkksgAi?gri52Lnhdpmylh9~mBmGmD4*n5nyo0nwl`6vn{l~j75neq6W6Un^7!m|l|aSn}ntlhaNnslpnpaRn85/okoqnAcWm104mRnEmTjwihjunMg+fZnGaim#lN8wjtlLhZm`nRg~nTmlnX94oCl.nkm}a}bLn6lh5go1n2o(or5bool|b3ndow840b0)0I0b0b0l0B0%0B0t0l0m5$0%0b0,0D0m0W50mwh^db1S5 0ceOph697dpi0=gt0Z04.

Quelle est la complexité d'un algorithme de dichotomie ? réfléchir avant de cliquer 😊

💚 A retenir : L’algorithme de dichotomie a une complexité logarithmique de l'ordre de $\log(n)$ pour une liste de taille $n$.

II. Le tri par sélection⚓︎

Quel est le principe du tri par sélection ? réfléchir avant de cliquer 😊

Pour un tableau tab de taille n

pour i allant de 0 à n-2
pos ← position du minimum dans tab à partir du rang 
si pos ≠  i :
    échanger tab[i] et tab[pos]

La fonction tri_selection

Compléter la fonction tri_selection prenant en argument un tableau et le triant en place à l'aide du tri par sélection.

Version sans code à trousVersion avec code à trous

Évaluations restantes : 5/5

.128013/oblvn-u_yhPp34]2;amkw:S7ig,rs) [5j=6+1edtf(c050P0O0Q0t0A0e0E0G0T0e0t0E0E0K010Q0A0n010406050E0i0u0u0t0D0k040y0c0e0i0.0c0g050b0^0`0|0~0?0n04051e171h0b1e0?0P0A0f0$0(0*0,0(0g0B0i0t0B0O0h0n0k0Q0l150G0l0A0B0l0e1J0l0Q0;050X0d0e0O1q0)0+011I1K1M1K0Q1S1U1Q0Q0D1f1E0$110E0n0t0g0,0r011W1s010R0Z0O0g0t0u0O1Q1=1@1|1Y1 1U22240;0a0G0m0D0c0n0c0E0A140g0G0V1:0D0D0O0T2p17270g1f0b1E2C1,1.1-1R0P291t0A0g212m1Q1n1p0%1X2M2O0g0c2S1Q0n2v1f2A2C2)0@1?2q2U1}2Y0D0{0e1Q0t1H2v0R0,030j0j0T2Z0O1M2X0c0h0z0h0N0;0N170t2*2-0=2,282/1Y2;2?2^2`0O2|012~3032342P370h1`040r3d3f1@3h2A2L013m0t2@1f2_0l2{2}2 310V3w2Y3y0o0;0o3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380p0;0p3#183%3i2.1r3l0c2=3L3o3P3q3R3u3U3@3W380I0;0I3}2)3(2-3I3,473:3t3T334d36380L0;0L4j3 3)423+443n3N3p3r4r3?353y0z0;0z4A3F1i2%172S2F0P1.2K3*014s2R1o1f2$0O2(3g3$4S4s4-280A0P0,2 2A3y3a4H4@4_4b4t4M383a0G2d0O504s3V4v391Q0b3e403I0v0;0V0R4/2B5h4#0w0;0G5n4=412V3J0R0;1,0A0j0E332w2y3~4S4C5x0:040S5u5p4D3J5A0t1T0O0t0i5P5K1}5M0F0x5u0?5I5o3H4 014`2-3y3A3.0G5.3=4c533z1{57594L3^5}2C3e0G665t5!1Y5j040R445u684m4#0g0;0A6f5Q5x0c5r042N6m693+0d0;0D1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0F6t6C6o0;0h6%6N5x0u0A3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0j6/0g6l6G6g6-1}0c0;0K6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0h7J3D7i7j6S6b6d0D7y4n0;0J7%4#6p6k167r7k6v6x6z0O6{4#6E7_5R6j7B7:6S7v040M7+5R6/6;7D6(6@0C855x0g6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0g3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0A5m808a7A6V8r8m3I5M0H8s2:7)8,8k0;0q8d7u0;020e0Q0s8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0q5(8w6{8A4{4w3o8A7d5|4x8K7R8N9l648Q8S9x7;6T5C7o9b3g8T3I827x8Z936T7*9h8(9j70379m7F9o624O9r8G7M7T4O9v9y6S7~8$6X9c8)0;8+8(6i6k96019e8c9J8U9)8 6W9?959:7}7m9C9 8;8}0,9Ha76T9*a5049/9,9;98a4a18t040q9_2)9Fahacak6@af4.9(9=at8:am7C2+0b4;4T4,4V4)170Q4YaK2I2D9}2C4W5*0V0X0Z0E04.

Évaluations restantes : 5/5

.1280138/oblvn-u_yhPp34]2;amkw:S7ig,rs) [é5j=6+1edtf(c050R0Q0S0u0B0f0F0H0V0f0u0F0F0M010S0B0o010406050F0j0v0v0u0E0l040z0d0f0j0:0d0h050c0`0|0~100^0o04051g191j0c1g0^0R0B0g0(0*0,0.0*0h0C0j0u0C0Q0i0o0l0S0m170H0m0B0C0m0f1L0m0S0?050Z0e0f0Q1s0+0-011K1M1O1M0S1U1W1S0S0E1h1G0(130F0o0u0h0.0s011Y1u010T0#0Q0h0u0v0Q1S1@1_1~1!211W24260?0a0H0n0E0d0o0d0F0B160h0H0X1=0E0E0Q0V2r19290h1h0c1G2E1.1:1/1T0R2b1v0B0h232o1S1p1r0)1Z2O2Q0h0d2U1S0o2x1h2C2E2+0_1^2s2W1 2!0E0}0f1S0u1J2x0T0.030k0k0V2#0Q1O2Z0d0i0b0i0P0?0P190u2,2/0@2.2a2;1!2?2^2`2|0Q2~01303234362R390i1|040s3f3h1_3j2C2N013o0u2_1h2{0m2}2 31330X3y2!3A0p0?0p3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0q0?0q3%1a3)3k2:1t3n0d2@3N3q3R3s3T3w3W3_3Y3a0K0?0K3 2+3*2/3K3.493=3v3V354f383a0N0?0N4l413+443-463p3P3r3t4t3^373A0A0?0A4C3H1k2)192U2H0R1:2M3,014u2T1q1h2(0Q2*3i3(4U4u4/2a0B0R0.312C3A3c4J4_4{4d4v4O3a3c0H2f0Q524u3X4x3b1S0c3g423K0w0?0X0T4;2D5j4%0x0?0H5p4@432X3L0T0?1.0B0k0F352y2A404U4E5z0=040U5w5r4F3L5C0u1V0Q0u0j5R5M1 5O0G0y5w0^5K5q3J51014|2/3A3C3:0H5:3@4e553B1}595b4N3`5 2E3g0H685v5$1!5l040T465w6a4o4%0h0?0B6h5S5z0d5t042P6o6b3-0e0?0E1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0G6v6E6q0?0i6)6P5z0v0B3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0k6;0h6n6I6i6/1 0d0?0M6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0i7L3F7k7l6U6d6f0E7A4p0?0L7)4%6r6m187t7m6x6z6B0Q6}4%6G7{5T6l7D7=6U7x040O7-5T6;6?7F6*6_0D875z0h6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0h3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0B5o828c7C6X8t8o3K5O0I8u2=7+8.8m0?0r8f7w0?020f0S0t8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0r5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720i4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040r9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0V4 030H0J0V0m7_7E2-0c4?4V4.4X4+190S4!a!2K2Fa02E4Y5,0X0Z0#0F04.

Utiliser La fonction tri_selection

Exécuter le script suivant :

La liste de départ a été modifiée ...

C'est ce qu'on appelle un effet de bord.

La fonction a modifié "en place" la liste.

Résumé

Le plus souvent, on écrit une procédure (pas de return) pour le tri par selection.
C'est un tri "en place" qui modifie la liste elle-même.
👉 Vous devez mémoriser cette procédure.

Quel est la complexité d'un algorithme de tri par selection ? réfléchir avant de cliquer 😊

💚 A retenir : L’algorithme du tri par selection a une complexité quadratique de l'ordre de $n^2$ pour une liste de taille $n$.

III. Le tri par insertion⚓︎

Quel est le principe du tri par insertion ? réfléchir avant de cliquer 😊

Pour un tableau tab de taille n

pour i allant de 1 à n-1
    clef ← tab[i]
    insérer la clef au bon endroit dans tab

La fonction tri_insertion

Compléter la fonction tri_insertion prenant en argument un tableau et le triant en place à l'aide du tri par insertion.

Version sans code à trousVersion avec code à trous

Évaluations restantes : 5/5

.1280138/oblvn-u_yhOPp34]2;amkw:S07ig,rs) [5j=61edtfè(c050R0Q0S0v0D0f0H0J0W0f0v0H0H0N010S0D0p010406050H0j0w0w0v0G0l040A0d0f0j0;0d0h050c0{0}0 110_0p04051h1a1k0c1h0_0R0D0g0)0+0-0/0+0h0E0j0v0E0Q0i0p0l0S0m180J0m0D0E0m0f1M0m0S0@050!0e0f0Q1t0,0.011L1N1P1N0S1V1X1T0S0G1i1H0)140H0p0v0h0/0t011Z1v010T0$0Q0h0v0w0Q1T1^1`1 1#221X25270@0a0J0o0G0d0p0d0H0D170h0J0Y1?0G0G0Q0W2s1a2a0h1i0c1H2F1/1;1:1U0R2c1w0D0h242p1T1q1s0*1!2P2R0h0d2V1T0p2y1i2D2F2,0`1_2t2X202#0G0~0f1T0v1K2y0T0/030k0k0W2$0Q1P2!0d0i0P0B3a0@0P1a0v2-2:0^2/2b2=1#2@2_2{2}0Q2 01313335372S3a3c1}040t3g3i1`3k2D2O013p0v2`1i2|0m2~3032340Y3z2#3B0i0q0@0q3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0i0r0@0r3)1b3+3l2;1u3o0d2^3O3r3S3t3U3x3X3{3Z3}0L0@0L422,3,2:3L3:4c3@3w3W364i393}0O0@0O4o443-473/493q3Q3s3u4w3`383!0C0@0C4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0b0@0b4W2E1l2*1a2V2I0R1;2N3.014x2U1r1i2)0Q2+3j3*3I054x572b0D0R0/322D3!0P3r5f5h4g4y4-3c5l0J2g0Q5o4x3Y4A5s1T0c3h453L0x0@0Y0T594?4H2Y010y0@0J5L5d465O0h0T0@1/0D0k2Q0H0Q0G2B435a5N200?040V5T5F4 0h5Z0v1W0Q0v0j5?5.1#5:0I0z5T0_5,5M4r5n015i2:3!3D3=0J6b4+5q3|3C1~5v5x4Q6m0i6g5D040J6x5S610/5H040T495T6z4r5^0@0D6G5@4!0d5Q042Q6M6A3M0e0@0G1`1C606I4!5:5=685U3L0w0D3e6#4Z5O5:0F6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0I64666~6i5g6c0k5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0g3O0Q0j0G0k0v5$0h5(2y0G6^7H1#0d0@0N7W6 3o5`5|5~7h4 5:0K7,4!756L7a6U5:0s7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040M7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0y1L1X8m6J8k8W6O0@020E0S0u8Z5O6-0@0B8*206P0@1`0R8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0i8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0i4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0i4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0W5l04030J0n2t5%0U2yaL4?0c5c4@564_531a0S4|bn2L2G8{bk0c4`670Y0!0$0H04.

Évaluations restantes : 5/5

.1280138/oblvn-u_yhPp34]2;amkw:S70ig,rs) [5j=61edtf(c050Q0P0R0u0C0f0G0I0U0f0u0G0G0M010R0C0o010406050G0j0v0v0u0F0l040z0d0f0j0/0d0h050c0_0{0}0 0@0o04051f181i0c1f0@0Q0C0g0%0)0+0-0)0h0D0j0u0D0P0i0o0l0R0m160I0m0C0D0m0f1K0m0R0=050Y0e0f0P1r0*0,011J1L1N1L0R1T1V1R0R0F1g1F0%120G0o0u0h0-0s011X1t010S0!0P0h0u0v0P1R1?1^1}1Z201V23250=0a0I0n0F0d0o0d0G0C150h0I0W1;0F0F0P0U2q18280h1g0c1F2D1-1/1.1S0Q2a1u0C0h222n1R1o1q0(1Y2N2P0h0d2T1R0o2w1g2B2D2*0^1@2r2V1~2Z0F0|0f1R0u1I2w0S0-030k0k0U2!0P1N2Y0d0i0O0O380=0O180u2+2.0?2-292:1Z2=2@2_2{0P2}012 3133352Q383a1{040s3e3g1^3i2B2M013n0u2^1g2`0m2|2~30320W3x2Z3z0i0p0=0p3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390i0q0=0q3%193)3j2/1s3m0d2?3M3p3Q3r3S3v3V3_3X3{0K0=0K402*3*2.3J3.4a3=3u3U344g373{0N0=0N4m423+453-473o3O3q3s4u3^363Y0A0=0A4D3G4o3k4G3K4I494K4b4M3@4f4P3{0b0=0b4U2C1j2(182T2G0Q1/2L3,014v2S1p1g2%0P2)3h3(3G054v55290C0Q0-302B3Y0O3p5d5f4e4w4+3a5j0I2e0P5m4v3W4y5q1R0c3f433J0w0=0W0S574;4F2W010x0=0I5J5b445M0h0S0=1-0C0k2O0G0P0F2z41585L1~0;040T5R5D4}0h5X0u1U0P0u0j5;5,1Z5.0H0y5R0@5*5K4p5l015g2.3Y3B3:0I694)5o3`3A1|5t5v4O6k0i6e5B040I6v5Q5 0-5F040S475R6x4p5?0=0C6E5=4Y0d5O042O6K6y3K0e0=0F1^1A5~6G4Y5.5:665S3J0v0C3c6Z4X5M5.0E6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0H62646|6g5e6a0k5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0g3M0P0j0F0k0u5!0h5$2w0F6?7F1Z0d0=0M7U6}3m5^5`5|7f4}5.0J7*4Y736J786S5.0r7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040L7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0x1J1V8k6H8i8U6M0=020D0R0t8X5M6+0=0B8(1~6N0=1^0Q8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0i8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0i4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0i4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0c5a4=544@51180R4`b92J2E8_b60c4^650W0Y0!0G04.

Utiliser La fonction tri_insertion

Exécuter le script suivant :

La liste de départ a été modifiée ...

C'est ce qu'on appelle un effet de bord.

La fonction a modifié "en place" la liste.

Résumé

Le plus souvent, on écrit une procédure (pas de return) pour le tri par insertion.
C'est un tri "en place" qui modifie la liste elle-même.
👉 Vous devez mémoriser cette procédure.

Quel est la complexité d'un algorithme de tri par insertion ? réfléchir avant de cliquer 😊

💚 A retenir : L’algorithme du tri par insertion a une complexité quadratique de l'ordre de $n^2$ pour une liste de taille $n$.