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

.128013ràwc1Dkp[dé2^=:l,}78eFTRzS4-+]mhanuù9ê6s_ N(3t0voÀiè;qfb{/.OgyA5xILP)050k0v0U0H0Z0q0O0Q0e0q0H0O0O0o010U0Z0i010406050O0J0F0F0H0b0.040A0X0q0J190X0I0Q020H0F0i0#0Q0y0v1j0b0$0J0v0O050*1g1i1k1m1e0i04051R1K1U0*1R1e0k0Z0W11131517130I0-0J0H0-0v0C0i0.0U0G1t0Q0G0Z0-0G0q1}0G0U1c050|0(0q0v1%1416011|1~201~0U2628240U0b1S1^111p0O0i0H0I170m012a1)010%0~0v0I1x0v242s2u2z2c2C282F0F2H040a0Q0@0b0X0i0X0O0Z1s1u0`2q0b0b0v0e2$1K2J0I1S0*1^2=2m2o2n250k2L1*0Z0I2E2Z241!1$122b2 310I0X35240i2+1S2:2=3i1f2t1u372A3b0b1j0q240H1{2+0%17030P0P0e3c0v203a0X0C0V0C0f1c0Q0f1K0H3j3m1d3l2K3o2c3q3s3u3w0v3y013A3C3E3G323J0C2x040Q0m3Q3S2u3U2:2~013Z0H3t1S3v0G3x3z3B3D0`3-3b3/0T3N0T3^2/3T1e3|3X173 410543453)473,303.3K0B3N0B4g1L4i3V3n1(3Y0X3r403#443%463+494v4b3K0:3N0:4B3i4j3m3}4n4L4r3*483F4R3I3K0N3N0N4X4D4k4G4m4I3!423$3(4)4u3H3/0t3N0t4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0u3N0u562;584F385b4J4o4q4N4s4P4+5j0C0L3N0L5o3{4!4l5t4{4p4}4O4*4a4-3L0V1c0f0V5G5q4#5c5v5N5y5P4,3/0f3M045+5X4E5Z5u4%5x4 5i4w3L3;0f3@0*3R4h3`1V3g1K352^0k2o2}5J4*341#1S3f0v3h3T612;054*6i2K0Z0k173B2:5*3#6q6s5z5Q6v0Q2P0v6y5(5B5,4g4@5s0h1c0`0%6k6o5r2A0d3N6Q5:5J0I0%6N0Z0e1_0U0X0F0Z0v6W6K2A1b040S6.5I5a0I1c3b0F0(2+1J4C626/2c6;0r6Q0Q6X6_1c0e0Z276-716l73176;0^0p6Q1e7g6R0Q6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0Q7M795s6`040`0(1r777O2A0X1c0o7V7i016+1c5W7p7o3k3|7z0P6u3K4d4|7/6G5`4d7E2Q7G5_4S0C7?3^7M7N7$7Q2C0I7#6^5s7Y047!7p78860(1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0^8a8n7X1c0C8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040d1|288I4#6N0v7T0U8^5J8d020q0U0#8f3i8-8E8t04888O5J6;7m7+8O7/7;0C4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200v0J8~5a8d953T978J018p9c7a9a309H8c1c0D9U3p8`8|9Q8o8B9$8F040*0*9)2c8L5~4Y9h9n9j4/9m9t8Y0C4/8!9{9p9}7J8+9y858.2c8:0Z6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0j9.9B049D6,9G8r7$6;0E9f9=aE4!9i8T0C539`8$7H80539 aR7 5RaP9xa58,ad8:2+0U0J0b89aiau010h0e1c0x0b1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900-93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0O7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0w40c8b#0e5,030Q2!0Q1`0I003v2t102m0X0J0W0lcL6j0*6n636h656e1K0U68df2{2?0H7e2=661Q7q5J2+0F0P0%0H0h0v0P0G7?1C1E1G1I0Qce6l1X3U353}0H0k0F1t2#0Z1`300%8d1QdMdOdQ2$0C190U2k041C6%0v0bd,0Q2t0b0Q1!6%0X6)6+7f1Y1T040=0qc_c~0-2#d?000J1u400-4I2#0G2Q2L0ZdE0+0Q0?292j0v0H0Jd:0b0Z102Ed:1k1x0!2m290k0Xe51fd21,040X271}0H6)0Zds2E0U0Q0MeA0Q2m0Zd61LeG0-040+1V3U1R0Y110G0HdE7r0U0l0beMdS0I0rc{1uc8d?1D2u2(c`130Q0W409Fd=0eeQe?280Q1IeR0l0-f60Q0c0Qf36m3E04bhah6ndGe(1e0J0q3U2004c`d30Ze`1`2+0I0WeD290Z1i0l1!eM1DeQ786na@a_d9fo1Kfz1efzc`3be_110{0U29fq29fec_eDeR7mfwfy0ZfA0J0ie=aC2+fjfl3vf528a+f)0I2mfi0p7re1dv1re,d-d,d=0k2u10f3d;19eB2W2#eBeqenep0Q6?6n7Sge0o0Qbxeq0D3O1K6n8C0*fZ05fzdUf}f729fkf3g3f7g6g8fcga0~0QgdeRghghd?gkg1ew0bgo0Qfh0Jd/0kgtdl28gvgxfo880QgBgD0Q0CgGfW0`04gJgL0*f@7oh9hbd~0?3v0z1teB292+g(0G290S0q000l0e1keRfa29fnh6cxfs0{fSfogz8}h56h0^c_hlfN0Je5fk6%e.1He:e=e@1`gafB1u88e5d;0Q0HfIeOhEhA301v921AhGgHfoe`0e00f/e/fm6nf-h?h66Ch`0OeRd0g*0Iglemg_eo0Jej0,e|4IeR2(f30(d312f.eRfGh*hy6nc/0 7f6ne%dJ7odo0_1#dYdP0IdRdT6ZdW1TiEd!e^d$2#d)0R8vf 1j0;fL40e~eVd30b102(ilg=2870d}1R2V32i80Qe80Qhthve630d@fKiG19iYhz6hg~h3h=hI3=fgiYfkad1ked1jf+0;1c090S5V0n0L09gJ3ie`0Sf90Q1G0Zfdi4jt1.0I2}0F0Mef2m0!100-e?jA0^iyi-040gg+fc0ieOhk10hu0OfE0Kg,f-i2f/i63f0lc8g70vfE1u0b0l40etemd3i9d1i#i%29i)in102Y15ag1IjM3Uhefz0/eq6gd{d=6)a+j.h(i=1ui^g.fdfHeO1`2(jbes1^je0vjg04ji090%e?0e0)jk0L0s0)0m0sjn6Qh^i3eRfk1!f kq7$jcktfPkwji0:0Q09192Q10jk0ukK8rgKf_f!f_k9e~0JiW0!jEi#kg3vi?kkhwkn2W2%hykTkseekWjh0SkzkB0)kZk#fLdFk)kGkIk+96h_f/kPjTcv5skUl6jfl80mldk$lg0V0n0tlkd8gLk830c`f1hOf+0Q0+lNfYk.gMk:gtfG19k^j@kfe{khk}hukl0kh`l01`krjdl7kxl9kA0HkCkEli0n0)0T0V0skJjo9LlmjxlokRl)0Wko1u0fiyhdfxdp0/lHfDi710e82920i4hkeV0}0qfcl,kVlul/kElD3`e`evgv0i1qeul*1ul{i!a+101`0O0}eRf2hs0q0l2Qg7h,6hh j6jwi5j:j+0Uk5iA6eiA0{mp0O04.

Évaluations restantes : 5/5

.128013ràwc1Dkp[dé2^=:l,}78eFTRzS4-+]mhanuù9ê6s_ N(3t0voÀiè;qfb{/.OgyA5xILP)050k0v0U0H0Z0q0O0Q0e0q0H0O0O0o010U0Z0i010406050O0J0F0F0H0b0.040A0X0q0J190X0I0Q020H0F0i0#0Q0y0v1j0b0$0J0v0O050*1g1i1k1m1e0i04051R1K1U0*1R1e0k0Z0W11131517130I0-0J0H0-0v0C0i0.0U0G1t0Q0G0Z0-0G0q1}0G0U1c050|0(0q0v1%1416011|1~201~0U2628240U0b1S1^111p0O0i0H0I170m012a1)010%0~0v0I1x0v242s2u2z2c2C282F0F2H040a0Q0@0b0X0i0X0O0Z1s1u0`2q0b0b0v0e2$1K2J0I1S0*1^2=2m2o2n250k2L1*0Z0I2E2Z241!1$122b2 310I0X35240i2+1S2:2=3i1f2t1u372A3b0b1j0q240H1{2+0%17030P0P0e3c0v203a0X0C0f3J1c0Q0f1K0H3j3m1d3l2K3o2c3q3s3u3w0v3y013A3C3E3G323J0C2x040Q0m3P3R2u3T2:2~013Y0H3t1S3v0G3x3z3B3D0`3,3b3.0T3M0T3@2/3S1e3{3W173~400542443(463+303-3K0B3M0B4f1L4h3U3n1(3X0X3r3 3!433$453*484u4a3K0:3M0:4A3i4i3m3|4m4K4q3)473F4Q3I3K0N3M0N4W4C4j4F4l4H3Z413#3%4(4t3H3.0t3M0t4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0u3M0u552;574E385a4I4n4p4M4r4O4*5i0C0L3M0L5n3`4Z4k5s4`4o4|4N4)494,3J0V1c0f0V5F5p4!5b5u5M5x5O4+3.0f0f5T3O0*3Q4g564D5Y5t4$5w4~5h4v3J3:0f3?5.3^2;1V3g1K352^0k2o2}5I4)341#1S3f0v3h3S5:634)6j2K0Z0k173B2:5)3!6q6s5y5P6v0Q2P0v6y5%5A5+2=5/4?5r0h1c0`0%6l6o5q2A0d3M6R5=5I0I0%6O0Z0e1_0U0X0F0Z0v6X6L2A1b040S6/5H590I1c3b0F0(2+1J4B3_6Y596=0r6R0Q745r6{040e0Z276.72636:2c6=0^0p6R1e7i6S0Q6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610Q7N797k4l6O0v0(1r787a2A0X1c0o7W7Q016,1c5V7r7q3k3{7B0P6u3K4c4{7:6G5|4c7G2Q7I5{4R0C7@3@7O7P6_7b1c2C0I7$877Y7!8c587b0(1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0^8g8z177Z040C8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040d1|288J6Z7S7U0U8^598G020q0U0#7#7r868n8t048a8P5I6=7o7,8P7:7=0C4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200v0J8}5r8G943i968E016=8q7.8d989a958.018G0D9F3p8`7V8r7%7m9b8~1c0*0*9)5r8L608O9$4Z9h8U0C4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0Z6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0j9.9Z049B6-9E9?au9M1c0E9e9=at1u9^2u518W9}9o0C528#aR5A528+a7a79U8:2+0U0J0b8bad9Q8/0e1c0x0b1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0-92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0O7hb?9c1cbF5;bHaN0I5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0Z5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0ha:040w3 c8cN3k0*6n646i666f1K0U69c~2{2?0H7g2=671Q7s5I2+0F0P0%0H0h0v0P0G7@1C1E1G1I0Qcd631X3T353|0H0k0F1t2#0Z1`300%8G1Qdvdxdz2$0C190U2k041C6(0v0bdR0Q2t0b0Q1!6(0X6*6,7h1Y1T040=0q0Q0O001/2#dY000J1u3 0-4H2#0G2Q2L0Zdn0+0Q0?292j0v0H0JdV0b0Z102EdV1k1x0!2m290k0Xd=1f2m1t0-040X271}0H6*0Zdb2E0U0Q0Mek0Q2m0Z0l2/eq1,040+1V3T1R0Y110G0Hdn7t0U0l0bexdB0I0r0Q1`c8dY1D2u2(2!0Q130Q0W3 9DdX0eeBe!280Q1IeC0l0-e^0Q0ce;3v056nbh7h6ndpeP1e0J0q3T2004e:0X0J0Ze(1`2+0I0Wen290Z1i0l1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0U29fbe 0OeC0OeneC7ofhfj0Zfl0J0ieZaC2+f5f7e?e^a*fR0I2mf40p7td-de1reTdSdRdX0k2u10e=dW19el2W2#eleae7e90Q6@6nbZg00o0Qb+ea0D3N1K6n8C0*fL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0Qf eCg3g3dYg6f;g96-0Qf30JdU0kgfd428ghgjfJ8a0Qgngp0Q0CgsfI0`04gvgx0*f%7qg|g~d*0?3v0z1tel292+gS0G290S0q000l0e1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0^d.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0Q0HfuezfEhn1u9092e,b!hx04e(0e00f00QeWe=ht6ifbhpg_6Ch,fXeg10g50Ig7e6g)e80Je30,1ufZ0beC2(e=0(fn12290{0QfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0IdAdC6!dF1TixdJe$dL2#dO0Rbr291j0;fx3 e,eGfn0bh}29idg#2871d)1R2V32h 0Qd^0Qhghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0;1c090S5U0n0L09gv3ie(0Se{h.fofWeC2m0!100-e!0I0k0^iri$040ggVe~0iezh710hh0Ofq0Kf;fV0Ih`eC2t103f0lc8f_0vfq1u0b0l3 ede6fni0106*a*iW0QiYifjS2Z2!7g0Ojy3Th1fk0/ea6hd%dXj,0bjYhTi+1ui.i9e ftez1`2(j4ec1^j70vj904jb090%e!0e0)jd0L0s0)0m0sjg6Rh*jPf:1!f/kf7%j5kifBkljb0:0Q09192Q10jd0ukz8rgwf)fMf)j~e,0JiP0!d k3k53vi,k9hjkc2W2%hlkHkhd~kKja0Skokq0)kNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0ml1kQl40V0n0tl86kkXf(040/30e:e/hD290+lC1Kgxj}gffs19k)j(a*k,k7i-hhka0kh,k;1`kgj6k{kmk}kp0Hkrktl60n0)0T0V0skyjhamlah{lcjFd?2E0Wkd1u0firh0fid8lwh fpgUi*d^2920fXh7eG0}0qe~lWkJlilZktlr3_e(efgh0i1qeelU1ul,iTj-e)i70}fY0Ze;hf0q0l2Qf_hXg_h?h(joebjUeBj`it6fit0{me0O04.

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

.128013ràwc1pk[d*é2=:l,E7e8TRS4-+]mhîanu96s _N(3tv0oiè;qfb/.Ogy5xIPL)CD050j0t0Q0F0U0p0K0L0e0p0F0K0K0n010Q0U0g010406050K0H0C0C0F0b0(040x0T0p0H140T0G0L020F0C0g0W0L0w0t1e0b0X0H0t0K050!1b1d1f1h190g04051M1F1P0!1M190j0U0R0|0~10120~0G0%0H0F0%0t0z0g0(0Q0D1o0L0D0U0%0D0p1^0D0Q17050@0Z0p0t1Y0 11011@1_1{1_0Q21231 0Q0b1N1:0|1k0K0g0F0G120m01251!010Y0_0t0G1s0t1 2n2p2u272x232A0C2C040a0L0,0b0T0g0T0K0U1n1p0=2l0b0b0t0e2X1F2E0G1N0!1:2-2h2j2i200j2G1#0U0G2z2U1 1V1X0}262`2|0G0T301 0g2$1N2+2-3d1a2o1p322v360b1e0p1 0F1?2$0Y12030M0M0e370t1{350T0z0m0z0f170L0f1F0F3e3h183g2F3j273l3n3p3r0t3t013v3x3z3B2}3E3E3I0m3L3N2p3P2+2_013U0F3o1N3q0D3s3u3w3y0=3(363*0P3I0P3.2*3O193=3S123^3`053|3~3!403%2{3)3F0y3I0y491G4b3Q3i1Z3T0T3m3_3W3}3Y3 3$424o443F0)3I0)4u3d4c3h3?4g4E4k3#413A4K3D3F0J3I0J4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0s3I0s4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0u3I0u4 2,514y33544C4h4j4G4l4I4!5c0z0I3I0I5h3;4T4e5m4;4i4?4H4Z434$3G0S170f0S5z5j4U555o5G5r5I4#3*0f3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0!3M4a3:1Q3b1F302:0j2j2^5C4Z2 1W1N3a0t3c3O5`2,054Z6b2F0U0j123w2+5Z3W6j6l5s5J6o0L2K0t6r5X5u5#494-5l0h170=0Y6d6h5k2v0d3I6J5)5C0G0Y172{1V0e0t6P6D2v16040O6Z5B530G172e0t0F0H6)525l6$0q6J0L6Q6+170e0U226Y4v5{6!276$0.0o6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040L7z6{754f6G0t0Z1m6`6|5l0T170n7I7C010C0U175P7c3P7V5)7m0M6n3F464=7Z6z5:467r2L7t5/4L0z7%3.7A7B6*5l6,042x0G7O7`2v7L047N7V7_6?3k0Z172J6=6L76176(7X7P7|6.6:8d3?77808827830z8q8e127R5N7a8n7Z7#0z4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040d1@238v4U7E7G0Q8#5C83020p0Q0W853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0t6;869l12838;3O8?8o8g8{6}040=8(8*53830A9G7{8_2{9B6@170.9K82170!0!9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0U6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0i9O3k9n0_0U9qan8f040B8~9$8i4T8C9*0z4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0z5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0F718mazaX01alataea$asbm8@6$aw8Abu0LaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0Q0H0b7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0K72aibn8}byb~1pbB0G5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0f7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010h0e170N1ob}4w7X0!6g5|6a5~671F0Q61c@2?2.bj232-5 1L6K3?2$0C0M0Y0F0h0t0M0D7%1x1z1B1D0Lax6c1S3P303?0F0j0C1o2W0U1=2{0Y831Ldodqds2X0z140Q2f041x0e0D0t0bdK246W1;0Q0T7RdgbA0Q0l0b0F140R240o0L0c2l0G2A0E2h721T1O040+0p0L0K001*2W0L2Z0pd{0p0%4B2W0D2Ld~242$dOdNdLd~0UdK0TdSdU1C2G0Udg0#1Q7Wd00;1WdAdr0Gdtdv6Sdy1OeudCduc5dFdH0-3qeadLecdP24e06VefdP0H0Lb!epd10-240e3_0e0Hd^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0T0U0{dg0pdg0{3y1d2z0@0U2$0K0#0L0+6 0L1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10$0b0qd~2pf0dMf40G0{flfn0{2Zfe0%dZ1I2X2lf20L230L0/f,0~0Lf40pg30=0{f3ar0bgd0K0Qg20U7RdX0tf80/eZe#e%6{4Zfk2pfm1+1-0(fq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0g9qgj2o0bdxe{0L0t0*0e0l0=0b0|0?0Qe?0^gaeOgle=f80r1p3Y0Y0?f,2Vg2dh0=0H0*bA0G6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0K1ogjf|2p0j0Kg69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0Lg?1md~0l2o10dMg23q0R3_h/gkgmgoeWd=0:f.h40|0 fc3igsg3ePhreRe-eUcteT2z0L1maq0K2pgjg70~0b1+bUe8g2e*0Gh60bimh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0lb|iZh.ic2R220Ve72|d_242Tb|iciye!f+g}1p0,1/1;0Gh.gdiZgf0{0G00h(jMf_h70_iChbh6f80v0Te^g{h-0L0x0UiX1=0Fimd}1eew0ge%0le8j!dT0Zf60L0Y0peh0@iZf?jJjD0pjF24b|dZd}0F0gg_eTf1e7g_g}0*1y0gg38~d;dn5Cdpevexhf0*1skz2MdzkEdBewdDeG2M0rkx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0/1oh%g30x1D2V1o6P696K3/6ec/cDb(7i0P3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0%6$020%8/ltlvlu1vbqaTi|jggLg,6T9!0#7Uj6gK0k0kfY5$0S0m48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0Wl^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0e5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0jig261yf3m!kp0Fm%k4kcggiWg7h;2Ln37Ymjl80z9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040u0#0I0u0u0y0J0)0J0s0y0P5!0)0u0t0A0P0S4~lT3fjnc;1S5}0!erp4677bp50=g90K04.

Évaluations restantes : 5/5

.128013ràwc1pk[d*é2=:l,E7e8TRS4-+]mhîanu96s _N(3tv0oiè;qfb/.Ogy5xIPL)CD050j0t0Q0F0U0p0K0L0e0p0F0K0K0n010Q0U0g010406050K0H0C0C0F0b0(040x0T0p0H140T0G0L020F0C0g0W0L0w0t1e0b0X0H0t0K050!1b1d1f1h190g04051M1F1P0!1M190j0U0R0|0~10120~0G0%0H0F0%0t0z0g0(0Q0D1o0L0D0U0%0D0p1^0D0Q17050@0Z0p0t1Y0 11011@1_1{1_0Q21231 0Q0b1N1:0|1k0K0g0F0G120m01251!010Y0_0t0G1s0t1 2n2p2u272x232A0C2C040a0L0,0b0T0g0T0K0U1n1p0=2l0b0b0t0e2X1F2E0G1N0!1:2-2h2j2i200j2G1#0U0G2z2U1 1V1X0}262`2|0G0T301 0g2$1N2+2-3d1a2o1p322v360b1e0p1 0F1?2$0Y12030M0M0e370t1{350T0z0y0z0f170L0f1F0F3e3h183g2F3j273l3n3p3r0t3t013v3x3z3B2}3E0z2s040L0m3L3N2p3P2+2_013U0F3o1N3q0D3s3u3w3y0=3(363*0P3I0P3:2*3O193@3S123`3|053~403!423%2{3)3F0y3I0y4b1G4d3Q3i1Z3T0T3m3{3W3 3Y413$444q463F0)3I0)4w3d4e3h3^4i4G4m3#433A4M3D3F0J3I0J4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0s3I0s4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0u3I0u512,534A33564E4j4l4I4n4K4$5e0z0I3I0I5j3?4V4g5o4?4k4^4J4#454(3G0S170f0S5B5l4W575q5I5t5K4%3*0f3H045$5S4z5U5p4Y5s4`5d4r3G3,0f3/0!3M4c3=1Q3b1F302:0j2j2^5E4#2 1W1N3a0t3c3O5|2,054#6d2F0U0j123w2+5#3W6l6n5u5L6q0L2K0t6t5Z5w5%4b4/5n0h170=0Y6f6j5m2v0d3I6L5+5E0G0Y172{1V0e0t6R6F2v16040O6#5D550G172e0t0F0H6+545n6(0q6L0L6S6-170e0U226!4x5}6$276(0.0o6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0L7B6~5n6.040=0Z1m6|7D2v0T170n7K77120C0U175R7e3P7X5+7o0M6p3F484@7#6B5=487t2L7v5;4N0z7)3:7B7C7R3_172x0G7Q6,5n7N047P7X6}7|0G0Z172J6@6N78176*7Z896/0F736=8e3^79816^7M170z8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040d1@238x4W6I0t7I0Q8(5E84020p0Q0W863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0t6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840A8.6 047 8 558r9N9J9z170!0!9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0U6K9Y8{4h70728%a69E8:8=0W9(3k8l8n9w9Ia79F170i9V7E179t0U9var6%170B929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0zaI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0z5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0Q0H0b80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0K74bF8q17aB4ybubH0G5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0h0e170N1oc19Cb60e5%030L0x0U0L1=0G003q0bav1p2h0T0H0R0lbE6e0!6i5~6c60691F0Q63de2?2.8m232-611L6M3^2$0C0M0Y0F0h0t0M0D7)1x1z1B1D0Lc55}1S3P303^0F0j0C1o2W0U1=2{0Y841LdLdNdP2X0z140Q2f041x0e0D0t0bd+246Y1;0Q0T7TdD0L2W0l0b0F140R240o0L0c2l0G2A0E2h741T1O040+0p0L0Kc|0%2W0L2Z0pc|0p0%4D2W0D2Lel242$d/d.d,el0Ud+0Td?d^1C2G0UdD0#1Q7Ydn0;1WdXdO0GdQdS6UdV1OeRdZdRc9d$d(0-c}2%d,ezd:24en6XeCd:0H0Lb(eMdo0-240e3{0e0Hefem00e;6Zele@b(e^d|2W24d?1m3Y0T0U0{dD0pdD0{3y1d2z0@0U2$0K0#0L0+71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe_cu8u85bg9Gax9K8+9Mc$cWcCfV9r9Ubu90170.cs9#9%f+a.049,d76ieLdIdo0$0b0qel2pfnd-fr0G0{fIfK0{2ZfB0%d}1I2X2lfp0L230L0/g30~0Lfr0pgn0=0{fqav0bgx0K0Qgm0U7T0Q0l0tfv0/e}e f16}4#fH2pfJ1+1-0(fN2a1|1~dpbmcwbyf=fXf^ao6)f!a87Gf$8-g+f*f(an7Ff-c2f/04f;g?f?cD8Af{dH6i0L0g9vgD2o0bdUfi0L0t0*0e0l0=0b0|0?0Qfd0^gue/gFfcfv0r1p3Y0Y0?g32VgmdE0=0H0*d`0G6YdEfF2Z5EfI1)gUfM291`gZfRg_cqf%f|3z3-0?gPfGhOgShQfLgWhTfPg!cpaXc#h!0=3-0K1ogDgg2p0j0Kgq9vhlh{glhMe}55hPfKgVgXhU2chW9E7F9Lg=g^ad179Qg+g`aY3fd8h#h7h9el0l2o10d-gm3q0R3{i3gEgGgJe`ec0:g5hm0|0 fziP0pf0gne:hJe=f7e^bx9vhf1p1mbx0K2pgDgr0~0b1+bZevgmf40Gho0biEhrdFh(hNi9h+ibhSfOhVg#b%i#cy3-b6ctilbvijg)iojeg}9HbAfS8}h@bkjca,iphYikjman9XjjcBh1g+cEh46gith_f~eb1MiMg9hDiP0{3a0lc0i_i2h72R220Veu2|eg242Tc0h7iQe~g2i%2P1/1;0Gi2gxi_gz0{c{h|j)gdhp0_iVhthofv0vd2hohdi1c?c^en1=0FiEek1eeT0gf10levj_d@0Zft0L0Y0peE0@i_gaj$jW0pjY24c0d}ek0F0ghbe@92ebdK5EdMeSeUhx0*1s0gd(dWkMdYeTd!e%2M0r0*1ykTeadJeQh*1%h,gV3y1ph/j6b62I2z2B170,j/1=0/1oh{gn0x1D2V1o6R6b6M3;6gd996b,7k0)3Gb/cR4|lh3Hb?bM46lm2t5a5Jce0zlrb`b60%6(020%8?lClElD1vg.7}g:crh0g*jz9)6Vf`0#7WlPfW0k0kh25P0S0m4acGc7a?99lhcKd`cMlvl,chb:3)l;5X5:b1lw3+7y5{7|lA17lF0Wm3m36}f.9Sg{9C7{f)7OcDlR0mlTg)lXlZ5(l#l%lV27g@c.7|cE3Kl(c2c8l|7^cLl?lq7@l=lkl@mEl_cjmH7^7zlzlBlHm5lHm7g|9SjglNjimsjnh?6|cA5nc:17c=0jiy261yfqi?e~2o71gHd676aEl*c9lh8S7nl/aLl|4tlocNn3ls4ZmKmDm mNm084dTm_7fm{lfl+lwljna3Dlh9gcQnol|9glt5Yl:nmlym0mPlGnDlIm86_8hlJiig;jhbgiqjpnijxf:g)f@mpf_jE7Ac/c;ixizc02Li_m;kF0Fm@kkksgAi?gri52Lnhdpmylh9~mBmGmD4*n5nyo0nwl`6vn{l~j75neq6W6Un^7!m|l|aSn}ntlhaNnslpnpaRn85/okoqnAcWm104mRnEmTjwihjunMg+fZnGaim#lN8wjtlLhZm`nRg~nTmlnX94oCl.nkm}a}bLn6lh5go1n2o(or5bool|b3ndow840u0#0I0u0u0y0J0)0J0s0y0P5$0)0u0t0A0P0S50mwh^db1S5 0!eOph697dpi0=gt0K04.

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

.128013nurw6cs _1pk(d[3tvo2=il:,j;7efSb4/-+gy5]mPh)a050o0D0r0T0w0x0h0i0g0x0T0h0h0v010r0w0l010406050h0c0P0P0T0d0M040F0t0x0c0.0t0b050I0^0`0|0~0?0l04051e171h0I1e0?0o0w0s0$0(0*0,0(0b0L0c0T0L0D0J0l0M0r0R150i0R0w0L0R0x1J0R0r0;050X0G0x0D1q0)0+011I1K1M1K0r1S1U1Q0r0d1f1E0$110h0l0T0b0,0u011W1s010E0Z0D0b0T0P0D1Q1=1@1|1Y1 1U22240;0a0i0Q0d0t0l0t0h0w140b0i0V1:0d0d0D0g2p17270b1f0I1E2C1,1.1-1R0o291t0w0b212m1Q1n1p0%1X2M2O0b0t2S1Q0l2v1f2A2C2)0@1?2q2U1}2Y0d0{0x1Q0T1H2v0E0,030j0j0g2Z0D1M2X0t0J0C0J0k0;0k170T2*2-0=2,282/1Y2;2?2^2`0D2|012~3032342P370J1`040u3d3f1@3h2A2L013m0T2@1f2_0R2{2}2 310V3w2Y3y0q0;0q3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380H0;0H3#183%3i2.1r3l0t2=3L3o3P3q3R3u3U3@3W380N0;0N3}2)3(2-3I3,473:3t3T334d36380f0;0f4j3 3)423+443n3N3p3r4r3?353y0C0;0C4A3F1i2%172S2F0o1.2K3*014s2R1o1f2$0D2(3g3$4S4s4-280w0o0,2 2A3y3a4H4@4_4b4t4M383a0i2d0D504s3V4v391Q0I3e403I0m0;0V0E4/2B5h4#0e0;0i5n4=412V3J0E0;1,0w0j0h332w2y3~4S4C5x0:040n5u5p4D3J5A0T1T0D0T0c5P5K1}5M0S0y5u0?5I5o3H4 014`2-3y3A3.0i5.3=4c533z1{57594L3^5}2C3e0i665t5!1Y5j040E445u684m4#0b0;0w6f5Q5x0t5r042N6m693+0G0;0d1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0S6t6C6o0;0J6%6N5x0P0w3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0j6/0b6l6G6g6-1}0t0;0v6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0J7J3D7i7j6S6b6d0d7y4n0;0A7%4#6p6k167r7k6v6x6z0D6{4#6E7_5R6j7B7:6S7v040K7+5R6/6;7D6(6@0z855x0b6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0b3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0w5m808a7A6V8r8m3I5M0p8s2:7)8,8k0;0O8d7u0;020x0r0B8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0O5(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;98a4a18t040O9_2)9Fahacak6@af4.9(9=at8:am7C2+0I4;4T4,4V4)170r4YaK2I2D9}2C4W5*0V0X0Z0h04.

Évaluations restantes : 5/5

.128013nurw6cs _1pk(d[3tvoé2=il:,j;7e8fSb4/-+gy5]mPh)a050o0E0r0V0x0y0h0i0g0y0V0h0h0w010r0x0l010406050h0c0R0R0V0d0O040H0t0y0c0:0t0b050K0`0|0~100^0l04051g191j0K1g0^0o0x0s0(0*0,0.0*0b0N0c0V0N0E0L0l0O0r0T170i0T0x0N0T0y1L0T0r0?050Z0I0y0E1s0+0-011K1M1O1M0r1U1W1S0r0d1h1G0(130h0l0V0b0.0v011Y1u010G0#0E0b0V0R0E1S1@1_1~1!211W24260?0a0i0S0d0t0l0t0h0x160b0i0X1=0d0d0E0g2r19290b1h0K1G2E1.1:1/1T0o2b1v0x0b232o1S1p1r0)1Z2O2Q0b0t2U1S0l2x1h2C2E2+0_1^2s2W1 2!0d0}0y1S0V1J2x0G0.030j0j0g2#0E1O2Z0t0L0F0L0k0?0k190V2,2/0@2.2a2;1!2?2^2`2|0E2~01303234362R390L1|040v3f3h1_3j2C2N013o0V2_1h2{0T2}2 31330X3y2!3A0q0?0q3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0J0?0J3%1a3)3k2:1t3n0t2@3N3q3R3s3T3w3W3_3Y3a0P0?0P3 2+3*2/3K3.493=3v3V354f383a0f0?0f4l413+443-463p3P3r3t4t3^373A0D0?0D4C3H1k2)192U2H0o1:2M3,014u2T1q1h2(0E2*3i3(4U4u4/2a0x0o0.312C3A3c4J4_4{4d4v4O3a3c0i2f0E524u3X4x3b1S0K3g423K0m0?0X0G4;2D5j4%0e0?0i5p4@432X3L0G0?1.0x0j0h352y2A404U4E5z0=040n5w5r4F3L5C0V1V0E0V0c5R5M1 5O0U0z5w0^5K5q3J51014|2/3A3C3:0i5:3@4e553B1}595b4N3`5 2E3g0i685v5$1!5l040G465w6a4o4%0b0?0x6h5S5z0t5t042P6o6b3-0I0?0d1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0U6v6E6q0?0L6)6P5z0R0x3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0j6;0b6n6I6i6/1 0t0?0w6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0L7L3F7k7l6U6d6f0d7A4p0?0B7)4%6r6m187t7m6x6z6B0E6}4%6G7{5T6l7D7=6U7x040M7-5T6;6?7F6*6_0A875z0b6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0b3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0x5o828c7C6X8t8o3K5O0p8u2=7+8.8m0?0Q8f7w0?020y0r0C8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0Q5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720L4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040Q9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0g4 030i0u0g0T7_7E2-0K4?4V4.4X4+190r4!a!2K2Fa02E4Y5,0X0Z0#0h04.

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

.128013nurw6cs _1pk(d[3tv0o2=il:,èj;7e8fSb4/-Ogy5]mPh)a050o0F0r0W0x0y0h0i0g0y0W0h0h0w010r0x0l010406050h0c0S0S0W0d0P040I0u0y0c0;0u0b050L0{0}0 110_0l04051h1a1k0L1h0_0o0x0s0)0+0-0/0+0b0O0c0W0O0F0M0l0P0r0U180i0U0x0O0U0y1M0U0r0@050!0J0y0F1t0,0.011L1N1P1N0r1V1X1T0r0d1i1H0)140h0l0W0b0/0v011Z1v010H0$0F0b0W0S0F1T1^1`1 1#221X25270@0a0i0T0d0u0l0u0h0x170b0i0Y1?0d0d0F0g2s1a2a0b1i0L1H2F1/1;1:1U0o2c1w0x0b242p1T1q1s0*1!2P2R0b0u2V1T0l2y1i2D2F2,0`1_2t2X202#0d0~0y1T0W1K2y0H0/030j0j0g2$0F1P2!0u0M0k0t3a0@0k1a0W2-2:0^2/2b2=1#2@2_2{2}0F2 01313335372S3a3c1}040v3g3i1`3k2D2O013p0W2`1i2|0U2~3032340Y3z2#3B0M0q0@0q3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0M0K0@0K3)1b3+3l2;1u3o0u2^3O3r3S3t3U3x3X3{3Z3}0Q0@0Q422,3,2:3L3:4c3@3w3W364i393}0f0@0f4o443-473/493q3Q3s3u4w3`383!0E0@0E4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0G0@0G4W2E1l2*1a2V2I0o1;2N3.014x2U1r1i2)0F2+3j3*3I054x572b0x0o0/322D3!0k3r5f5h4g4y4-3c5l0i2g0F5o4x3Y4A5s1T0L3h453L0m0@0Y0H594?4H2Y010e0@0i5L5d465O0b0H0@1/0x0j2Q0h0F0d2B435a5N200?040n5T5F4 0b5Z0W1W0F0W0c5?5.1#5:0V0z5T0_5,5M4r5n015i2:3!3D3=0i6b4+5q3|3C1~5v5x4Q6m0M6g5D040i6x5S610/5H040H495T6z4r5^0@0x6G5@4!0u5Q042Q6M6A3M0J0@0d1`1C606I4!5:5=685U3L0S0x3e6#4Z5O5:0A6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0V64666~6i5g6c0j5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0s3O0F0c0d0j0W5$0b5(2y0d6^7H1#0u0@0w7W6 3o5`5|5~7h4 5:0p7,4!756L7a6U5:0R7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040C7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0e1L1X8m6J8k8W6O0@020O0r0D8Z5O6-0@0t8*206P0@1`0o8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0M8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0M4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0M4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0g5l04030i0N2t5%0B2yaL4?0L5c4@564_531a0r4|bn2L2G8{bk0L4`670Y0!0$0h04.

Évaluations restantes : 5/5

.128013nurw6cs _1pk(d[3tv0o2=il:,j;7e8fSb4/-gy5]mPh)a050o0E0r0U0x0y0h0i0g0y0U0h0h0w010r0x0l010406050h0c0Q0Q0U0d0N040H0u0y0c0/0u0b050K0_0{0}0 0@0l04051f181i0K1f0@0o0x0s0%0)0+0-0)0b0M0c0U0M0E0L0l0N0r0S160i0S0x0M0S0y1K0S0r0=050Y0I0y0E1r0*0,011J1L1N1L0r1T1V1R0r0d1g1F0%120h0l0U0b0-0v011X1t010G0!0E0b0U0Q0E1R1?1^1}1Z201V23250=0a0i0R0d0u0l0u0h0x150b0i0W1;0d0d0E0g2q18280b1g0K1F2D1-1/1.1S0o2a1u0x0b222n1R1o1q0(1Y2N2P0b0u2T1R0l2w1g2B2D2*0^1@2r2V1~2Z0d0|0y1R0U1I2w0G0-030j0j0g2!0E1N2Y0u0L0k0k380=0k180U2+2.0?2-292:1Z2=2@2_2{0E2}012 3133352Q383a1{040v3e3g1^3i2B2M013n0U2^1g2`0S2|2~30320W3x2Z3z0L0q0=0q3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390L0J0=0J3%193)3j2/1s3m0u2?3M3p3Q3r3S3v3V3_3X3{0O0=0O402*3*2.3J3.4a3=3u3U344g373{0f0=0f4m423+453-473o3O3q3s4u3^363Y0D0=0D4D3G4o3k4G3K4I494K4b4M3@4f4P3{0F0=0F4U2C1j2(182T2G0o1/2L3,014v2S1p1g2%0E2)3h3(3G054v55290x0o0-302B3Y0k3p5d5f4e4w4+3a5j0i2e0E5m4v3W4y5q1R0K3f433J0m0=0W0G574;4F2W010e0=0i5J5b445M0b0G0=1-0x0j2O0h0E0d2z41585L1~0;040n5R5D4}0b5X0U1U0E0U0c5;5,1Z5.0T0z5R0@5*5K4p5l015g2.3Y3B3:0i694)5o3`3A1|5t5v4O6k0L6e5B040i6v5Q5 0-5F040G475R6x4p5?0=0x6E5=4Y0u5O042O6K6y3K0I0=0d1^1A5~6G4Y5.5:665S3J0Q0x3c6Z4X5M5.0A6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0T62646|6g5e6a0j5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0s3M0E0c0d0j0U5!0b5$2w0d6?7F1Z0u0=0w7U6}3m5^5`5|7f4}5.0p7*4Y736J786S5.0P7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040B7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0e1J1V8k6H8i8U6M0=020M0r0C8X5M6+0=0t8(1~6N0=1^0o8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0L8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0L4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0L4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0K5a4=544@51180r4`b92J2E8_b60K4^650W0Y0!0h04.

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$.