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

.128013g[r) ;/(DloF4,I6b=xa+5ut}P7e{À-h0Tmnkê^:SéNq.èy1cdz32à8ù_wvLpfO9RA]is050Y0C0y0u0@0k0^0f0X0k0u0^0^0s010y0@0-010406050^0x0J0J0u0d0V040P0l0k0x190l0K0f020u0J0-0g0f0;0C1j0d0S0x0C0^050h1g1i1k1m1e0-04051R1K1U0h1R1e0Y0@0+11131517130K0b0x0u0b0C0F0-0V0y0G1t0f0G0@0b0G0k1}0G0y1c050|0r0k0C1%1416011|1~201~0y2628240y0d1S1^111p0^0-0u0K170#012a1)010.0~0C0K1x0C242s2u2z2c2C282F0J2H040a0f0A0d0l0-0l0^0@1s1u0`2q0d0d0C0X2$1K2J0K1S0h1^2=2m2o2n250Y2L1*0@0K2E2Z241!1$122b2 310K0l35240-2+1S2:2=3i1f2t1u372A3b0d1j0k240u1{2+0.17030)0)0X3c0C203a0l0F0H0F0W1c0f0W1K0u3j3m1d3l2K3o2c3q3s3u3w0C3y013A3C3E3G323J0F2x040f0#3Q3S2u3U2:2~013Z0u3t1S3v0G3x3z3B3D0`3-3b3/0!3N0!3^2/3T1e3|3X173 410543453)473,303.3K0n3N0n4g1L4i3V3n1(3Y0l3r403#443%463+494v4b3K0w3N0w4B3i4j3m3}4n4L4r3*483F4R3I3K0q3N0q4X4D4k4G4m4I3!423$3(4)4u3H3/0B3N0B4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0%3N0%562;584F385b4J4o4q4N4s4P4+5j0F0:3N0:5o3{4!4l5t4{4p4}4O4*4a4-3L0H1c0W0H5G5q4#5c5v5N5y5P4,3/0W3M045+5X4E5Z5u4%5x4 5i4w3L3;0W3@0h3R4h3`1V3g1K352^0Y2o2}5J4*341#1S3f0C3h3T612;054*6i2K0@0Y173B2:5*3#6q6s5z5Q6v0f2P0C6y5(5B5,4g4@5s0L1c0`0.6k3=5:5J0K0.6N0@0X1_0y0l0J0@0C6Q6S5a1b040i6)6K3p1c3b0J0r2+1J4C626:2c6,0o6Q0f6*5s0K1c0X0@276(6{6l6}176,0e0O6Q1e7b6o1u6x016t3m3/3;5M7n5h5A5`2x6C2G6F507x245 3=0f7H736;040`0r1r717J2c0l1c0s7P7d016$1c5W7k7j3k3|7u0)6u3K4d4|7)6G5`4d7z2Q7B5_4S0F7-3^7H7I7W75042C0K7V5I5a7S047U7k72800r1c2O6/865s6,6.7k7Q4m6=6#6^1I8h598j1c0e858u2A880F8y5r2A7Y5-7i8t7m6r7o7*7q4x6w8L7v6A8P7?6E8M7:7`4y2=3R7~8c8i2A6M040*1|288D4#6N0C7N0y8:5J88020k0y0g8a3i8(8z3Y1c838J3}6,7h7#977)7+0F4U7.8R6z5)4T2y6D7^7w7`9g7}8%7~8n3~1c6$200C0x8_877T9C8v6-976T95309F8A1c0v9M947L8?7O8m7W7f9I9D040h0h9Y5s8G5~4Y9c9i9e4/9h9o8T0F4/8V9;9k9?7E8$9t7 8)2c8+0@6P8b9v8177799Q17880s903T928E9R6?8r6`7%a07e1c0c9%7K9y6%9B9Van016,0?9a9+aw6p9-8O0F539:8X7C7`539^aK7_5RaI9s9~8%9v8+2+0y0x0d84a57W0L0X1c0I0d1H8IaD8K6y9e5laJ8S9`5laOa_5Ba@aT9taW1c4+a491a676788/a%ax8{0b8~aa9w04aj6_ar6~apbl8o04at9Aboay1caAa/amaEa=aG5Da^9j5B5Da|bE5`bCb0aUag8;9S8@bgacbg81bravb67W889Pbb93178G3P9ba:0f9daG5V8Q9_6H5TbH8Y5Rb/8#7G9~b2043F0^7abyahao04aB4Db+b-2u5*6I3v7/aLb_3Mb@cgcc9|b|bMbN9J829Lb#c401bSctbObVbR1c8Ccx5Jb(bx6j7(aFcb3K5}b:aP9pb_7y9ncO9=cMb{aVa(1caYa!a$bXaxa)1c0m40c1bg0X5,030f2!0f1`0K02030!0:0g3v2t102m0l0x0+0QcG620h6n636h656e1K0y68df2{2?0u792=661Q7l3}2+0J0)0.0u0L0C0)0G7-1C1E1G1I0fc7d81Y0_1#3}0u0Y0J1t2#0@1`300.881QdMdOdQ2$0F190y2k041C6Y0C0dd,0f2t0d0f1!6Y0l6!6$7adJ1R0p0kc=001/2#d?000x1u400b4I2#0G2Q2L0@dE0T0f0,292j0C0u0xd:0d0@102Ed:1k1x0U2m290Y0le41fd21,040l271}0u6!0@ds2E0y0f0Mez0f2m0@d61LeF0b040T1V3U1R0E110G0udEb,0y0Q0deLdS0K0oc@1uc1d?1D2u2(c?130f0+409Ad=0XePe=280f1IeQ0Q0bf50f0$0ff26m3E04a8ba6ndGe%1e0x0k3U2004c?d30@e_1`2+0K0+eC290@1i0Q1!eL1DeP726na,a.d9fn1Kfy1efyc?3be^110{0y29fp29fdc=eCeQ7hfvfx0@fz0x0-e;au2+fifk3vf428a!f(0K2mfh0Ob,e0dv1re+d-d,d=0Y2u10f2d;19eA2W2#eAepemeo0f6.6n7Mgd0s0fbV0f0v3O1K6n8x0hfY05fydUf|f629fjf2g2f6g5g7fbg90~0fgceQggggd?gjg0ev0dgn0ffg0xd/0Ygsdl28gugwfn830fgAgC0FgFfV0`04gIgK0hf?7jh7h91T040,3v0Z1teA292+g%0G290i0k000Q0X1keQf929fmh496h36hfceQhy6hgy8^hBh5c=hkfM0xe4fj6Ye-1He/e;e?1`g9fA1u83e4d;0f0ufHeNfRg|301v8}1AhHgGfne_0X00f.e.fl6nf,h?h46Ch`0^eQd0g)0Kgkelg^en0xei0/e{4IeQ2(f20rd312f-eQfFh*hx6nc+0 7a6ne$1X3U0hdodK365adNdP0KdRdT6UdW1TdYiHiJ0Kd$2#d)0R8qf~1j0tfK40e}eUd30d102(ilg;286`d}042V32i80fe70fhshue530d@fJiI19i#hFcr1uh1h=hJi`fge0fj9v1kec1jf*0t1c090i5V0N0:09gI3ie_0if80f1G0@fci4jw1.0K2}0J0Mee2m0U100be=jD0eiyi:0jg*fb0-eNhj10ht0^fD0(g+f,i2f.i63f0Qc1g60CfD1u0d0Q40eseld3i9d1i(i*29i,in102Y15b91IjP3Uhcfy0=ep6gd{d=6!a!j:h(i^1ui{g-fcfGeN1`2(jeer1^jh0Cjj04jl090.e=0X0Djn0:0z0D0#0zjq6Qh^i3eQfj1!f~ks7WjfkvfOkyjl0w0f09192Q10jn0%kM8mgJf^fZf^kbe}0xiZ0UjHi(ki3vi_kmhvkp2W2%hxkVkuedkYjk0ikBkD0Dk#k%fKdFk+kIkKk-91h_f.kRjVcpiFl7kwkZ0i0#lfk(li0H0N0Blm6jk/f@040=30c?f0hOf*0f0TlRfXk:gLk=gsfF19k`j_khe`kjk htkn0Yh`l21`ktjgl9kzlbkC0ukEkGlk0N0D0!0H0zkLjraflojAlqkTl-0+kq1u0WiyhbfwdplKi8fCi710e72920i4hjeU0}0kfbl:kXjilakGlF3`e_eugu0-1qetl.1ul i%a!101`0^0}eQf1hr0k0Q2Qg6h,h4h j9j)j=j-0yk77jiCiB0{mt0^04.

