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

.128013ex )sk_à}8-bi26]:O^+70vl;3[qLczgPh/r5ASaèF,4Ào.9myùwuêR1dIDtpfN{Tné=(050)0b0,0O0n0y0f0d0E0y0O0f0f0@010,0n0-010406050f0#0X0X0O0K0Y040N0U0y0#190U0=0d020O0X0-0z0d0%0b1j0K0C0#0b0f050J1g1i1k1m1e0-04051R1K1U0J1R1e0)0n0x11131517130=0G0#0O0G0b0l0-0Y0,0I1t0d0I0n0G0I0y1}0I0,1c050|0m0y0b1%1416011|1~201~0,2628240,0K1S1^111p0f0-0O0=170o012a1)010.0~0b0=1x0b242s2u2z2c2C282F0X2H040a0d0H0K0U0-0U0f0n1s1u0`2q0K0K0b0E2$1K2J0=1S0J1^2=2m2o2n250)2L1*0n0=2E2Z241!1$122b2 310=0U35240-2+1S2:2=3i1f2t1u372A3b0K1j0y240O1{2+0.17030h0h0E3c0b203a0U0l0w0l0(1c0d0(1K0O3j3m1d3l2K3o2c3q3s3u3w0b3y013A3C3E3G323J0l2x040d0o3Q3S2u3U2:2~013Z0O3t1S3v0I3x3z3B3D0`3-3b3/0A3N0A3^2/3T1e3|3X173 410543453)473,303.3K0S3N0S4g1L4i3V3n1(3Y0U3r403#443%463+494v4b3K0L3N0L4B3i4j3m3}4n4L4r3*483F4R3I3K0p3N0p4X4D4k4G4m4I3!423$3(4)4u3H3/0v3N0v4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0k3N0k562;584F385b4J4o4q4N4s4P4+5j0l0W3N0W5o3{4!4l5t4{4p4}4O4*4a4-3L0w1c0(0w5G5q4#5c5v5N5y5P4,3/0(3M045+5X4E5Z5u4%5x4 5i4w3L3;0(3@0J3R4h3`1V3g1K352^0)2o2}5J4*341#1S3f0b3h3T612;054*6i2K0n0)173B2:5*3#6q6s5z5Q6v0d2P0b6y5(5B5,4g4@5s0g1c0`0.6k6o5r2A0!3N6Q5:5J0=0.6N0n0E1_0,0U0X0n0b6W6K2A1b040^6.5I5a0=1c3b0X0m2+1J4C626/2c6;0R6Q0d6X6_1c0E0n276-716l73176;0e0r6Q1e7g6R0d6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0d7M795s6`040`0m1r777O2A0U1c0@7V7i016+1c5W7p7o3k3|7z0h6u3K4d4|7/6G5`4d7E2Q7G5_4S0l7?3^7M7N7$7Q2C0=7#6^5s7Y047!7p78860m1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0e8a8n7X1c0l8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040!1|288I4#6N0b7T0,8^5J8d020y0,0z8f3i8-8E8t04888O5J6;7m7+8O7/7;0l4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200b0#8~5a8d953T978J018p9c7a9a309H8c1c0u9U3p8`8|9Q8o8B9$8F040J0J9)2c8L5~4Y9h9n9j4/9m9t8Y0l4/8!9{9p9}7J8+9y858.2c8:0n6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0B9.9B049D6,9G8r7$6;0q9f9=aE4!9i8T0l539`8$7H80539 aR7 5RaP9xa58,ad8:2+0,0#0K89aiau010g0E1c0;0K1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900G93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0f7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0Q40c8b#0E5,030d2!0d1`0=02030A0W0z3v2t102m0U0#0x0?cL6j0J6n636h656e1K0,68dj2{2?0O7e2=661Q7q5J2+0X0h0.0O0g0b0h0I7?1C1E1G1I0dce6l1X3U353}0O0)0X1t2#0n1`300.8d1QdQdSdU2$0l190,2k041C6%0b0Kd:0d2t0K0d1!6%0U6)6+7f1Y1T040*0yc_001/2#d`000#1u400G4I2#0I2Q2L0ndI0V0d0D292j0b0O0#d@0K0n102Ed@1k1x0P2m290)0Ue91fd61,040U271}0O6)0ndw2E0,0d0$eE0d2m0nda1LeK0G040V1V3U1R0T110I0OdI7r0,0?0KeQdW0=0Rc{1uc8d`1D2u2(c`130d0x409Fd_0EeUe`280d1IeV0?0Gfa0d0i0df76m3E04bhah6ndKe,1e0#0y3U2004c`d70ne~1`2+0=0xeH290n1i0?1!eQ1DeU786na@a_ddfs1KfD1efDc`3be}110{0,29fu29fic_eHeV7mfAfC0nfE0#0-e_aC2+fnfp3vf928a+f-0=2mfm0r7re5dz1re:d;d:d_0)2u10f7d^19eF2W2#eFeueret0d6?6n7Sgi0@0dbxeu0u3O1K6n8C0Jf%05fDdYg1fb29fof7g7fbgagcfgge0~0dgheVglgld`gog5eA0Kgs0dfl0#d?0)gxdp28gzgBfs880dgFgH0d0lgKf!0`04gNgP0Jf{7ohdhfe20D3v0F1teF292+g,0I290^0y000?0E1keVfe29frhacxfw0{fWfsgD8}h96h0ec_hpfR0#e9fo6%e=1He@e_e{1`gefF1u88e9d^0d0OfMeShIhE301v921AhKgLfse~0E00f?e?fq6nf;h`ha6Ch~0feVd4g.0=gpeqg}es0#en0sf04IeV2(f70md712f=eVfKh.hC6nc/0 7f6ne+dN7ods0_1#d$dT0=dVdX6Zd!1TiId(e|d*2#d-0/8vg31j0cfP40f2eZd70K102(ipg_2870e11R2V32ic0dec0dhxhzea30d{fOiK19i$hD6hh2h7h_hM3=fki$foad1keh1jf/0c1c090^5V0t0W09gN3ie~0^fd0d1G0nfhi8jx1.0=2}0X0$ej2m0P100Ge`jE0eiCi;040+g/fg0-eSho10hy0ffI0Zg:f;i6f?ia3f0?c8gb0bfI1u0K0?40exeqd7idd5i)i+29i-ir102Y15ag1IjQ3UhifD0Meu6gd d_6)a+j=h,i_1ui|g=fhfLeS1`2(jfew1^ji0bjk04jm090.e`0E0:jo0W0j0:0o0jjr6Qh|i7eVfo1!g3ku7$jgkxfTkAjm0L0d09192Q10jo0kkO8rgOf}f(f}kdf20#i!0PjIi)kk3vi`kohAkr2W2%hCkXkweik!jl0^kDkF0:k%k)fPdJk-kKkMk/96h}f?kTjXcv5skYlajjlc0olhk*lk0w0t0vlodcgPkc30c`f5hSf/0d0VlRf$k=gQk@gxfK19k|j{kje kll1hykp0)h~l41`kvjhlbkBldkE0OkGkIlm0t0:0A0w0jkNjs9LlqjBlskVl-0xks1u0(iChhfBdt0MlLfHib10ec2920i8hoeZ0}0yfgl:kZlyl?kIlH3`e~ezgz0-1qeyl.1ul i(a+101`0f0}eVf6hw0y0?2Qgbh:6hi3jajAi9j@j/0,k9iE6eiE0{mt0f04.

Évaluations restantes : 5/5

.128013ex )sk_à}8-bi26]:O^+70vl;3[qLczgPh/r5ASaèF,4Ào.9myùwuêR1dIDtpfN{Tné=(050)0b0,0O0n0y0f0d0E0y0O0f0f0@010,0n0-010406050f0#0X0X0O0K0Y040N0U0y0#190U0=0d020O0X0-0z0d0%0b1j0K0C0#0b0f050J1g1i1k1m1e0-04051R1K1U0J1R1e0)0n0x11131517130=0G0#0O0G0b0l0-0Y0,0I1t0d0I0n0G0I0y1}0I0,1c050|0m0y0b1%1416011|1~201~0,2628240,0K1S1^111p0f0-0O0=170o012a1)010.0~0b0=1x0b242s2u2z2c2C282F0X2H040a0d0H0K0U0-0U0f0n1s1u0`2q0K0K0b0E2$1K2J0=1S0J1^2=2m2o2n250)2L1*0n0=2E2Z241!1$122b2 310=0U35240-2+1S2:2=3i1f2t1u372A3b0K1j0y240O1{2+0.17030h0h0E3c0b203a0U0l0(3J1c0d0(1K0O3j3m1d3l2K3o2c3q3s3u3w0b3y013A3C3E3G323J0l2x040d0o3P3R2u3T2:2~013Y0O3t1S3v0I3x3z3B3D0`3,3b3.0A3M0A3@2/3S1e3{3W173~400542443(463+303-3K0S3M0S4f1L4h3U3n1(3X0U3r3 3!433$453*484u4a3K0L3M0L4A3i4i3m3|4m4K4q3)473F4Q3I3K0p3M0p4W4C4j4F4l4H3Z413#3%4(4t3H3.0v3M0v4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0k3M0k552;574E385a4I4n4p4M4r4O4*5i0l0W3M0W5n3`4Z4k5s4`4o4|4N4)494,3J0w1c0(0w5F5p4!5b5u5M5x5O4+3.0(0(5T3O0J3Q4g564D5Y5t4$5w4~5h4v3J3:0(3?5.3^2;1V3g1K352^0)2o2}5I4)341#1S3f0b3h3S5:634)6j2K0n0)173B2:5)3!6q6s5y5P6v0d2P0b6y5%5A5+2=5/4?5r0g1c0`0.6l6o5q2A0!3M6R5=5I0=0.6O0n0E1_0,0U0X0n0b6X6L2A1b040^6/5H590=1c3b0X0m2+1J4B3_6Y596=0R6R0d745r6{040E0n276.72636:2c6=0e0r6R1e7i6S0d6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610d7N797k4l6O0b0m1r787a2A0U1c0@7W7Q016,1c5V7r7q3k3{7B0h6u3K4c4{7:6G5|4c7G2Q7I5{4R0l7@3@7O7P6_7b1c2C0=7$877Y7!8c587b0m1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0e8g8z177Z040l8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040!1|288J6Z7S7U0,8^598G020y0,0z7#7r868n8t048a8P5I6=7o7,8P7:7=0l4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200b0#8}5r8G943i968E016=8q7.8d989a958.018G0u9F3p8`7V8r7%7m9b8~1c0J0J9)5r8L608O9$4Z9h8U0l4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0n6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0B9.9Z049B6-9E9?au9M1c0q9e9=at1u9^2u518W9}9o0l528#aR5A528+a7a79U8:2+0,0#0K8bad9Q8/0E1c0;0K1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0G92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0f7hb?9c1cbF5;bHaN0=5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0n5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0ga:040Q3 c8cN3k0J6n646i666f1K0,69c~2{2?0O7g2=671Q7s5I2+0X0h0.0O0g0b0h0I7@1C1E1G1I0dcd631X3T353|0O0)0X1t2#0n1`300.8G1Qdvdxdz2$0l190,2k041C6(0b0KdR0d2t0K0d1!6(0U6*6,7h1Y1T040*0y0d0f001/2#dY000#1u3 0G4H2#0I2Q2L0ndn0V0d0D292j0b0O0#dV0K0n102EdV1k1x0P2m290)0Ud=1f2m1t0G040U271}0O6*0ndb2E0,0d0$ek0d2m0n0?2/eq1,040V1V3T1R0T110I0Odn7t0,0?0KexdB0=0R0d1`c8dY1D2u2(2!0d130d0x3 9DdX0EeBe!280d1IeC0?0Ge^0d0ie;3v056nbh7h6ndpeP1e0#0y3T2004e:0U0#0ne(1`2+0=0xen290n1i0?1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0,29fbe 0feC0feneC7ofhfj0nfl0#0-eZaC2+f5f7e?e^a*fR0=2mf40r7td-de1reTdSdRdX0)2u10e=dW19el2W2#eleae7e90d6@6nbZg00@0db+ea0u3N1K6n8C0JfL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0df eCg3g3dYg6f;g96-0df30#dU0)gfd428ghgjfJ8a0dgngp0d0lgsfI0`04gvgx0Jf%7qg|g~d*0D3v0F1tel292+gS0I290^0y000?0E1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0ed.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0d0OfuezfEhn1u9092e,b!hx04e(0E00f00deWe=ht6ifbhpg_6Ch,fXeg10g50=g7e6g)e80#e30s1ufZ0KeC2(e=0mfn12290{0dfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0=dAdC6!dF1TixdJe$dL2#dO0/br291j0cfx3 e,eGfn0Kh}29idg#2871d)1R2V32h 0dd^0dhghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0c1c090^5U0t0W09gv3ie(0^e{h.fofWeC2m0P100Ge!0=0)0eiri$040+gVe~0-ezh710hh0ffq0Zf;fV0=h`eC2t103f0?c8f_0bfq1u0K0?3 ede6fni0106*a*iW0diYifjS2Z2!7g0fjy3Th1fk0Mea6hd%dXj,0KjYhTi+1ui.i9e ftez1`2(j4ec1^j70bj904jb090.e!0E0:jd0W0j0:0o0jjg6Rh*jPf:1!f/kf7%j5kifBkljb0L0d09192Q10jd0kkz8rgwf)fMf)j~e,0#iP0Pd k3k53vi,k9hjkc2W2%hlkHkhd~kKja0^kokq0:kNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0ol1kQl40w0t0vl86kkXf(040M30e:e/hD290VlC1Kgxj}gffs19k)j(a*k,k7i-hhka0)h,k;1`kgj6k{kmk}kp0Okrktl60t0:0A0w0jkyjhamlah{lcjFd?2E0xkd1u0(irh0fid8lwh fpgUi*d^2920fXh7eG0}0ye~lWkJlilZktlr3_e(efgh0-1qeelU1ul,iTj-e)i70}fY0ne;hf0y0?2Qf_hXg_h?h(joebjUeBj`it6fit0{me0f04.

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

.128013*ex )sk_=à8-bi26]:O+70vl;3î[qLcgPh/r5aSè4,o.E9mywuR1dIDtpfNTnéC(050#0c0(0M0o0y0g0e0F0y0M0g0g0j010(0o0)010406050g0Y0V0V0M0K0W040N0R0y0Y140R0-0e020M0V0)0z0e0Z0c1e0K0D0Y0c0g050J1b1d1f1h190)04051M1F1P0J1M190#0o0x0|0~10120~0-0G0Y0M0G0c0m0)0W0(0I1o0e0I0o0G0I0y1^0I0(17050@0n0y0c1Y0 11011@1_1{1_0(21231 0(0K1N1:0|1k0g0)0M0-120p01251!010*0_0c0-1s0c1 2n2p2u272x232A0V2C040a0e0H0K0R0)0R0g0o1n1p0=2l0K0K0c0F2X1F2E0-1N0J1:2-2h2j2i200#2G1#0o0-2z2U1 1V1X0}262`2|0-0R301 0)2$1N2+2-3d1a2o1p322v360K1e0y1 0M1?2$0*12030i0i0F370c1{350R0m0p0m0!170e0!1F0M3e3h183g2F3j273l3n3p3r0c3t013v3x3z3B2}3E3E3I0p3L3N2p3P2+2_013U0M3o1N3q0I3s3u3w3y0=3(363*0A3I0A3.2*3O193=3S123^3`053|3~3!403%2{3)3F0P3I0P491G4b3Q3i1Z3T0R3m3_3W3}3Y3 3$424o443F0L3I0L4u3d4c3h3?4g4E4k3#413A4K3D3F0q3I0q4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0v3I0v4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0l3I0l4 2,514y33544C4h4j4G4l4I4!5c0m0U3I0U5h3;4T4e5m4;4i4?4H4Z434$3G0w170!0w5z5j4U555o5G5r5I4#3*0!3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0J3M4a3:1Q3b1F302:0#2j2^5C4Z2 1W1N3a0c3c3O5`2,054Z6b2F0o0#123w2+5Z3W6j6l5s5J6o0e2K0c6r5X5u5#494-5l0h170=0*6d6h5k2v0X3I6J5)5C0-0*172{1V0F0c6P6D2v16040:6Z5B530-172e0c0M0Y6)525l6$0Q6J0e6Q6+170F0o226Y4v5{6!276$0f0s6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040e7z6{754f6G0c0n1m6`6|5l0R170j7I7C010V0o175P7c3P7V5)7m0i6n3F464=7Z6z5:467r2L7t5/4L0m7%3.7A7B6*5l6,042x0-7O7`2v7L047N7V7_6?3k0n172J6=6L76176(7X7P7|6.6:8d3?77808827830m8q8e127R5N7a8n7Z7#0m4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040X1@238v4U7E7G0(8#5C83020y0(0z853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0c6;869l12838;3O8?8o8g8{6}040=8(8*53830u9G7{8_2{9B6@170f9K82170J0J9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0o6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0C9O3k9n0_0o9qan8f040r8~9$8i4T8C9*0m4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0m5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0M718mazaX01alataea$asbm8@6$aw8Abu0eaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0(0Y0K7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0g72aibn8}byb~1pbB0-5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0!7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010h0F170+1ob}4w7X0J6g5|6a5~671F0(61c@2?2.bj232-5 1L6K3?2$0V0i0*0M0h0c0i0I7%1x1z1B1D0eax6c1S3P303?0M0#0V1o2W0o1=2{0*831Ldodqds2X0m140(2f041x0F0I0c0KdK246W1;0(0R7RdgbA0(0.0K0M140x240s0e0k2l0-2A0B2h721T1O040$0y0e0g001*2W0e2Z0yd{0y0G4B2W0I2Ld~242$dOdNdLd~0odK0RdSdU1C2G0odg0S1Q7Wd00;1WdAdr0-dtdv6Sdy1OeudCduc5dFdH0E3qeadLecdP24e06VefdP0Y0eb!epd10E240F3_0F0Yd^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0R0o0{dg0ydg0{3y1d2z0@0o2$0g0S0e0$6 0e1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10t0K0Qd~2pf0dMf40-0{flfn0{2Zfe0GdZ1I2X2lf20e230e0/f,0~0ef40yg30=0{f3ar0Kgd0g0(g20o7RdX0cf80/eZe#e%6{4Zfk2pfm1+1-0Wfq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0)9qgj2o0Kdxe{0e0c0d0F0.0=0K0|0?0(e?0^gaeOgle=f80T1p3Y0*0?f,2Vg2dh0=0Y0dbA0-6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0g1ogjf|2p0#0gg69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0eg?1md~0.2o10dMg23q0x3_h/gkgmgoeWd=0%f.h40|0 fc3igsg3ePhreRe-eUcteT2z0e1maq0g2pgjg70~0K1+bUe8g2e*0-h60Kimh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0.b|iZh.ic2R220Oe72|d_242Tb|iciye!f+g}1p0H1/1;0-h.gdiZgf0{0-00h(jMf_h70_iChbh6f80,0Re^g{h-0e0N0oiX1=0Mimd}1eew0)e%0.e8j!dT0nf60e0*0yeh0@iZf?jJjD0yjF24b|dZd}0M0)g_eTf1e7g_g}0d1y0)g38~d;dn5Cdpevexhf0d1skz2MdzkEdBewdDeG2M0Tkx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0/1oh%g30N1D2V1o6P696K3/6ec/cDb(7i0A3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0G6$020G8/ltlvlu1vbqaTi|jggLg,6T9!0S7Uj6gK0b0bfY5$0w0p48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0zl^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0F5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0#ig261yf3m!kp0Mm%k4kcggiWg7h;2Ln37Ymjl80m9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040l0S0U0l0l0P0q0L0q0v0P0A5!0L0l0c0u0A0w4~lT3fjnc;1S5}0Jerp4677bp50=g90g04.

Évaluations restantes : 5/5

.128013*ex )sk_=à8-bi26]:O+70vl;3î[qLcgPh/r5aSè4,o.E9mywuR1dIDtpfNTnéC(050#0c0(0M0o0y0g0e0F0y0M0g0g0j010(0o0)010406050g0Y0V0V0M0K0W040N0R0y0Y140R0-0e020M0V0)0z0e0Z0c1e0K0D0Y0c0g050J1b1d1f1h190)04051M1F1P0J1M190#0o0x0|0~10120~0-0G0Y0M0G0c0m0)0W0(0I1o0e0I0o0G0I0y1^0I0(17050@0n0y0c1Y0 11011@1_1{1_0(21231 0(0K1N1:0|1k0g0)0M0-120p01251!010*0_0c0-1s0c1 2n2p2u272x232A0V2C040a0e0H0K0R0)0R0g0o1n1p0=2l0K0K0c0F2X1F2E0-1N0J1:2-2h2j2i200#2G1#0o0-2z2U1 1V1X0}262`2|0-0R301 0)2$1N2+2-3d1a2o1p322v360K1e0y1 0M1?2$0*12030i0i0F370c1{350R0m0P0m0!170e0!1F0M3e3h183g2F3j273l3n3p3r0c3t013v3x3z3B2}3E0m2s040e0p3L3N2p3P2+2_013U0M3o1N3q0I3s3u3w3y0=3(363*0A3I0A3:2*3O193@3S123`3|053~403!423%2{3)3F0P3I0P4b1G4d3Q3i1Z3T0R3m3{3W3 3Y413$444q463F0L3I0L4w3d4e3h3^4i4G4m3#433A4M3D3F0q3I0q4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0v3I0v4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0l3I0l512,534A33564E4j4l4I4n4K4$5e0m0U3I0U5j3?4V4g5o4?4k4^4J4#454(3G0w170!0w5B5l4W575q5I5t5K4%3*0!3H045$5S4z5U5p4Y5s4`5d4r3G3,0!3/0J3M4c3=1Q3b1F302:0#2j2^5E4#2 1W1N3a0c3c3O5|2,054#6d2F0o0#123w2+5#3W6l6n5u5L6q0e2K0c6t5Z5w5%4b4/5n0h170=0*6f6j5m2v0X3I6L5+5E0-0*172{1V0F0c6R6F2v16040:6#5D550-172e0c0M0Y6+545n6(0Q6L0e6S6-170F0o226!4x5}6$276(0f0s6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0e7B6~5n6.040=0n1m6|7D2v0R170j7K77120V0o175R7e3P7X5+7o0i6p3F484@7#6B5=487t2L7v5;4N0m7)3:7B7C7R3_172x0-7Q6,5n7N047P7X6}7|0-0n172J6@6N78176*7Z896/0M736=8e3^79816^7M170m8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040X1@238x4W6I0c7I0(8(5E84020y0(0z863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0c6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840u8.6 047 8 558r9N9J9z170J0J9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0o6K9Y8{4h70728%a69E8:8=0z9(3k8l8n9w9Ia79F170C9V7E179t0o9var6%170r929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0maI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0m5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0(0Y0K80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0g74bF8q17aB4ybubH0-5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0h0F170+1oc19Cb60F5%030e0N0o0e1=0-02030A0U0z3q0Kav1p2h0R0Y0x0.bE6e0J6i5~6c60691F0(63di2?2.8m232-611L6M3^2$0V0i0*0M0h0c0i0I7)1x1z1B1D0ec55}1S3P303^0M0#0V1o2W0o1=2{0*841LdPdRdT2X0m140(2f041x0F0I0c0Kd/246Y1;0(0R7TdH0e2W0.0K0M140x240s0e0k2l0-2A0B2h741T1O040$0y0e0g001*2W0e2Z0yem0y0G4D2W0I2Lep242$d?d=d:ep0od/0Rd`d|1C2G0odH0S1Q7Ydr0;1Wd#dS0-dUdW6UdZ1OeVd%dVc9d*d,0Ed12%d:eDd@24er6XeGd@0Y0eb(eQds0E240F3{0F0Yejeq00e^6Zepe{b(e|e02W24d`1m3Y0R0o0{dH0ydH0{3y1d2z0@0o2$0g0S0e0$71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe}cu8u85bg9Gax9K8+9Mc$cWcCfZ9r9Ubu90170fcs9#9%f/a.049,db6iePdMds0t0K0Qep2pfrd;fv0-0{fMfO0{2ZfF0Ge11I2X2lft0e230e0/g70~0efv0ygr0=0{fuav0KgB0g0(gq0o7T0(0.0cfz0/f1f3f56}4#fL2pfN1+1-0WfR2a1|1~dtbmcwbyf_f#f|ao6)f(a87Gf*8-g/f.f,an7Ff;c2f?04f^g`f`cD8Af dL6i0e0)9vgH2o0KdYfm0e0c0d0F0.0=0K0|0?0(fh0^gye?gJfgfz0T1p3Y0*0?g72VgqdI0=0Y0dd~0-6YdIfJ2Z5EfM1)gYfQ291`g%fVg}cqf+g03z3-0?gTfKhSgWhUfPg!hXfTg(cpaXc#h(0=3-0g1ogHgk2p0#0ggu9vhph gphQf155hTfOgZg#hY2ch!9E7F9Lg_g|ad179Qg/g~aY3fdch)hbhdep0.2o10d;gq3q0x3{i7gIgKgNe~eg0%g9hq0|0 fDiT0yf4gre@hNe_fbe|bx9vhj1p1mbx0g2pgHgv0~0K1+bZezgqf80-hs0KiIhvdJh,hRidh/ifhWfShZg)b%i)cy3-b6ctipbving-isjih19HbAfW8}h{bkjga,ith$iojqan9XjncBh5g/cEh86gixh}g2ef1MiQgdhHiT0{3a0.c0i}i6hb2R220Oey2|ek242Tc0hbiUf2g6i+2P1/1;0-i6gBi}gD0{0-00i0j-ghht0_iZhxhsfz0,d6hshhi5c?c^er1=0MiIeo1eeX0)f50.ezj}d{0nfx0e0*0yeI0@i}gej*j!0yj$24c0e1eo0M0)hfe{92efdO5EdQeWeYhB0d1s0)d,d!kRd$eXd(e+2M0T0d1ykYeedNeUh.1%h:gZ3y1ph?jab62I2z2B170Hj?1=0/1oh gr0N1D2V1o6R6b6M3;6gdd96b,7k0L3Gb/cR4|lm3Hb?bM46lr2t5a5Jce0mlwb`b60G6(020G8?lHlJlI1vg=7}g@crh4g.jD9)6Vf~0S7WlUf!0b0bh65P0w0p4acGc7a?99lmcKd~cMlAl;chb:3)l_5X5:b1lB3+7y5{7|lF17lK0zm8m86}f=9Sg 9C7{f-7OcDlW0plYg-l$l(5(l*l,l!27g{c.7|cE3Kl-c2c8m17^cLl{lv7@l`lpl|mJl~cjmM7^7zlElGlMmalMmch09SjklSjmmxjrh`6|cA5nc:17c=0#iC261yfui`f22o71gLda76aEl/c9lm8S7nl@aLm14tltcNn8lx4ZmPmIn4mSm584dXm~7fn0lkl:lBlonf3Dlm9gcQntm19gly5Yl^nrlDm5mUlLnIlNmd6_8hlOimg^jlbgiujtnnjBf@g-f{muf}jI7Ac/c;iBiDc02Li}m_kK0Mm|kpkxgEi`gvi92LnmdtmDlm9~mGmLmI4*nanDo5nBl 6vo0m3jb5neu6W6Un}7!n1m1aSo2nylmaNnxlunuaRnd5/opovnFcWm604mWnJmYjAiljynRg/f%nLaim*lS8wjxlQh%m nWh2nYmqn$94oHl?npn2a}bLnblm5go6n7o-ow5botm1b3nioB840l0S0U0l0l0P0q0L0q0v0P0A5$0L0l0c0u0A0w50mBh|df1S5 0JeSpm697dpn0=gx0g04.

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

.128013r5aSe )jsP4_k,(o-myibw26u]:1+d7vl;3t[pfcng=/h050E0f0K0d0u0H0j0g0O0H0d0j0j0R010K0u0M010406050j0z0s0s0d0b0t040e0q0H0z0.0q0P050S0^0`0|0~0?0M04051e171h0S1e0?0E0u0G0$0(0*0,0(0P0Q0z0d0Q0f0r0M0t0K0T150g0T0u0Q0T0H1J0T0K0;050X0v0H0f1q0)0+011I1K1M1K0K1S1U1Q0K0b1f1E0$110j0M0d0P0,0x011W1s010N0Z0f0P0d0s0f1Q1=1@1|1Y1 1U22240;0a0g0k0b0q0M0q0j0u140P0g0V1:0b0b0f0O2p17270P1f0S1E2C1,1.1-1R0E291t0u0P212m1Q1n1p0%1X2M2O0P0q2S1Q0M2v1f2A2C2)0@1?2q2U1}2Y0b0{0H1Q0d1H2v0N0,030m0m0O2Z0f1M2X0q0r0F0r0C0;0C170d2*2-0=2,282/1Y2;2?2^2`0f2|012~3032342P370r1`040x3d3f1@3h2A2L013m0d2@1f2_0T2{2}2 310V3w2Y3y0J0;0J3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380l0;0l3#183%3i2.1r3l0q2=3L3o3P3q3R3u3U3@3W380c0;0c3}2)3(2-3I3,473:3t3T334d36380y0;0y4j3 3)423+443n3N3p3r4r3?353y0F0;0F4A3F1i2%172S2F0E1.2K3*014s2R1o1f2$0f2(3g3$4S4s4-280u0E0,2 2A3y3a4H4@4_4b4t4M383a0g2d0f504s3V4v391Q0S3e403I0n0;0V0N4/2B5h4#0w0;0g5n4=412V3J0N0;1,0u0m0j332w2y3~4S4C5x0:040p5u5p4D3J5A0d1T0f0d0z5P5K1}5M0h0B5u0?5I5o3H4 014`2-3y3A3.0g5.3=4c533z1{57594L3^5}2C3e0g665t5!1Y5j040N445u684m4#0P0;0u6f5Q5x0q5r042N6m693+0v0;0b1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0h6t6C6o0;0r6%6N5x0s0u3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0m6/0P6l6G6g6-1}0q0;0R6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0r7J3D7i7j6S6b6d0b7y4n0;0i7%4#6p6k167r7k6v6x6z0f6{4#6E7_5R6j7B7:6S7v040D7+5R6/6;7D6(6@0o855x0P6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0P3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0u5m808a7A6V8r8m3I5M0L8s2:7)8,8k0;0A8d7u0;020H0K0I8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0A5(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;98a4a18t040A9_2)9Fahacak6@af4.9(9=at8:am7C2+0S4;4T4,4V4)170K4YaK2I2D9}2C4W5*0V0X0Z0j04.

Évaluations restantes : 5/5

.128013r5aSe )jsP4_k,(o8-myibw26u]:1+d7vl;3t[pfcngé=/h050F0f0L0d0v0I0j0g0P0I0d0j0j0T010L0v0N010406050j0A0t0t0d0b0u040e0q0I0A0:0q0Q050U0`0|0~100^0N04051g191j0U1g0^0F0v0H0(0*0,0.0*0Q0R0A0d0R0f0s0N0u0L0V170g0V0v0R0V0I1L0V0L0?050Z0w0I0f1s0+0-011K1M1O1M0L1U1W1S0L0b1h1G0(130j0N0d0Q0.0y011Y1u010O0#0f0Q0d0t0f1S1@1_1~1!211W24260?0a0g0k0b0q0N0q0j0v160Q0g0X1=0b0b0f0P2r19290Q1h0U1G2E1.1:1/1T0F2b1v0v0Q232o1S1p1r0)1Z2O2Q0Q0q2U1S0N2x1h2C2E2+0_1^2s2W1 2!0b0}0I1S0d1J2x0O0.030m0m0P2#0f1O2Z0q0s0r0s0D0?0D190d2,2/0@2.2a2;1!2?2^2`2|0f2~01303234362R390s1|040y3f3h1_3j2C2N013o0d2_1h2{0V2}2 31330X3y2!3A0K0?0K3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0l0?0l3%1a3)3k2:1t3n0q2@3N3q3R3s3T3w3W3_3Y3a0c0?0c3 2+3*2/3K3.493=3v3V354f383a0z0?0z4l413+443-463p3P3r3t4t3^373A0G0?0G4C3H1k2)192U2H0F1:2M3,014u2T1q1h2(0f2*3i3(4U4u4/2a0v0F0.312C3A3c4J4_4{4d4v4O3a3c0g2f0f524u3X4x3b1S0U3g423K0n0?0X0O4;2D5j4%0x0?0g5p4@432X3L0O0?1.0v0m0j352y2A404U4E5z0=040p5w5r4F3L5C0d1V0f0d0A5R5M1 5O0h0C5w0^5K5q3J51014|2/3A3C3:0g5:3@4e553B1}595b4N3`5 2E3g0g685v5$1!5l040O465w6a4o4%0Q0?0v6h5S5z0q5t042P6o6b3-0w0?0b1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0h6v6E6q0?0s6)6P5z0t0v3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0m6;0Q6n6I6i6/1 0q0?0T6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0s7L3F7k7l6U6d6f0b7A4p0?0i7)4%6r6m187t7m6x6z6B0f6}4%6G7{5T6l7D7=6U7x040E7-5T6;6?7F6*6_0o875z0Q6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0Q3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0v5o828c7C6X8t8o3K5O0M8u2=7+8.8m0?0B8f7w0?020I0L0J8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0B5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720s4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040B9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0P4 030g0S0P0V7_7E2-0U4?4V4.4X4+190L4!a!2K2Fa02E4Y5,0X0Z0#0j04.

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

.128013r5aSèe )jsP4_k,(o8-myibw26u]:O1d70vl;3t[pfcng=/h050G0g0N0d0w0K0k0h0R0K0d0k0k0U010N0w0P010406050k0B0u0u0d0b0v040e0r0K0B0;0r0S050V0{0}0 110_0P04051h1a1k0V1h0_0G0w0J0)0+0-0/0+0S0T0B0d0T0g0t0P0v0N0W180h0W0w0T0W0K1M0W0N0@050!0x0K0g1t0,0.011L1N1P1N0N1V1X1T0N0b1i1H0)140k0P0d0S0/0z011Z1v010Q0$0g0S0d0u0g1T1^1`1 1#221X25270@0a0h0l0b0r0P0r0k0w170S0h0Y1?0b0b0g0R2s1a2a0S1i0V1H2F1/1;1:1U0G2c1w0w0S242p1T1q1s0*1!2P2R0S0r2V1T0P2y1i2D2F2,0`1_2t2X202#0b0~0K1T0d1K2y0Q0/030n0n0R2$0g1P2!0r0t0F0I3a0@0F1a0d2-2:0^2/2b2=1#2@2_2{2}0g2 01313335372S3a3c1}040z3g3i1`3k2D2O013p0d2`1i2|0W2~3032340Y3z2#3B0t0M0@0M3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0t0m0@0m3)1b3+3l2;1u3o0r2^3O3r3S3t3U3x3X3{3Z3}0c0@0c422,3,2:3L3:4c3@3w3W364i393}0A0@0A4o443-473/493q3Q3s3u4w3`383!0H0@0H4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0s0@0s4W2E1l2*1a2V2I0G1;2N3.014x2U1r1i2)0g2+3j3*3I054x572b0w0G0/322D3!0F3r5f5h4g4y4-3c5l0h2g0g5o4x3Y4A5s1T0V3h453L0o0@0Y0Q594?4H2Y010y0@0h5L5d465O0S0Q0@1/0w0n2Q0k0g0b2B435a5N200?040q5T5F4 0S5Z0d1W0g0d0B5?5.1#5:0i0D5T0_5,5M4r5n015i2:3!3D3=0h6b4+5q3|3C1~5v5x4Q6m0t6g5D040h6x5S610/5H040Q495T6z4r5^0@0w6G5@4!0r5Q042Q6M6A3M0x0@0b1`1C606I4!5:5=685U3L0u0w3e6#4Z5O5:0p6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0i64666~6i5g6c0n5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0J3O0g0B0b0n0d5$0S5(2y0b6^7H1#0r0@0U7W6 3o5`5|5~7h4 5:0O7,4!756L7a6U5:0C7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040j7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0y1L1X8m6J8k8W6O0@020T0N0L8Z5O6-0@0I8*206P0@1`0G8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0t8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0t4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0t4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0R5l04030h0E2t5%0f2yaL4?0V5c4@564_531a0N4|bn2L2G8{bk0V4`670Y0!0$0k04.

Évaluations restantes : 5/5

.128013r5aSe )jsP4_k,(o8-myibw26u]:1d70vl;3t[pfcng=/h050E0f0L0d0v0I0j0g0P0I0d0j0j0S010L0v0N010406050j0A0t0t0d0b0u040e0q0I0A0/0q0Q050T0_0{0}0 0@0N04051f181i0T1f0@0E0v0H0%0)0+0-0)0Q0R0A0d0R0f0s0N0u0L0U160g0U0v0R0U0I1K0U0L0=050Y0w0I0f1r0*0,011J1L1N1L0L1T1V1R0L0b1g1F0%120j0N0d0Q0-0y011X1t010O0!0f0Q0d0t0f1R1?1^1}1Z201V23250=0a0g0k0b0q0N0q0j0v150Q0g0W1;0b0b0f0P2q18280Q1g0T1F2D1-1/1.1S0E2a1u0v0Q222n1R1o1q0(1Y2N2P0Q0q2T1R0N2w1g2B2D2*0^1@2r2V1~2Z0b0|0I1R0d1I2w0O0-030m0m0P2!0f1N2Y0q0s0D0D380=0D180d2+2.0?2-292:1Z2=2@2_2{0f2}012 3133352Q383a1{040y3e3g1^3i2B2M013n0d2^1g2`0U2|2~30320W3x2Z3z0s0K0=0K3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390s0l0=0l3%193)3j2/1s3m0q2?3M3p3Q3r3S3v3V3_3X3{0c0=0c402*3*2.3J3.4a3=3u3U344g373{0z0=0z4m423+453-473o3O3q3s4u3^363Y0F0=0F4D3G4o3k4G3K4I494K4b4M3@4f4P3{0r0=0r4U2C1j2(182T2G0E1/2L3,014v2S1p1g2%0f2)3h3(3G054v55290v0E0-302B3Y0D3p5d5f4e4w4+3a5j0g2e0f5m4v3W4y5q1R0T3f433J0n0=0W0O574;4F2W010x0=0g5J5b445M0Q0O0=1-0v0m2O0j0f0b2z41585L1~0;040p5R5D4}0Q5X0d1U0f0d0A5;5,1Z5.0h0C5R0@5*5K4p5l015g2.3Y3B3:0g694)5o3`3A1|5t5v4O6k0s6e5B040g6v5Q5 0-5F040O475R6x4p5?0=0v6E5=4Y0q5O042O6K6y3K0w0=0b1^1A5~6G4Y5.5:665S3J0t0v3c6Z4X5M5.0o6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0h62646|6g5e6a0m5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0H3M0f0A0b0m0d5!0Q5$2w0b6?7F1Z0q0=0S7U6}3m5^5`5|7f4}5.0M7*4Y736J786S5.0B7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040i7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0x1J1V8k6H8i8U6M0=020R0L0J8X5M6+0=0G8(1~6N0=1^0E8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0s8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0s4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0s4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0T5a4=544@51180L4`b92J2E8_b60T4^650W0Y0!0j04.

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