Évaluations restantes : 5/5

.128013g[r) ;/(DloF4,I6b=xa+5ut}P7e{À-h0Tmnkê^:SéNq.èy1cdz32à8ù_wvLpfO9RA]is050Y0C0y0u0@0k0^0f0X0k0u0^0^0s010y0@0-010406050^0x0J0J0u0d0V040P0l0k0x190l0K0f020u0J0-0g0f0;0C1j0d0S0x0C0^050h1g1i1k1m1e0-04051R1K1U0h1R1e0Y0@0+11131517130K0b0x0u0b0C0F0-0V0y0G1t0f0G0@0b0G0k1}0G0y1c050|0r0k0C1%1416011|1~201~0y2628240y0d1S1^111p0^0-0u0K170#012a1)010.0~0C0K1x0C242s2u2z2c2C282F0J2H040a0f0A0d0l0-0l0^0@1s1u0`2q0d0d0C0X2$1K2J0K1S0h1^2=2m2o2n250Y2L1*0@0K2E2Z241!1$122b2 310K0l35240-2+1S2:2=3i1f2t1u372A3b0d1j0k240u1{2+0.17030)0)0X3c0C203a0l0F0W3J1c0f0W1K0u3j3m1d3l2K3o2c3q3s3u3w0C3y013A3C3E3G323J0F2x040f0#3P3R2u3T2:2~013Y0u3t1S3v0G3x3z3B3D0`3,3b3.0!3M0!3@2/3S1e3{3W173~400542443(463+303-3K0n3M0n4f1L4h3U3n1(3X0l3r3 3!433$453*484u4a3K0w3M0w4A3i4i3m3|4m4K4q3)473F4Q3I3K0q3M0q4W4C4j4F4l4H3Z413#3%4(4t3H3.0B3M0B4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0%3M0%552;574E385a4I4n4p4M4r4O4*5i0F0:3M0:5n3`4Z4k5s4`4o4|4N4)494,3J0H1c0W0H5F5p4!5b5u5M5x5O4+3.0W0W5T3O0h3Q4g564D5Y5t4$5w4~5h4v3J3:0W3?5.3^2;1V3g1K352^0Y2o2}5I4)341#1S3f0C3h3S5:634)6j2K0@0Y173B2:5)3!6q6s5y5P6v0f2P0C6y5%5A5+2=5/4?5r0L1c0`0.6l3;5=5I0K0.6O0@0X1_0y0l0J0@0C6R6T591b040i6*6L3p1c3b0J0r2+1J4B3_6+5r6-0o6R0f6~6=040X0@276)6|636;2c6-0e0O6R1e7b6o1u6x016t3m3.3:5L7n5g5z5|2x6C2G6F4 7x24610f7G737d4l6O0C0r1r72742c0l1c0s7P7J016%1c5V7k7j3k3{7u0)6u3K4c4{7)6G5|4c7z2Q7B5{4R0F7-3@7H7I5H590K1c2C0K7V805r7S047U7k7 585r0K0r1c2O6:872A6-6/7k7Q7K046@6_1I8k8e8m1c0e868x7R1c0F8B5q2A7Y045-4X8w7m6r7o7*7q4w6w8P7v6A8T7?6E8Q7:7`4x6J3;7H8q016N040*1|288G4!7L7N0y8?5I89020k0y0g8b3i8d8H3X83308N3|6-7h7#997)7+0F4T7.8V6z5(4S2y6D7^7w7`9i7}7~8+7W82046%200C0x8{5989923S949a1c8o7%8l9604849E881c0v9S750`8_995I7f9!9F1c0h0h9%5r8J608M8p7(9k9g4.9j9q8X0F4.8Z9`9m9|7E3Q9v9w9O178.0@6Q8c8,9y77799W8D8a9H3_9J6U6?6$8u6{9N8C176-0c9,759A6(9D9;a6016-0?9c9:ar8O6y9g529_8#7C7`529~aO7_5QaM9ua47~8,8.2+0y0x0d85ab7W0L0X1c0I0d1H7i9e9?8S0F5kaN8Wa05kaSa}5Aa{aX9va!1c4*aa93ac1cae8=a+aC8}0b90ag8r8t6`aw7e1cavaBas3}1cay9Cboat1caFa?bsaJ8Q9g5Ca|9l5A5Cb0bJ5|bHb4aYal818^7Obfbt9Gbkbu9z0~azbZ899VbW95178J8L4CbD0f9fa_5U8U9 6H5SbM8$5Qb^8)bRb6043F0^7aaI9K04aGb:c8b?2u5)6I7t9kb~cg9o7AaT9rb ch7FbRa5bt9y9Rb+3|bYcyamb#9BaAba7W898FcB59b.bCcda^cf3K5 b_co9{cSb}aPb 7scs7Gc3a$a(a*cGaCa-1c0m3 c6cN6k0h6n646i666f1K0y69c}2{2?0u792=671Q7l3|2+0J0)0.0u0L0C0)0G7-1C1E1G1I0fcb6}1X3T353|0u0Y0J1t2#0@1`300.891Qdudwdy2$0F190y2k041C6Z0C0ddQ0f2t0d0f1!6Z0l6#6%7a1Y1T040p0k0f0^001/2#dX000x1u3 0b4H2#0G2Q2L0@dm0T0f0,292j0C0u0xdU0d0@102EdU1k1x0U2m290Y0ld;1f2m1t0b040l271}0u6#0@da2E0y0f0Mej0f2m0@0Q2/ep1,040T1V3T1R0E110G0udmb=0y0Q0dewdA0K0o0f1`c6dX1D2u2(2!0f130f0+3 9CdW0XeAeZ280f1IeB0Q0be@0f0$e:3v056nbd7a6ndoeO1e0x0k3T2004e/0l0x0@e%1`2+0K0+em290@1i0Q1!ew1DeA736na:a=c@3E2=fj1efje/3be$110{0y29fae~0^eB0^emeB7hfgfi0@fk0x0-eYaz2+f4f6e=e@a(fQ0K2mf30Ob=d,dd1reSdRdQdW0Y2u10e;dV19ek2W2#eke9e6e80f6/6n9Yf 0s0fbwe90v3N1K6n8A0hfK05fjdCf,e^29f5e;e?28f?e`f^e|29f{0~0ff~eBg2g2dXg5f:g86(0ff20xdT0Yged328gggifI840fgmgo0f0FgrfH0`04gugw0hf$7jg{g}d)0,3v0Z1tek292+gR0G290i0k000Q0X1keBe{29f8g,98g@6ie~eBhlg^gk8`hog_d-h7fyfneBf56ZeU1HeWeYe!1`f{fl1u84d;dV0f0ufteyfDhm1u8~90e+9Zhwe%0X00e 0feVe;hs6ifagsfI6Ch)fWef10g40Kg6e5g(e70xe20/1ufY0deB2(e;0rfm12290{0ffrhThk6nc/0 fbfIeNdr7jd60_1#dGdx0KdzdB6VdE1TiudIe#dK2#dN0Raof.1j0tfw3 e+eFfm0dh`29iag!286{d(1R2V32h|0fd@0fhfhhd=30dYfviw19iOh.9Q30g;h!bVfcf1iOf58,1kd|1jfS0t1c090i5U0N0:09gu3ie%0ie`h+fnfVeB2m0U100beZ0K0Y0eioiZ040jgUe}0-eyh610hg0^fp0(f:fU0Kh@eB2t103f0Qc6f^0Cfp1u0d0Q3 ece5fmh}106#a(iT0fiVicjP2Z2!790^jv3Th0fj0=e96hd$dWj)0djVhRi(1ui+i6e~fsey1`2(j1eb1^j40Cj604j8090.eZ0X0Dja0:0z0D0#0zjd6Rh%jMf/1!f.kc7Wj2kffAkij80w0f09192Q10ja0%kw8pgvf(fLf(j{e+0xiM0Ud~k0k23vi)k6hik92W2%hkkEked}kHj70iklkn0DkKkMfwdnkQkskukS93h(h*f5kBk;aCkFk@j5k_0#k~kNl10H0N0Bl5c?gwj`30e/e.hB290Tlx1KlqkXgefr19k$j#a(k)k4i*hgk70Yh)k.1`kdj3k^kjk`km0ukokql30N0D0!0H0zkvje9Il7h^l9jCd=2E0+ka1u0Wiog fhd70=lsfogTi%d@2920fWh6eF0}0ke}lRkGlflUkqlo3_e%eegg0-1qedlP1ul%iQj*e(i40}fX0@e:he0k0Q2Qf^hVg^h:hwjleajReAj@iq6fiq0{m90^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

.128013Eg[î r;)/(lDo4,6Ib=a+x5utP7e-h0TmnCk:SéNq.èy1cd32à8_wvLpf*O9R]is050V0C0z0u0/0l0:0f0U0l0u0:0:0t010z0/0(010406050:0y0H0H0u0g0S040M0n0l0y140n0I0f020u0H0(0h0f0-0C1e0g0P0y0C0:050j1b1d1f1h190(04051M1F1P0j1M190V0/0$0|0~10120~0I0c0y0u0c0C0D0(0S0z0E1o0f0E0/0c0E0l1^0E0z17050@0s0l0C1Y0 11011@1_1{1_0z21231 0z0g1N1:0|1k0:0(0u0I120X01251!010)0_0C0I1s0C1 2n2p2u272x232A0H2C040a0f0A0g0n0(0n0:0/1n1p0=2l0g0g0C0U2X1F2E0I1N0j1:2-2h2j2i200V2G1#0/0I2z2U1 1V1X0}262`2|0I0n301 0(2$1N2+2-3d1a2o1p322v360g1e0l1 0u1?2$0)12030!0!0U370C1{350n0D0X0D0T170f0T1F0u3e3h183g2F3j273l3n3p3r0C3t013v3x3z3B2}3E3E3I0X3L3N2p3P2+2_013U0u3o1N3q0E3s3u3w3y0=3(363*0W3I0W3.2*3O193=3S123^3`053|3~3!403%2{3)3F0o3I0o491G4b3Q3i1Z3T0n3m3_3W3}3Y3 3$424o443F0x3I0x4u3d4c3h3?4g4E4k3#413A4K3D3F0q3I0q4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0B3I0B4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0Z3I0Z4 2,514y33544C4h4j4G4l4I4!5c0D0,3I0,5h3;4T4e5m4;4i4?4H4Z434$3G0F170T0F5z5j4U555o5G5r5I4#3*0T3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0j3M4a3:1Q3b1F302:0V2j2^5C4Z2 1W1N3a0C3c3O5`2,054Z6b2F0/0V123w2+5Z3W6j6l5s5J6o0f2K0C6r5X5u5#494-5l0K170=0)6d040f5)5C0I0)172{1V0U0C6J6M5316040k6V6D3k172e0C0u0y6#5B6X170p6J6L6$3T170U0/226U4v5{6@126Y0i0L6J196~6e3=6q016m3h3*5=5F7a5a5t5:2s6v2B6y4_7k1 5^6K0f7u6W5l0I6G0C0s1m6=7w2v0n170t7D70010H0/175P773P7Q5)7h0!6n3F464=7U6z5:467m2L7o5/4L0D7Y3.7u7v7K7y042x0I7J6.5l7G047I7Q6?7{3k0s172J6-525l6Y6!7S7=6(0u6|6+875k2v727`887F170D8m8j277M5N758i0f7U7W0D4r7Z6k7b6s5Y4q2t6w7*7j7,8C7/7:7E276F040#1@238r4U7z7B0z8Y5C7}020l0z0h7 3d818n6^7@2{8x5C6Y747Q763f798E7c2p3*4N8D8L6t4M8J7n8F7#7,948P7:8Q8d047M1{0C6,808R127}8.3O8:8s71178b8~828=0=8#8%537}0v9E7x177^8^6/040i9I8o040j0j9Q8t7N045@4R8x8z7d4%6p908G5u4(7(6x9b7p7,4(2-3M9g9g9p018T0/6I9o9i6`6|9V9q178*8,a43@8e8g9n9z8;9w040d9M9J9j0_0/9maj8k170.8{9!8c4T9$923F4|959:7+5K4|9.968H0DaA9f9_9`9i9La09Aa57~a97?9kanad9t9{7}8qaQaf7L9X3K8|9#9*8A5eaB7i970D5eaGaC8M5Ka:aLaNaR9|174!9 8/9{7?a28Xa%9v019r9s3:9u8Z046)8hava(6YaiblbbaVamaobp3?6Yas8wbuax0I3*5wa;9+5:5wa_a=aIbDa~aMbg5C8T2$0z0y0g7_babhaWbtauae1pbA5Z5MbE9c5K5O997)a`a?b-9@7taM9{8T3A0:6}b#bv17at4wbza.9%3G6B3q7!9;b,3HbIbF7,5!7r9^bNa a(7?9C7CbW8(7HaU17bYaYbfa!179Hcp538u5$byb~b%3F0T7fc89*b+5Z7l8Kb:aIcIchb@bO53bQ0?bTbVb57K0K0U170O1ob}c23f0j6g5|6a5~671F0z61c^2?2.8f232-5 1L6hbb2$0H0!0)0u0K0C0!0E7Y1x1z1B1D0fc15{1S3P303?0u0V0H1o2W0/1=2{0)7}1Ldpdrdt2X0D140z2f041x0U0E0C0gdL246S1;0z0n7Mdh8y0z0N0g0u140$240L0f0Y2l0I2A0e2h6}1T1O040r0l0f0:001*2W0f2Z0ld|0l0c4B2W0E2Ld 242$dPdOdMd 0/dL0ndTdV1C2G0/dh0Q1Q7Rd10;1WdBds0Idudw6Odz1OevdDdvbBdGdI0%3qebdMeddQ24e16RegdQ0y0fcueqd20%240U3_0U0yd_e000eR6Td eUcueVdZ2W24dT1m3Y0n0/0{dh0ldh0{3y1d2z0@0/2$0:0Q0f0r6`0f1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Db0br9lcv2,cV7|crcA899xap9B7Acoc#b09Gcs8?c!6c7K8lfE9R9Ta9cC9Z6cc/3z04epdmd20+0g0pd 2pf1dNf50I0{fmfo0{2Zff0cd!1I2X2lf30f230f0Jf-0~0ff50lg40=0{f4an0gge0:0zg30/7MdY0Cf90Je!e$e(6L4Zfl2pfn1+1-0Sfr2a1|1~d3bXbsfz6KcxaTfU278afH4f8!fKaZ7KfNgOgSfPgR01fTfLa(7}fWgYa)17fZdl6g0f0(9mgk2o0gdye|0f0C0w0U0N0=0g0|0?0ze@0^gbePgme?f90b1p3Y0)0?f-2Vg3di0=0y0w8y0I6Sdifj2Z5Cfm1)gAfq291`gFfvclgT8$7Sf#0=6K0?gvfkhwgyhyfpgChBftgGb69K8@hIg;0:1ogkf}2p0V0:g79mh3h$g2hue!53hxfogBgDhC2chEbqhGa9gXg(h g!h!f$g=g@d 0N2o10dNg33q0$3_h.glgngpeXd?0mf/h40|0 fd3igtg4eQhreSe.eVgJg}1p1mam0:2pgkg80~0g1+bTe9g3e+0Ih60gihh9djhNhvh@hQh_hAfshDgH6NctgJi1fDi3bhcnhHi;cq04czi^9N9yfRfwhYfQcwgW8pfOi?g#g%gVfM17g+i|5lfY6VhJ6af(d=1Mipf?hlis0{3a0Nb|iTh-g=2R220Re82|d`242Tb|g=ite#f,iE2P1/1;0Ih-geiTgg0{0I00h%jHf`h70_ixhbh6f90G0ne_g{h,0f0M0/iR1=0uihd~1eex0(e(0Ne9jUdU0sf70f0)0lei0@iTf@jEjy0ljA24b|d!d~0u0(g_eUf2e8g_g}0w1y0(g48{d=do5Cdqeweyhf0w1skt2MdAkydCexdEeH2M0bkr1tb9kweuhP1%hRgB3y1phUi*9{2I2z2B170AjN1=0J1oh$g40M1D2V1o6V69d33/6ec:8 6r6n0W3G9)aH4`l2cccPbJl6l35V5.a{7-l3b?9{0c6Y020c8,lmloln1vg#cmfJi@jag)i:lxbb0H6P9Y0Q7Pje9R0*0*fXa*0F0X48a,c3l07dl2cJ8ycLcalgcO9ala3)lU2t585HlYl(li7Klka6lrlp0hl?6Lbui,i58/7;jbgNlH8tlD0XlFi/04lJlL5NlNlPm1aSi{lA3?cCa+b!i 6ic492l27.cKl5l%7-b.9/l$44mpl)4Xmx3Dmzl.b0l:04l?mJlrl_b~l{j7g,i2mgl{aPl}9{0U5#03iaicb|2LiTiQe#2o6`dYcEmlb$mnbBl28OmrcQlb4rcdcMm?mA5-mClg8O7slj7}dxm.6 awm;lg9em^n1l24Nm|l,0Dnhl*5Wnj9en4l/lll=nt8,mMm/b 6Zlti0mQcyfOmUnx8_179PnC9Sm99Y6=fB2vmX17mZ0Vib261yf4m)kj0um,j~k6ghiQg8h:2Ln878nalSmo0D9?7glXaDlg9-l9cemDn?m 59n~n{cTn56Q6On.gHb%l2aKneo3ocmvmsmyaJo1l+n`ogmFa(mHmKlqnvnA04mPmdbcnDg,gQl`537?nFj3l a$oylu9DoDfF9Om69Ug,jglQcFnbl2a}oem}a@ohm_mta^nmle6toXo5l/7}0Z0Q0,0Z0Z0o0q0x0q0B0o0W5!0x0Z0C0v0W0F4~oUf!c:1S5}0jespd6776pe0=ga0:04.

Évaluations restantes : 5/5

.128013Eg[î r;)/(lDo4,6Ib=a+x5utP7e-h0TmnCk:SéNq.èy1cd32à8_wvLpf*O9R]is050V0C0z0u0/0l0:0f0U0l0u0:0:0t010z0/0(010406050:0y0H0H0u0g0S040M0n0l0y140n0I0f020u0H0(0h0f0-0C1e0g0P0y0C0:050j1b1d1f1h190(04051M1F1P0j1M190V0/0$0|0~10120~0I0c0y0u0c0C0D0(0S0z0E1o0f0E0/0c0E0l1^0E0z17050@0s0l0C1Y0 11011@1_1{1_0z21231 0z0g1N1:0|1k0:0(0u0I120X01251!010)0_0C0I1s0C1 2n2p2u272x232A0H2C040a0f0A0g0n0(0n0:0/1n1p0=2l0g0g0C0U2X1F2E0I1N0j1:2-2h2j2i200V2G1#0/0I2z2U1 1V1X0}262`2|0I0n301 0(2$1N2+2-3d1a2o1p322v360g1e0l1 0u1?2$0)12030!0!0U370C1{350n0D0o0D0T170f0T1F0u3e3h183g2F3j273l3n3p3r0C3t013v3x3z3B2}3E0D2s040f0X3L3N2p3P2+2_013U0u3o1N3q0E3s3u3w3y0=3(363*0W3I0W3:2*3O193@3S123`3|053~403!423%2{3)3F0o3I0o4b1G4d3Q3i1Z3T0n3m3{3W3 3Y413$444q463F0x3I0x4w3d4e3h3^4i4G4m3#433A4M3D3F0q3I0q4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0B3I0B4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0Z3I0Z512,534A33564E4j4l4I4n4K4$5e0D0,3I0,5j3?4V4g5o4?4k4^4J4#454(3G0F170T0F5B5l4W575q5I5t5K4%3*0T3H045$5S4z5U5p4Y5s4`5d4r3G3,0T3/0j3M4c3=1Q3b1F302:0V2j2^5E4#2 1W1N3a0C3c3O5|2,054#6d2F0/0V123w2+5#3W6l6n5u5L6q0f2K0C6t5Z5w5%4b4/5n0K170=0)6f3-5+5E0I0)172{1V0U0C6L6N5516040k6W6F3k172e0C0u0y6$5D6Y170p6L0f6X5n0I170U0/226V4x5}6%276Z0i0L6L19706g3@6s016o3h3*3,5H7c5c5v5=2s6x2B6A4{7m1 5`3-0f7w6^6(040=0s1m6?7y270n170t7E72120H0/175R793P7R5+7j0!6p3F484@7V6B5=487o2L7q5;4N0D7Z3:7w7x7L3_172x0I7K6/5n7H047J7R6@7?0I0s172J6.545n6Z6#7T836)0u6~6,885m2v747{892v7~0D8n8k277N5P778j0f7V7X3E6r6m7d6u5!4s2t6y7+7l7-4t2-3M7;827|2v6H040#1@238s4W6I0C7C0z8!5E7~020l0z0h803d8S8o3T7^2{8y5E6Z767R783f7b8E7e2p3*4P7!938G5w4P7)6z8F7$7-977:8R7;7F4h177N1{0C6-819m017~8;3O8?8t128b8{556`7A8%7D9t7?7~0v8*9E8_7`8d8T73170i9N7}170j0j9W2v8v045_4T8y8A7f4)8D8L6v9.9d9:8H0D4*8P7v9k9z3^8V0/6K9J9S9n046|6~9#7G178-8/a9a56*8i9R8@9B170d9D6_9o0_0/9ran8l170.8~9*ai1p9,953F4~989@5w4~9?9f7r7-aE9j9}8R9u9F7_ae9v7IaU9F9par9s8=9u8qaU9%3K8 9+998B5gaFaK7,5M5gaJ7k9;0Da:aO9k9u8V4$a2a$8ea66}8Za3ajaV7 9x3=9~6O8f8ha#6e7?6Zamaz8#04aZasbo8|avax4yboaB0I3*5ya;a`9^5ya_9a5=bCa~aPbf558V2$0z0y0g9Qb4a47@bqaqbsay914Vbz5#5ObDbI7-5Q8J7pa=8M5Mb.9{bMb0173A0:6 b$ba8}8xbya.9-3G6D3q7#aLb?3HbH9gcb7t8QbM9lb57B9IbVba9waXap9qbjbea%179Mb99A01a*c2b aAc4aC5?9/b;a{5^b/7*cJ9^cLb^cjbWbP0?bSbU9yb00U170O1ob~cY7?0U5%030f0M0/0f1=0I02030W0,0h3q0gar1p2h0n0y0$0NcC6e0j6i5~6c60691F0z63dd2?2.8g232-611L6jcz2$0H0!0)0u0K0C0!0E7Z1x1z1B1D0fbw5}1S3P303^0u0V0H1o2W0/1=2{0)7~1LdKdMdO2X0D140z2f041x0U0E0C0gd*246T1;0z0n7NdC8z0z0N0g0u140$240L0f0Y2l0I2A0e2h6 1T1O040r0l0f0:001*2W0f2Z0leh0l0c4D2W0E2Lek242$d.d-d+ek0/d*0nd=d@1C2G0/dC0Q1Q7Sdm0;1WdWdN0IdPdR6PdU1OeQdYdQbAd#d%0%c|2%d+eyd/24em6SeBd/0y0fbr9sea1M0%240U3{0U0yeeel00e:6Ueke?e^e@d{2W24d=1m3Y0n0/0{dC0ldC0{3y1d2z0@0/2$0:0Q0f0r6|c;1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DbWaYbZct2,bN9X7 aU9Cbt9O9G8(aU9Lcq04aTf$8a9Uf*9Y9!cy3^9%9)d66ieKdHdn0+0g0pek2pfnd,fr0I0{fIfK0{2ZfB0cd|1I2X2lfp0f230f0Jg30~0ffr0lgn0=0{fqar0ggx0:0zgm0/7Nd`0Cfv0Je}e f16@4#fH2pfJ1+1-0SfN2a1|1~dobpe^f=fZf^bu6!at8^f(cmc)bWf+g)f%f.cD3^8mg?fY9Za)7O9(6Wd73z3-0(9rgD2o0gdTfi0f0C0w0U0N0=0g0|0?0zfd0^gue.gFfcfv0b1p3Y0)0?g32VgmdD0=0y0w8z0I6TdDfF2Z5EfI1)gTfM291`gYfRba9Fcl8)7Th30=3-0?gOfGhMgRhOfLgVhRfPgZaR9Ph26ief1ogDgg2p0V0:gq9rhj0:d?ethKe}55hNfKgUgWhS2chUczhW9HhYcnczg=ikbpg^f|h40fh61mek0N2o10d,gm3q0$3{i1gEgGgIeLdn0mg5hk0|0 fziN0lf0gne/hHe;f7e@fUhd1p1maq0:2pgDgr0~0g1+bSeugmf40Ihm0giChpdEh(hLi8h+iahQfOhTg!bgbYcsg%bdfWh=g.ijg:cocwf!178cg_j5ipcu9K178rg|7zhXg,ak049Vjraa04g~jy7Mh0f{dGf}iIebiKg9hBiN0{3a0Nb}i?i0is2R220Ret2|ef242Tb}isiOe~g2i!2P1/1;0Ii0gxi?gz0{0I00h`j(gdhn0_iThrhmfv0Gd1hmhbh c.c:em1=0uiCej1eeS0(f10Neuj^d?0sft0f0)0leD0@i?gaj#jV0ljX24b}d|ej0u0(h9e?8~eadJ5EdLeReThv0w1s0(d%dVkMdXeSdZe$2M0b0w1ykTe9dIePh*1%h,gU3y1ph/j39u2I2z2B170Aj.1=0J1oi3gn0M1D2V1o6W6bdo3;6gd8926t6p0x3GcIbE4|lhcc8KcOllli5X5:b=0Dlmcgj4550c6Z020c8/lClElD1vjubXjtjCbbj96M7?0H6Q9(0Q7Qin8+170*0*g 5P0F0X4aa,c3lf7flh7hc899celv3+cM9elk3)l.2t5a5Jcal?7h7u9ulAablHlF0hm86@f/7zjmfW7=g;aWlMlR170XlUg%lZl#5(l%l)lW55imjeczcBl*g_b(lh7/l:aGl{7.l^mG46mDl}4Zl`mLmI9{m4lBm7mV8/mbjkf%lLmufYcxm$md8`81fX2vc+17c-0Viw261yfqi:e~2o6|d`d571b%cFbAlh8O7il;m0n4mJlpmH4tlsmP3Dn9mS7?ep6R6Pm 7an1l,95lh9imFnbmQ9clonfl?9cl~5Yn8lvlxmTm6lGnJlImc9Tg+nMa5m#mx3^mwjnfSh?nP01g{m)jzf@n#jDml6?m-27m/04m;m?iy2Li?m`kF0um}kkksgAi:gri3fpnng!mC9_ljb,ngo6cdnE4*neo8l?9`6EbWnk04dSo37Un2l?aNnunzlhaInyofoumN5/ot0DaNm3njmUnKmalJihf)lMnUjabljioJnXn(bbjqoToKg/n0c0f;oM9YmqjF5ka-nqn3a|o7l=lha^owo:o.oeo@a}oEoj7~0Z0Q0,0Z0Z0o0q0x0q0B0o0W5$0x0Z0C0v0W0F50mAiqh#d9dl6978eN0jpq0=gt0:04.

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

Text Only

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

.128013kg[: r);S/(lo4y,6b=ac1+5ujd3t2_Pw7evp-fhmn]is050B0J0D0u0S0m0T0f0v0m0u0T0T0t010D0S0L010406050T0z0P0P0u0g0p040j0n0m0z0.0n0Q050k0^0`0|0~0?0L04051e171h0k1e0?0B0S0K0$0(0*0,0(0Q0c0z0u0c0J0M0L0p0D0O150f0O0S0c0O0m1J0O0D0;050X0s0m0J1q0)0+011I1K1M1K0D1S1U1Q0D0g1f1E0$110T0L0u0Q0,0E011W1s010N0Z0J0Q0u0P0J1Q1=1@1|1Y1 1U22240;0a0f0G0g0n0L0n0T0S140Q0f0V1:0g0g0J0v2p17270Q1f0k1E2C1,1.1-1R0B291t0S0Q212m1Q1n1p0%1X2M2O0Q0n2S1Q0L2v1f2A2C2)0@1?2q2U1}2Y0g0{0m1Q0u1H2v0N0,030F0F0v2Z0J1M2X0n0M0I0M0w0;0w170u2*2-0=2,282/1Y2;2?2^2`0J2|012~3032342P370M1`040E3d3f1@3h2A2L013m0u2@1f2_0O2{2}2 310V3w2Y3y0C0;0C3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380o0;0o3#183%3i2.1r3l0n2=3L3o3P3q3R3u3U3@3W380y0;0y3}2)3(2-3I3,473:3t3T334d36380r0;0r4j3 3)423+443n3N3p3r4r3?353y0I0;0I4A3F1i2%172S2F0B1.2K3*014s2R1o1f2$0J2(3g3$4S4s4-280S0B0,2 2A3y3a4H4@4_4b4t4M383a0f2d0J504s3V4v391Q0k3e403I0b0;0V0N4/2B0f5h4#0Q0N0;1,0S0F0T332w2y3~4S4C2V010:040l5n4=415F0Q5u0u1T0J0u0z5K5q4D5G0;0h0e5K0?5C2B5h4 014`2-3y3A3.0f5+3=4c533z1{57594L3^5`2C3e0f635p5E1}5j040N445K654m5r0;0S6c5W5F0n0H6g165(046d3j5X0Q0s0;0g1@1z5V661Y5H5J6p6j2:6v042c6A6e5X6D6L6s5N5P5R5T6P5M1}5H0h6i6B0,0n0;0M6!6M5F0P0S3b6V3I6Y5#6p5%2+3H5?5x5.383Y4~4^5,515b3X5{2358725a4u75616q647f6G3l6g0F6-0Q6h6p6r6W1Y6%040t6*6Q2:6g5$6:6{4{3_3o6{7a5_3`56775}5^5 3`7d7f7g6#01686a0g7v7q3+0;0A7X3I6l6n7$5r6I6x1v0J6:4#6O6F7S5O047n2)7p7%0;0x7*5X6-6/7?6+6X0;0q805N6I6K847w6C0;6E6_857i041)5S5U8d7Y5Y040h5!7z8p5=715-1@3y4g707L525 4g7J248E744f5e627Q8P7h0,680S5m7o8R3J6S1U6U8w7;0;0d7:6t7!8*5F5H0R891}7s020m0D0i8;8k8m8#8i8e0,5H8)8$8+7_7k2N7`4.7S8/6?4k7A8y6|8A4w7E9g7G5 4x8I785@8F4e0M4x7P8P9x638X7^5w7l993F7|4#7s7u8W7@8,6@9f507C379k8K7b384O9p9T5_4O9w8Q9L8l5Q8!8o8 8q928-7x7_9/8f040R889K8j7Z9(6T9+9a9{8r939,4n7j9D9=910;8:9`90019I8{9|8}9 5Da19.946R96a7an869@9_7{9A8Z8na8a2az9Baz8/8v2+0k4;4T4,4V4)170D4YaN2I2D9)aK0k4W5%0V0X0Z0T04.

Évaluations restantes : 5/5

.128013kg[: r);Sé/(lo4y,6b=ac1+5ujd3t28_Pw7evp-fhmn]is050C0L0E0v0U0n0V0f0w0n0v0V0V0u010E0U0N010406050V0A0R0R0v0g0q040j0o0n0A0:0o0S050l0`0|0~100^0N04051g191j0l1g0^0C0U0M0(0*0,0.0*0S0c0A0v0c0L0O0N0q0E0Q170f0Q0U0c0Q0n1L0Q0E0?050Z0t0n0L1s0+0-011K1M1O1M0E1U1W1S0E0g1h1G0(130V0N0v0S0.0F011Y1u010P0#0L0S0v0R0L1S1@1_1~1!211W24260?0a0f0I0g0o0N0o0V0U160S0f0X1=0g0g0L0w2r19290S1h0l1G2E1.1:1/1T0C2b1v0U0S232o1S1p1r0)1Z2O2Q0S0o2U1S0N2x1h2C2E2+0_1^2s2W1 2!0g0}0n1S0v1J2x0P0.030H0H0w2#0L1O2Z0o0O0G0O0x0?0x190v2,2/0@2.2a2;1!2?2^2`2|0L2~01303234362R390O1|040F3f3h1_3j2C2N013o0v2_1h2{0Q2}2 31330X3y2!3A0D0?0D3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0p0?0p3%1a3)3k2:1t3n0o2@3N3q3R3s3T3w3W3_3Y3a0z0?0z3 2+3*2/3K3.493=3v3V354f383a0s0?0s4l413+443-463p3P3r3t4t3^373A0K0?0K4C3H1k2)192U2H0C1:2M3,014u2T1q1h2(0L2*3i3(4U4u4/2a0U0C0.312C3A3c4J4_4{4d4v4O3a3c0f2f0L524u3X4x3b1S0l3g423K0b0?0X0P4;2D0f5j4%0S0P0?1.0U0H0V352y2A404U4E2X010=040m5p4@435H0S5w0v1V0L0v0A5M5s4F5I0?0h0e5M0^5E2D5j51014|2/3A3C3:0f5-3@4e553B1}595b4N3`5|2E3g0f655r5G1 5l040P465M674o5t0?0U6e5Y5H0o0J6i185*046f3l5Z0S0t0?0g1_1B5X681!5J5L6r6l2=6x042e6C6g5Z6F6N6u5P5R5T5V6R5O1 5J0h6k6D0.0o0?0O6$6O5H0R0U3d6X3K6!5%6r5)2-3J5^5z5:3a3!504`5.535d3Z5}255a745c4w77636s667h6I3n6i0H6/0S6j6r6t6Y1!6)040u6,6S2=6i5(6=6}4}3{3q6}7c5{3|58795 5`613|7f7h7i6%016a6c0g7x7s3-0?0B7Z3K6n6p7(5t6K6z1x0L6=4%6Q6H7U5Q047p2+7r7)0?0y7,5Z6/6;7^6-6Z0?0r825P6K6M867y6E0?6G6{877k041+5U5W8f7!5!040h5$7B8r5@735/1_3A4i727N54614i7L268G764h5g647S8R7j0.6a0U5o7q8T3L6U1W6W8y7?0?0d7=6v7$8,5H5J0T8b1 7u020n0E0i8?8m8o8%8k8g0.5J8+8(8-7{7m2P7|4:7U8;6^4m7C8A6~8C4y7G9i7I614z8K7a5_8H4g0O4z7R8R9z658Z7`5y7n9b3H7~4%7u7w8Y7_8.6_9h527E0O4Q8F7b609v4Q9r8M7d3a9U3F9A9C8#8p8/880495918s9D9.8h040T8a9M8l7#8n5S8$8q9=6?8*9^9 9E9aa78t8=9}92019K8}9 8 a39c9~8t9;amaf9D997oab8;9|7}9+a06Val5Fan94ab9@968:0?ad7}9I5Z0w4 030f0k0w0Q6A7;9P6H0l4?4V4.4X4+190E4!a*2K2Fa1a%0l4Y5)0X0Z0#0V04.

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

Python

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

.128013kg[: r);S/(èlo4y,6b=ac15ujd3t28_Pw7evp-fh0Omn]is050B0K0D0v0V0n0W0f0w0n0v0W0W0u010D0V0M010406050W0z0S0S0v0g0q040j0o0n0z0;0o0T050k0{0}0 110_0M04051h1a1k0k1h0_0B0V0L0)0+0-0/0+0T0c0z0v0c0K0N0M0q0D0P180f0P0V0c0P0n1M0P0D0@050!0t0n0K1t0,0.011L1N1P1N0D1V1X1T0D0g1i1H0)140W0M0v0T0/0E011Z1v010O0$0K0T0v0S0K1T1^1`1 1#221X25270@0a0f0H0g0o0M0o0W0V170T0f0Y1?0g0g0K0w2s1a2a0T1i0k1H2F1/1;1:1U0B2c1w0V0T242p1T1q1s0*1!2P2R0T0o2V1T0M2y1i2D2F2,0`1_2t2X202#0g0~0n1T0v1K2y0O0/030G0G0w2$0K1P2!0o0N0x0Q3a0@0x1a0v2-2:0^2/2b2=1#2@2_2{2}0K2 01313335372S3a3c1}040E3g3i1`3k2D2O013p0v2`1i2|0P2~3032340Y3z2#3B0N0C0@0C3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0N0p0@0p3)1b3+3l2;1u3o0o2^3O3r3S3t3U3x3X3{3Z3}0y0@0y422,3,2:3L3:4c3@3w3W364i393}0s0@0s4o443-473/493q3Q3s3u4w3`383!0J0@0J4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0F0@0F4W2E1l2*1a2V2I0B1;2N3.014x2U1r1i2)0K2+3j3*3I054x572b0V0B0/322D3!0x3r5f5h4g4y4-3c5l0f2g0K5o4x3Y4A5s1T0k3h453L0b0@0Y0O592E0f5F4 0T0O0@1/0V0G2Q0W0K0g2B435a4H2Y010?040l5L5d465(0T5S0v1W0K0v0z5-5O4!5*0h0e5-0_5#4?3K5n015i2:3!3D3=0f664+5q3|3C1~5v5x4Q6h0N6b5D040f6s5N5%205H040O495-6u4r5P0@0V6B5|5(0o0I6F19636r6I2?0t0@0g1`1C5{6v1#5*5,6O6Q1#0S0V3e6X6D5}0@0r6H6Y3/6S042f6,4Z5(6!6`5/2?5=5@5_6~3L5~5 61746e0G5j3}3$4M7a5y4z3!3$5u265w675p5z7j5C3h6t7u6C6{70040L3O0K0z0g0G0v5V0T5X2y0g6;6-6J0@0u7M7x3o711X736$6=5)0@0d746E046G7X7N205*0U787*5e5g7o7c3c3 7f7=6f7q3}3 7l276l4,6n7_3G7v6t6%3/0@0A7R6 1#0o7P8d4s6F7/2.657{7b694k5m8o7h5r0N4l807n7|7i8r2F7t877w8e0/6x0I1L1X8i7%8c6O8G3L8g04020c0D0i8N4!6)0@0Q8Z6J6L041`0B8(7y1,5^5`7:8H7Z047#8?8j048P2,8R4 8T0N8.6(6*043f8{4 7-940/8T8V8X9c3M0@7A1X7D7F7H7J5Y7$6.04606O628m4r7a7@0N4C7`826g4j3c4C8y9E7}9H7s6r8F7u899i048:7W9x7S0/5*8`9W8@5;8}9r6|0@7.8Q9R8T7Q9-7Y9%9U8=9#757!9)7y8~3j904!929h8#979|6Z9+8l588n5o9A4T9D7o8u6n4T9Jag6m9G0Nae869P889=8b9h9/9h9%9~3Ia07O04939;7+956+9v798o9A4/af8A8v4/akaP6naNaq879R9?5?7V9^aaaG9Y9{994!aya6a)049,8 9.8haF9X9S9k7C7E7G5W5Y9qa^8@0w5l04030f0R2t5W0m2ya95a0k5c4@564_531a0D4|bm2L2Ga!bj0k4`620Y0!0$0W04.

Évaluations restantes : 5/5

.128013kg[: r);S/(lo4y,6b=ac15ujd3t28_Pw7evp-fh0mn]is050A0J0C0u0T0m0U0f0v0m0u0U0U0t010C0T0L010406050U0y0Q0Q0u0g0p040j0n0m0y0/0n0R050k0_0{0}0 0@0L04051f181i0k1f0@0A0T0K0%0)0+0-0)0R0c0y0u0c0J0M0L0p0C0O160f0O0T0c0O0m1K0O0C0=050Y0s0m0J1r0*0,011J1L1N1L0C1T1V1R0C0g1g1F0%120U0L0u0R0-0D011X1t010N0!0J0R0u0Q0J1R1?1^1}1Z201V23250=0a0f0G0g0n0L0n0U0T150R0f0W1;0g0g0J0v2q18280R1g0k1F2D1-1/1.1S0A2a1u0T0R222n1R1o1q0(1Y2N2P0R0n2T1R0L2w1g2B2D2*0^1@2r2V1~2Z0g0|0m1R0u1I2w0N0-030F0F0v2!0J1N2Y0n0M0w0w380=0w180u2+2.0?2-292:1Z2=2@2_2{0J2}012 3133352Q383a1{040D3e3g1^3i2B2M013n0u2^1g2`0O2|2~30320W3x2Z3z0M0B0=0B3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390M0o0=0o3%193)3j2/1s3m0n2?3M3p3Q3r3S3v3V3_3X3{0x0=0x402*3*2.3J3.4a3=3u3U344g373{0r0=0r4m423+453-473o3O3q3s4u3^363Y0I0=0I4D3G4o3k4G3K4I494K4b4M3@4f4P3{0E0=0E4U2C1j2(182T2G0A1/2L3,014v2S1p1g2%0J2)3h3(3G054v55290T0A0-302B3Y0w3p5d5f4e4w4+3a5j0f2e0J5m4v3W4y5q1R0k3f433J0b0=0W0N572C0f5D4}0R0N0=1-0T0F2O0U0J0g2z41584F2W010;040l5J5b445$0R5Q0u1U0J0u0y5+5M4Y5(0h0e5+0@5Z4;3I5l015g2.3Y3B3:0f644)5o3`3A1|5t5v4O6f0M695B040f6q5L5#1~5F040N475+6s4p5N0=0T6z5`5$0n0H6D17616p6G2;0s0=0g1^1A5_6t1Z5(5*6M6O1Z0Q0T3c6V6B5{0=0q6F6W3-6Q042d6*4X5$6Y6^5-2;5:5=5@6|3J5|5}5 726c0F5h3{3!4K785w4x3Y3!5s245u655n5x7h5A3f6r7s6A6_6~040K3M0J0y0g0F0u5T0R5V2w0g6/6+6H0=0t7K7v3m6 1V716!6:5%0=0d726C046E7V7L1~5(0S767(5c5e7m7a3a3}7d7:6d7o3{3}7j256j4*6l7@3E7t6r6#3-0=0z7P6}1Z0n7N8b4q6D7-2,637_79674i5k8m7f5p0M4j7~7l7`7g8p2D7r857u8c0-6v0H1J1V8g7#8a6M8E3J8e04020c0C0i8L4Y6%0=0P8X6H6J041^0A8$7w1*5?5^7.8F7X047Z8;8h048N2*8P4}8R0M8,6$6(043d8_4}7+920-8R8T8V9a3K0=7y1V7B7D7F7H5W7!6,045~6M608k4p787=0M4A7^806e4h3a4A8w9C7{9F7q6p8D7s879g048.7U9v7Q0-5(8^9U8=5/8{9p6`0=7,8O9P8R7O9+7W9#9S8:9Z737Y9%7w8|3h8~4Y909f8Z959`6X9)8j568l5m9y4R9B7m8s6l4R9Hae6k9E0Mac849N869:899f9-9f9#9|3G9~7M04919/7)936)9t778m9y4-ad8y8t4-aiaN6laLao859P9;5;7T9?a8aE9W9_974Yawa4a%049*8}9,8faD9V9Q9i7A7C7E5U5W9oaH6!0k5a4=544@51180C4`b82J2EaYb50k4^600W0Y0!0U04.

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