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

.128013ùA=+xvétfrêi8T^ÀPea}yDq{ cR1/;d(èls30àO29zF_,-S.g5L[7b:u)Ion4hk6wp]Nm050F0s0i0t0m0I0J0z0A0I0t0J0J0d010i0m0=010406050J0(0^0^0t0k0v040V0+0I0(190+0,0z020t0^0=0E0z0B0s1j0k0x0(0s0J050D1g1i1k1m1e0=04051R1K1U0D1R1e0F0m0g11131517130,0X0(0t0X0s0U0=0v0i0.1t0z0.0m0X0.0I1}0.0i1c050|0$0I0s1%1416011|1~201~0i2628240i0k1S1^111p0J0=0t0,170O012a1)010j0~0s0,1x0s242s2u2z2c2C282F0^2H040a0z0r0k0+0=0+0J0m1s1u0`2q0k0k0s0A2$1K2J0,1S0D1^2=2m2o2n250F2L1*0m0,2E2Z241!1$122b2 310,0+35240=2+1S2:2=3i1f2t1u372A3b0k1j0I240t1{2+0j17030S0S0A3c0s203a0+0U0L0U0C1c0z0C1K0t3j3m1d3l2K3o2c3q3s3u3w0s3y013A3C3E3G323J0U2x040z0O3Q3S2u3U2:2~013Z0t3t1S3v0.3x3z3B3D0`3-3b3/0K3N0K3^2/3T1e3|3X173 410543453)473,303.3K0-3N0-4g1L4i3V3n1(3Y0+3r403#443%463+494v4b3K0Y3N0Y4B3i4j3m3}4n4L4r3*483F4R3I3K0:3N0:4X4D4k4G4m4I3!423$3(4)4u3H3/0#3N0#4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0n3N0n562;584F385b4J4o4q4N4s4P4+5j0U0P3N0P5o3{4!4l5t4{4p4}4O4*4a4-3L0L1c0C0L5G5q4#5c5v5N5y5P4,3/0C3M045+5X4E5Z5u4%5x4 5i4w3L3;0C3@0D3R4h3`1V3g1K352^0F2o2}5J4*341#1S3f0s3h3T612;054*6i2K0m0F173B2:5*3#6q6s5z5Q6v0z2P0s6y5(5B5,4g4@5s0/1c0`0j6k3=5:5J0,0j6N0m0A1_0i0+0^0m0s6Q6S5a1b040G6)6K3p1c3b0^0$2+1J4C626:2c6,0T6Q0z6*5s0,1c0A0m276(6{6l6}176,0)0%6Q1e7b6o1u6x016t3m3/3;5M7n5h5A5`2x6C2G6F507x245 3=0z7H736;040`0$1r717J2c0+1c0d7P7d016$1c5W7k7j3k3|7u0S6u3K4d4|7)6G5`4d7z2Q7B5_4S0U7-3^7H7I7W75042C0,7V5I5a7S047U7k72800$1c2O6/865s6,6.7k7Q4m6=6#6^1I8h598j1c0)858u2A880U8y5r2A7Y5-7i8t7m6r7o7*7q4x6w8L7v6A8P7?6E8M7:7`4y2=3R7~8c8i2A6M040;1|288D4#6N0s7N0i8:5J88020I0i0E8a3i8(8z3Y1c838J3}6,7h7#977)7+0U4U7.8R6z5)4T2y6D7^7w7`9g7}8%7~8n3~1c6$200s0(8_877T9C8v6-976T95309F8A1c0e9M947L8?7O8m7W7f9I9D040D0D9Y5s8G5~4Y9c9i9e4/9h9o8T0U4/8V9;9k9?7E8$9t7 8)2c8+0m6P8b9v8177799Q17880d903T928E9R6?8r6`7%a07e1c0!9%7K9y6%9B9Van016,0?9a9+aw6p9-8O0U539:8X7C7`539^aK7_5RaI9s9~8%9v8+2+0i0(0k84a57W0/0A1c0o0k1H8IaD8K6y9e5laJ8S9`5laOa_5Ba@aT9taW1c4+a491a676788/a%ax8{0X8~aa9w04aj6_ar6~apbl8o04at9Aboay1caAa/amaEa=aG5Da^9j5B5Da|bE5`bCb0aUag8;9S8@bgacbg81bravb67W889Pbb93178G3P9ba:0z9daG5V8Q9_6H5TbH8Y5Rb/8#7G9~b2043F0J7abyahao04aB4Db+b-2u5*6I3v7/aLb_3Mb@cgcc9|b|bMbN9J829Lb#c401bSctbObVbR1c8Ccx5Jb(bx6j7(aFcb3K5}b:aP9pb_7y9ncO9=cMb{aVa(1caYa!a$bXaxa)1c0R40c1bg0A5,030z2!0z1`0,02030K0P0E3v2t102m0+0(0g0hcG620D6n636h656e1K0i68df2{2?0t792=661Q7l3}2+0^0S0j0t0/0s0S0.7-1C1E1G1I0zc7d81Y0_1#3}0t0F0^1t2#0m1`300j881QdMdOdQ2$0U190i2k041C6Y0s0kd,0z2t0k0z1!6Y0+6!6$7adJ1R0*0Ic=001/2#d?000(1u400X4I2#0.2Q2L0mdE0W0z0Z292j0s0t0(d:0k0m102Ed:1k1x0H2m290F0+e41fd21,040+271}0t6!0mds2E0i0z0lez0z2m0md61LeF0X040W1V3U1R0q110.0tdEb,0i0h0keLdS0,0Tc@1uc1d?1D2u2(c?130z0g409Ad=0AePe=280z1IeQ0h0Xf50z0M0zf26m3E04a8ba6ndGe%1e0(0I3U2004c?d30me_1`2+0,0geC290m1i0h1!eL1DeP726na,a.d9fn1Kfy1efyc?3be^110{0i29fp29fdc=eCeQ7hfvfx0mfz0(0=e;au2+fifk3vf428a!f(0,2mfh0%b,e0dv1re+d-d,d=0F2u10f2d;19eA2W2#eAepemeo0z6.6n7Mgd0d0zbV0z0e3O1K6n8x0DfY05fydUf|f629fjf2g2f6g5g7fbg90~0zgceQggggd?gjg0ev0kgn0zfg0(d/0Fgsdl28gugwfn830zgAgC0UgFfV0`04gIgK0Df?7jh7h91T040Z3v0Q1teA292+g%0.290G0I000h0A1keQf929fmh496h36hfceQhy6hgy8^hBh5c=hkfM0(e4fj6Ye-1He/e;e?1`g9fA1u83e4d;0z0tfHeNfRg|301v8}1AhHgGfne_0A00f.e.fl6nf,h?h46Ch`0JeQd0g)0,gkelg^en0(ei0Ne{4IeQ2(f20$d312f-eQfFh*hx6nc+0 7a6ne$1X3U0DdodK365adNdP0,dRdT6UdW1TdYiHiJ0,d$2#d)0@8qf~1j0ffK40e}eUd30k102(ilg;286`d}042V32i80ze70zhshue530d@fJiI19i#hFcr1uh1h=hJi`fge0fj9v1kec1jf*0f1c090G5V0p0P09gI3ie_0Gf80z1G0mfci4jw1.0,2}0^0lee2m0H100Xe=jD0)iyi:0wg*fb0=eNhj10ht0JfD0bg+f,i2f.i63f0hc1g60sfD1u0k0h40eseld3i9d1i(i*29i,in102Y15b91IjP3Uhcfy0cep6gd{d=6!a!j:h(i^1ui{g-fcfGeN1`2(jeer1^jh0sjj04jl090je=0A0yjn0P0u0y0O0ujq6Qh^i3eQfj1!f~ks7WjfkvfOkyjl0Y0z09192Q10jn0nkM8mgJf^fZf^kbe}0(iZ0HjHi(ki3vi_kmhvkp2W2%hxkVkuedkYjk0GkBkD0yk#k%fKdFk+kIkKk-91h_f.kRjVcpiFl7kwkZ0G0Olfk(li0L0p0#lm6jk/f@040c30c?f0hOf*0z0WlRfXk:gLk=gsfF19k`j_khe`kjk htkn0Fh`l21`ktjgl9kzlbkC0tkEkGlk0p0y0K0L0ukLjraflojAlqkTl-0gkq1u0CiyhbfwdplKi8fCi710e72920i4hjeU0}0Ifbl:kXjilakGlF3`e_eugu0=1qetl.1ul i%a!101`0J0}eQf1hr0I0h2Qg6h,h4h j9j)j=j-0ik77jiCiB0{mt0J04.

Évaluations restantes : 5/5

.128013ùA=+xvétfrêi8T^ÀPea}yDq{ cR1/;d(èls30àO29zF_,-S.g5L[7b:u)Ion4hk6wp]Nm050F0s0i0t0m0I0J0z0A0I0t0J0J0d010i0m0=010406050J0(0^0^0t0k0v040V0+0I0(190+0,0z020t0^0=0E0z0B0s1j0k0x0(0s0J050D1g1i1k1m1e0=04051R1K1U0D1R1e0F0m0g11131517130,0X0(0t0X0s0U0=0v0i0.1t0z0.0m0X0.0I1}0.0i1c050|0$0I0s1%1416011|1~201~0i2628240i0k1S1^111p0J0=0t0,170O012a1)010j0~0s0,1x0s242s2u2z2c2C282F0^2H040a0z0r0k0+0=0+0J0m1s1u0`2q0k0k0s0A2$1K2J0,1S0D1^2=2m2o2n250F2L1*0m0,2E2Z241!1$122b2 310,0+35240=2+1S2:2=3i1f2t1u372A3b0k1j0I240t1{2+0j17030S0S0A3c0s203a0+0U0C3J1c0z0C1K0t3j3m1d3l2K3o2c3q3s3u3w0s3y013A3C3E3G323J0U2x040z0O3P3R2u3T2:2~013Y0t3t1S3v0.3x3z3B3D0`3,3b3.0K3M0K3@2/3S1e3{3W173~400542443(463+303-3K0-3M0-4f1L4h3U3n1(3X0+3r3 3!433$453*484u4a3K0Y3M0Y4A3i4i3m3|4m4K4q3)473F4Q3I3K0:3M0:4W4C4j4F4l4H3Z413#3%4(4t3H3.0#3M0#4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0n3M0n552;574E385a4I4n4p4M4r4O4*5i0U0P3M0P5n3`4Z4k5s4`4o4|4N4)494,3J0L1c0C0L5F5p4!5b5u5M5x5O4+3.0C0C5T3O0D3Q4g564D5Y5t4$5w4~5h4v3J3:0C3?5.3^2;1V3g1K352^0F2o2}5I4)341#1S3f0s3h3S5:634)6j2K0m0F173B2:5)3!6q6s5y5P6v0z2P0s6y5%5A5+2=5/4?5r0/1c0`0j6l3;5=5I0,0j6O0m0A1_0i0+0^0m0s6R6T591b040G6*6L3p1c3b0^0$2+1J4B3_6+5r6-0T6R0z6~6=040A0m276)6|636;2c6-0)0%6R1e7b6o1u6x016t3m3.3:5L7n5g5z5|2x6C2G6F4 7x24610z7G737d4l6O0s0$1r72742c0+1c0d7P7J016%1c5V7k7j3k3{7u0S6u3K4c4{7)6G5|4c7z2Q7B5{4R0U7-3@7H7I5H590,1c2C0,7V805r7S047U7k7 585r0,0$1c2O6:872A6-6/7k7Q7K046@6_1I8k8e8m1c0)868x7R1c0U8B5q2A7Y045-4X8w7m6r7o7*7q4w6w8P7v6A8T7?6E8Q7:7`4x6J3;7H8q016N040;1|288G4!7L7N0i8?5I89020I0i0E8b3i8d8H3X83308N3|6-7h7#997)7+0U4T7.8V6z5(4S2y6D7^7w7`9i7}7~8+7W82046%200s0(8{5989923S949a1c8o7%8l9604849E881c0e9S750`8_995I7f9!9F1c0D0D9%5r8J608M8p7(9k9g4.9j9q8X0U4.8Z9`9m9|7E3Q9v9w9O178.0m6Q8c8,9y77799W8D8a9H3_9J6U6?6$8u6{9N8C176-0!9,759A6(9D9;a6016-0?9c9:ar8O6y9g529_8#7C7`529~aO7_5QaM9ua47~8,8.2+0i0(0k85ab7W0/0A1c0o0k1H7i9e9?8S0U5kaN8Wa05kaSa}5Aa{aX9va!1c4*aa93ac1cae8=a+aC8}0X90ag8r8t6`aw7e1cavaBas3}1cay9Cboat1caFa?bsaJ8Q9g5Ca|9l5A5Cb0bJ5|bHb4aYal818^7Obfbt9Gbkbu9z0~azbZ899VbW95178J8L4CbD0z9fa_5U8U9 6H5SbM8$5Qb^8)bRb6043F0J7aaI9K04aGb:c8b?2u5)6I7t9kb~cg9o7AaT9rb ch7FbRa5bt9y9Rb+3|bYcyamb#9BaAba7W898FcB59b.bCcda^cf3K5 b_co9{cSb}aPb 7scs7Gc3a$a(a*cGaCa-1c0R3 c6cN6k0D6n646i666f1K0i69c}2{2?0t792=671Q7l3|2+0^0S0j0t0/0s0S0.7-1C1E1G1I0zcb6}1X3T353|0t0F0^1t2#0m1`300j891Qdudwdy2$0U190i2k041C6Z0s0kdQ0z2t0k0z1!6Z0+6#6%7a1Y1T040*0I0z0J001/2#dX000(1u3 0X4H2#0.2Q2L0mdm0W0z0Z292j0s0t0(dU0k0m102EdU1k1x0H2m290F0+d;1f2m1t0X040+271}0t6#0mda2E0i0z0lej0z2m0m0h2/ep1,040W1V3T1R0q110.0tdmb=0i0h0kewdA0,0T0z1`c6dX1D2u2(2!0z130z0g3 9CdW0AeAeZ280z1IeB0h0Xe@0z0Me:3v056nbd7a6ndoeO1e0(0I3T2004e/0+0(0me%1`2+0,0gem290m1i0h1!ew1DeA736na:a=c@3E2=fj1efje/3be$110{0i29fae~0JeB0JemeB7hfgfi0mfk0(0=eYaz2+f4f6e=e@a(fQ0,2mf30%b=d,dd1reSdRdQdW0F2u10e;dV19ek2W2#eke9e6e80z6/6n9Yf 0d0zbwe90e3N1K6n8A0DfK05fjdCf,e^29f5e;e?28f?e`f^e|29f{0~0zf~eBg2g2dXg5f:g86(0zf20(dT0Fged328gggifI840zgmgo0z0UgrfH0`04gugw0Df$7jg{g}d)0Z3v0Q1tek292+gR0.290G0I000h0A1keBe{29f8g,98g@6ie~eBhlg^gk8`hog_d-h7fyfneBf56ZeU1HeWeYe!1`f{fl1u84d;dV0z0tfteyfDhm1u8~90e+9Zhwe%0A00e 0zeVe;hs6ifagsfI6Ch)fWef10g40,g6e5g(e70(e20N1ufY0keB2(e;0$fm12290{0zfrhThk6nc/0 fbfIeNdr7jd60_1#dGdx0,dzdB6VdE1TiudIe#dK2#dN0@aof.1j0ffw3 e+eFfm0kh`29iag!286{d(1R2V32h|0zd@0zhfhhd=30dYfviw19iOh.9Q30g;h!bVfcf1iOf58,1kd|1jfS0f1c090G5U0p0P09gu3ie%0Ge`h+fnfVeB2m0H100XeZ0,0F0)ioiZ040wgUe}0=eyh610hg0Jfp0bf:fU0,h@eB2t103f0hc6f^0sfp1u0k0h3 ece5fmh}106#a(iT0ziVicjP2Z2!790Jjv3Th0fj0ce96hd$dWj)0kjVhRi(1ui+i6e~fsey1`2(j1eb1^j40sj604j8090jeZ0A0yja0P0u0y0O0ujd6Rh%jMf/1!f.kc7Wj2kffAkij80Y0z09192Q10ja0nkw8pgvf(fLf(j{e+0(iM0Hd~k0k23vi)k6hik92W2%hkkEked}kHj70Gklkn0ykKkMfwdnkQkskukS93h(h*f5kBk;aCkFk@j5k_0Ok~kNl10L0p0#l5c?gwj`30e/e.hB290Wlx1KlqkXgefr19k$j#a(k)k4i*hgk70Fh)k.1`kdj3k^kjk`km0tkokql30p0y0K0L0ukvje9Il7h^l9jCd=2E0gka1u0Ciog fhd70clsfogTi%d@2920fWh6eF0}0Ie}lRkGlflUkqlo3_e%eegg0=1qedlP1ul%iQj*e(i40}fX0me:he0I0h2Qf^hVg^h:hwjleajReAj@iq6fiq0{m90J04.

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=+xvétfEri8TaeP*yDq cRC1/;d(èls30àO29_,-S.gî5L[7b:u)Ion4hk6wp]Nm050B0o0g0n0k0E0F0u0v0E0n0F0F0b010g0k0-010406050F0Z0:0:0n0j0r040P0$0E0Z140$0%0u020n0:0-0A0u0w0o1e0j0t0Z0o0F050z1b1d1f1h190-04051M1F1P0z1M190B0k0e0|0~10120~0%0R0Z0n0R0o0O0-0r0g0)1o0u0)0k0R0)0E1^0)0g17050@0X0E0o1Y0 11011@1_1{1_0g21231 0g0j1N1:0|1k0F0-0n0%120K01251!010h0_0o0%1s0o1 2n2p2u272x232A0:2C040a0u0p0j0$0-0$0F0k1n1p0=2l0j0j0o0v2X1F2E0%1N0z1:2-2h2j2i200B2G1#0k0%2z2U1 1V1X0}262`2|0%0$301 0-2$1N2+2-3d1a2o1p322v360j1e0E1 0n1?2$0h12030M0M0v370o1{350$0O0K0O0y170u0y1F0n3e3h183g2F3j273l3n3p3r0o3t013v3x3z3B2}3E3E3I0K3L3N2p3P2+2_013U0n3o1N3q0)3s3u3w3y0=3(363*0G3I0G3.2*3O193=3S123^3`053|3~3!403%2{3)3F0(3I0(491G4b3Q3i1Z3T0$3m3_3W3}3Y3 3$424o443F0T3I0T4u3d4c3h3?4g4E4k3#413A4K3D3F0+3I0+4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0W3I0W4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0l3I0l4 2,514y33544C4h4j4G4l4I4!5c0O0L3I0L5h3;4T4e5m4;4i4?4H4Z434$3G0H170y0H5z5j4U555o5G5r5I4#3*0y3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0z3M4a3:1Q3b1F302:0B2j2^5C4Z2 1W1N3a0o3c3O5`2,054Z6b2F0k0B123w2+5Z3W6j6l5s5J6o0u2K0o6r5X5u5#494-5l0*170=0h6d040u5)5C0%0h172{1V0v0o6J6M5316040C6V6D3k172e0o0n0Z6#5B6X170N6J6L6$3T170v0k226U4v5{6@126Y0!0Y6J196~6e3=6q016m3h3*5=5F7a5a5t5:2s6v2B6y4_7k1 5^6K0u7u6W5l0%6G0o0X1m6=7w2v0$170b7D70010:0k175P773P7Q5)7h0M6n3F464=7U6z5:467m2L7o5/4L0O7Y3.7u7v7K7y042x0%7J6.5l7G047I7Q6?7{3k0X172J6-525l6Y6!7S7=6(0n6|6+875k2v727`887F170O8m8j277M5N758i0u7U7W0O4r7Z6k7b6s5Y4q2t6w7*7j7,8C7/7:7E276F040,1@238r4U7z7B0g8Y5C7}020E0g0A7 3d818n6^7@2{8x5C6Y747Q763f798E7c2p3*4N8D8L6t4M8J7n8F7#7,948P7:8Q8d047M1{0o6,808R127}8.3O8:8s71178b8~828=0=8#8%537}0c9E7x177^8^6/040!9I8o040z0z9Q8t7N045@4R8x8z7d4%6p908G5u4(7(6x9b7p7,4(2-3M9g9g9p018T0k6I9o9i6`6|9V9q178*8,a43@8e8g9n9z8;9w040V9M9J9j0_0k9maj8k170.8{9!8c4T9$923F4|959:7+5K4|9.968H0OaA9f9_9`9i9La09Aa57~a97?9kanad9t9{7}8qaQaf7L9X3K8|9#9*8A5eaB7i970O5eaGaC8M5Ka:aLaNaR9|174!9 8/9{7?a28Xa%9v019r9s3:9u8Z046)8hava(6YaiblbbaVamaobp3?6Yas8wbuax0%3*5wa;9+5:5wa_a=aIbDa~aMbg5C8T2$0g0Z0j7_babhaWbtauae1pbA5Z5MbE9c5K5O997)a`a?b-9@7taM9{8T3A0F6}b#bv17at4wbza.9%3G6B3q7!9;b,3HbIbF7,5!7r9^bNa a(7?9C7CbW8(7HaU17bYaYbfa!179Hcp538u5$byb~b%3F0y7fc89*b+5Z7l8Kb:aIcIchb@bO53bQ0?bTbVb57K0*0v170/1ob}c23f0z6g5|6a5~671F0g61c^2?2.8f232-5 1L6hbb2$0:0M0h0n0*0o0M0)7Y1x1z1B1D0uc15{1S3P303?0n0B0:1o2W0k1=2{0h7}1Ldpdrdt2X0O140g2f041x0v0)0o0jdL246S1;0g0$7Mdh8y0g0f0j0n140e240Y0u0I2l0%2A0S2h6}1T1O040#0E0u0F001*2W0u2Z0Ed|0E0R4B2W0)2Ld 242$dPdOdMd 0kdL0$dTdV1C2G0kdh0Q1Q7Rd10;1WdBds0%dudw6Odz1OevdDdvbBdGdI0U3qebdMeddQ24e16RegdQ0Z0ucueqd20U240v3_0v0Zd_e000eR6Td eUcueVdZ2W24dT1m3Y0$0k0{dh0Edh0{3y1d2z0@0k2$0F0Q0u0#6`0u1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Db0br9lcv2,cV7|crcA899xap9B7Acoc#b09Gcs8?c!6c7K8lfE9R9Ta9cC9Z6cc/3z04epdmd20J0j0Nd 2pf1dNf50%0{fmfo0{2Zff0Rd!1I2X2lf30u230u0xf-0~0uf50Eg40=0{f4an0jge0F0gg30k7MdY0of90xe!e$e(6L4Zfl2pfn1+1-0rfr2a1|1~d3bXbsfz6KcxaTfU278afH4f8!fKaZ7KfNgOgSfPgR01fTfLa(7}fWgYa)17fZdl6g0u0-9mgk2o0jdye|0u0o0d0v0f0=0j0|0?0ge@0^gbePgme?f90i1p3Y0h0?f-2Vg3di0=0Z0d8y0%6Sdifj2Z5Cfm1)gAfq291`gFfvclgT8$7Sf#0=6K0?gvfkhwgyhyfpgChBftgGb69K8@hIg;0F1ogkf}2p0B0Fg79mh3h$g2hue!53hxfogBgDhC2chEbqhGa9gXg(h g!h!f$g=g@d 0f2o10dNg33q0e3_h.glgngpeXd?0sf/h40|0 fd3igtg4eQhreSe.eVgJg}1p1mam0F2pgkg80~0j1+bTe9g3e+0%h60jihh9djhNhvh@hQh_hAfshDgH6NctgJi1fDi3bhcnhHi;cq04czi^9N9yfRfwhYfQcwgW8pfOi?g#g%gVfM17g+i|5lfY6VhJ6af(d=1Mipf?hlis0{3a0fb|iTh-g=2R220De82|d`242Tb|g=ite#f,iE2P1/1;0%h-geiTgg0{0%00h%jHf`h70_ixhbh6f90m0$e_g{h,0u0P0kiR1=0nihd~1eex0-e(0fe9jUdU0Xf70u0h0Eei0@iTf@jEjy0EjA24b|d!d~0n0-g_eUf2e8g_g}0d1y0-g48{d=do5Cdqeweyhf0d1skt2MdAkydCexdEeH2M0ikr1tb9kweuhP1%hRgB3y1phUi*9{2I2z2B170pjN1=0x1oh$g40P1D2V1o6V69d33/6ec:8 6r6n0G3G9)aH4`l2cccPbJl6l35V5.a{7-l3b?9{0R6Y020R8,lmloln1vg#cmfJi@jag)i:lxbb0:6P9Y0Q7Pje9R0q0qfXa*0H0K48a,c3l07dl2cJ8ycLcalgcO9ala3)lU2t585HlYl(li7Klka6lrlp0Al?6Lbui,i58/7;jbgNlH8tlD0KlFi/04lJlL5NlNlPm1aSi{lA3?cCa+b!i 6ic492l27.cKl5l%7-b.9/l$44mpl)4Xmx3Dmzl.b0l:04l?mJlrl_b~l{j7g,i2mgl{aPl}9{0v5#03iaicb|2LiTiQe#2o6`dYcEmlb$mnbBl28OmrcQlb4rcdcMm?mA5-mClg8O7slj7}dxm.6 awm;lg9em^n1l24Nm|l,0Onhl*5Wnj9en4l/lll=nt8,mMm/b 6Zlti0mQcyfOmUnx8_179PnC9Sm99Y6=fB2vmX17mZ0Bib261yf4m)kj0nm,j~k6ghiQg8h:2Ln878nalSmo0O9?7glXaDlg9-l9cemDn?m 59n~n{cTn56Q6On.gHb%l2aKneo3ocmvmsmyaJo1l+n`ogmFa(mHmKlqnvnA04mPmdbcnDg,gQl`537?nFj3l a$oylu9DoDfF9Om69Ug,jglQcFnbl2a}oem}a@ohm_mta^nmle6toXo5l/7}0l0Q0L0l0l0(0+0T0+0W0(0G5!0T0l0o0c0G0H4~oUf!c:1S5}0zespd6776pe0=ga0F04.

Évaluations restantes : 5/5

.128013=+xvétfEri8TaeP*yDq cRC1/;d(èls30àO29_,-S.gî5L[7b:u)Ion4hk6wp]Nm050B0o0g0n0k0E0F0u0v0E0n0F0F0b010g0k0-010406050F0Z0:0:0n0j0r040P0$0E0Z140$0%0u020n0:0-0A0u0w0o1e0j0t0Z0o0F050z1b1d1f1h190-04051M1F1P0z1M190B0k0e0|0~10120~0%0R0Z0n0R0o0O0-0r0g0)1o0u0)0k0R0)0E1^0)0g17050@0X0E0o1Y0 11011@1_1{1_0g21231 0g0j1N1:0|1k0F0-0n0%120K01251!010h0_0o0%1s0o1 2n2p2u272x232A0:2C040a0u0p0j0$0-0$0F0k1n1p0=2l0j0j0o0v2X1F2E0%1N0z1:2-2h2j2i200B2G1#0k0%2z2U1 1V1X0}262`2|0%0$301 0-2$1N2+2-3d1a2o1p322v360j1e0E1 0n1?2$0h12030M0M0v370o1{350$0O0(0O0y170u0y1F0n3e3h183g2F3j273l3n3p3r0o3t013v3x3z3B2}3E0O2s040u0K3L3N2p3P2+2_013U0n3o1N3q0)3s3u3w3y0=3(363*0G3I0G3:2*3O193@3S123`3|053~403!423%2{3)3F0(3I0(4b1G4d3Q3i1Z3T0$3m3{3W3 3Y413$444q463F0T3I0T4w3d4e3h3^4i4G4m3#433A4M3D3F0+3I0+4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0W3I0W4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0l3I0l512,534A33564E4j4l4I4n4K4$5e0O0L3I0L5j3?4V4g5o4?4k4^4J4#454(3G0H170y0H5B5l4W575q5I5t5K4%3*0y3H045$5S4z5U5p4Y5s4`5d4r3G3,0y3/0z3M4c3=1Q3b1F302:0B2j2^5E4#2 1W1N3a0o3c3O5|2,054#6d2F0k0B123w2+5#3W6l6n5u5L6q0u2K0o6t5Z5w5%4b4/5n0*170=0h6f3-5+5E0%0h172{1V0v0o6L6N5516040C6W6F3k172e0o0n0Z6$5D6Y170N6L0u6X5n0%170v0k226V4x5}6%276Z0!0Y6L19706g3@6s016o3h3*3,5H7c5c5v5=2s6x2B6A4{7m1 5`3-0u7w6^6(040=0X1m6?7y270$170b7E72120:0k175R793P7R5+7j0M6p3F484@7V6B5=487o2L7q5;4N0O7Z3:7w7x7L3_172x0%7K6/5n7H047J7R6@7?0%0X172J6.545n6Z6#7T836)0n6~6,885m2v747{892v7~0O8n8k277N5P778j0u7V7X3E6r6m7d6u5!4s2t6y7+7l7-4t2-3M7;827|2v6H040,1@238s4W6I0o7C0g8!5E7~020E0g0A803d8S8o3T7^2{8y5E6Z767R783f7b8E7e2p3*4P7!938G5w4P7)6z8F7$7-977:8R7;7F4h177N1{0o6-819m017~8;3O8?8t128b8{556`7A8%7D9t7?7~0c8*9E8_7`8d8T73170!9N7}170z0z9W2v8v045_4T8y8A7f4)8D8L6v9.9d9:8H0O4*8P7v9k9z3^8V0k6K9J9S9n046|6~9#7G178-8/a9a56*8i9R8@9B170V9D6_9o0_0k9ran8l170.8~9*ai1p9,953F4~989@5w4~9?9f7r7-aE9j9}8R9u9F7_ae9v7IaU9F9par9s8=9u8qaU9%3K8 9+998B5gaFaK7,5M5gaJ7k9;0Oa:aO9k9u8V4$a2a$8ea66}8Za3ajaV7 9x3=9~6O8f8ha#6e7?6Zamaz8#04aZasbo8|avax4yboaB0%3*5ya;a`9^5ya_9a5=bCa~aPbf558V2$0g0Z0j9Qb4a47@bqaqbsay914Vbz5#5ObDbI7-5Q8J7pa=8M5Mb.9{bMb0173A0F6 b$ba8}8xbya.9-3G6D3q7#aLb?3HbH9gcb7t8QbM9lb57B9IbVba9waXap9qbjbea%179Mb99A01a*c2b aAc4aC5?9/b;a{5^b/7*cJ9^cLb^cjbWbP0?bSbU9yb00v170/1ob~cY7?0v5%030u0P0k0u1=0%02030G0L0A3q0jar1p2h0$0Z0e0fcC6e0z6i5~6c60691F0g63dd2?2.8g232-611L6jcz2$0:0M0h0n0*0o0M0)7Z1x1z1B1D0ubw5}1S3P303^0n0B0:1o2W0k1=2{0h7~1LdKdMdO2X0O140g2f041x0v0)0o0jd*246T1;0g0$7NdC8z0g0f0j0n140e240Y0u0I2l0%2A0S2h6 1T1O040#0E0u0F001*2W0u2Z0Eeh0E0R4D2W0)2Lek242$d.d-d+ek0kd*0$d=d@1C2G0kdC0Q1Q7Sdm0;1WdWdN0%dPdR6PdU1OeQdYdQbAd#d%0Uc|2%d+eyd/24em6SeBd/0Z0ubr9sea1M0U240v3{0v0Zeeel00e:6Ueke?e^e@d{2W24d=1m3Y0$0k0{dC0EdC0{3y1d2z0@0k2$0F0Q0u0#6|c;1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DbWaYbZct2,bN9X7 aU9Cbt9O9G8(aU9Lcq04aTf$8a9Uf*9Y9!cy3^9%9)d66ieKdHdn0J0j0Nek2pfnd,fr0%0{fIfK0{2ZfB0Rd|1I2X2lfp0u230u0xg30~0ufr0Egn0=0{fqar0jgx0F0ggm0k7Nd`0ofv0xe}e f16@4#fH2pfJ1+1-0rfN2a1|1~dobpe^f=fZf^bu6!at8^f(cmc)bWf+g)f%f.cD3^8mg?fY9Za)7O9(6Wd73z3-0-9rgD2o0jdTfi0u0o0d0v0f0=0j0|0?0gfd0^gue.gFfcfv0i1p3Y0h0?g32VgmdD0=0Z0d8z0%6TdDfF2Z5EfI1)gTfM291`gYfRba9Fcl8)7Th30=3-0?gOfGhMgRhOfLgVhRfPgZaR9Ph26ief1ogDgg2p0B0Fgq9rhj0Fd?ethKe}55hNfKgUgWhS2chUczhW9HhYcnczg=ikbpg^f|h40uh61mek0f2o10d,gm3q0e3{i1gEgGgIeLdn0sg5hk0|0 fziN0Ef0gne/hHe;f7e@fUhd1p1maq0F2pgDgr0~0j1+bSeugmf40%hm0jiChpdEh(hLi8h+iahQfOhTg!bgbYcsg%bdfWh=g.ijg:cocwf!178cg_j5ipcu9K178rg|7zhXg,ak049Vjraa04g~jy7Mh0f{dGf}iIebiKg9hBiN0{3a0fb}i?i0is2R220Det2|ef242Tb}isiOe~g2i!2P1/1;0%i0gxi?gz0{0%00h`j(gdhn0_iThrhmfv0md1hmhbh c.c:em1=0niCej1eeS0-f10feuj^d?0Xft0u0h0EeD0@i?gaj#jV0EjX24b}d|ej0n0-h9e?8~eadJ5EdLeReThv0d1s0-d%dVkMdXeSdZe$2M0i0d1ykTe9dIePh*1%h,gU3y1ph/j39u2I2z2B170pj.1=0x1oi3gn0P1D2V1o6W6bdo3;6gd8926t6p0T3GcIbE4|lhcc8KcOllli5X5:b=0Olmcgj4550R6Z020R8/lClElD1vjubXjtjCbbj96M7?0:6Q9(0Q7Qin8+170q0qg 5P0H0K4aa,c3lf7flh7hc899celv3+cM9elk3)l.2t5a5Jcal?7h7u9ulAablHlF0Am86@f/7zjmfW7=g;aWlMlR170KlUg%lZl#5(l%l)lW55imjeczcBl*g_b(lh7/l:aGl{7.l^mG46mDl}4Zl`mLmI9{m4lBm7mV8/mbjkf%lLmufYcxm$md8`81fX2vc+17c-0Biw261yfqi: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`kF0nm}kkksgAi:gri3fpnng!mC9_ljb,ngo6cdnE4*neo8l?9`6EbWnk04dSo37Un2l?aNnunzlhaInyofoumN5/ot0OaNm3njmUnKmalJihf)lMnUjabljioJnXn(bbjqoToKg/n0c0f;oM9YmqjF5ka-nqn3a|o7l=lha^owo:o.oeo@a}oEoj7~0l0Q0L0l0l0(0+0T0+0W0(0G5$0T0l0o0c0G0H50mAiqh#d9dl6978eN0zpq0=gt0F04.

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

.128013/;=d(l+s3v2t_f,-Srig5[7baeP:u)yjon4hk6 cwp]m1050e0A0m0z0t0g0i0N0O0g0z0i0i0d010m0t0Q010406050i0D0S0S0z0s0F040r0H0g0D0.0H0I050b0^0`0|0~0?0Q04051e171h0b1e0?0e0t0k0$0(0*0,0(0I0u0D0z0u0A0q0Q0F0m0K150N0K0t0u0K0g1J0K0m0;050X0y0g0A1q0)0+011I1K1M1K0m1S1U1Q0m0s1f1E0$110i0Q0z0I0,0l011W1s010o0Z0A0I0z0S0A1Q1=1@1|1Y1 1U22240;0a0N0B0s0H0Q0H0i0t140I0N0V1:0s0s0A0O2p17270I1f0b1E2C1,1.1-1R0e291t0t0I212m1Q1n1p0%1X2M2O0I0H2S1Q0Q2v1f2A2C2)0@1?2q2U1}2Y0s0{0g1Q0z1H2v0o0,030n0n0O2Z0A1M2X0H0q0x0q0T0;0T170z2*2-0=2,282/1Y2;2?2^2`0A2|012~3032342P370q1`040l3d3f1@3h2A2L013m0z2@1f2_0K2{2}2 310V3w2Y3y0j0;0j3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380J0;0J3#183%3i2.1r3l0H2=3L3o3P3q3R3u3U3@3W380v0;0v3}2)3(2-3I3,473:3t3T334d36380M0;0M4j3 3)423+443n3N3p3r4r3?353y0x0;0x4A3F1i2%172S2F0e1.2K3*014s2R1o1f2$0A2(3g3$4S4s4-280t0e0,2 2A3y3a4H4@4_4b4t4M383a0N2d0A504s3V4v391Q0b3e403I0L0;0V0o4/2B0N5h4#0I0o0;1,0t0n0i332w2y3~4S4C2V010:040f5n4=415F0I5u0z1T0A0z0D5K5q4D5G0;0E0C5K0?5C2B5h4 014`2-3y3A3.0N5+3=4c533z1{57594L3^5`2C3e0N635p5E1}5j040o445K654m5r0;0t6c5W5F0H0P6g165(046d3j5X0I0y0;0s1@1z5V661Y5H5J6p6j2:6v042c6A6e5X6D6L6s5N5P5R5T6P5M1}5H0E6i6B0,0H0;0q6!6M5F0S0t3b6V3I6Y5#6p5%2+3H5?5x5.383Y4~4^5,515b3X5{2358725a4u75616q647f6G3l6g0n6-0I6h6p6r6W1Y6%040d6*6Q2:6g5$6:6{4{3_3o6{7a5_3`56775}5^5 3`7d7f7g6#01686a0s7v7q3+0;0G7X3I6l6n7$5r6I6x1v0A6:4#6O6F7S5O047n2)7p7%0;0h7*5X6-6/7?6+6X0;0p805N6I6K847w6C0;6E6_857i041)5S5U8d7Y5Y040E5!7z8p5=715-1@3y4g707L525 4g7J248E744f5e627Q8P7h0,680t5m7o8R3J6S1U6U8w7;0;0w7:6t7!8*5F5H0R891}7s020g0m0c8;8k8m8#8i8e0,5H8)8$8+7_7k2N7`4.7S8/6?4k7A8y6|8A4w7E9g7G5 4x8I785@8F4e0q4x7P8P9x638X7^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+0b4;4T4,4V4)170m4YaN2I2D9)aK0b4W5%0V0X0Z0i04.

Évaluations restantes : 5/5

.128013/;=d(l+s3v2ét_f,-Srig85[7baeP:u)yjon4hk6 cwp]m1050e0C0n0B0u0g0i0P0Q0g0B0i0i0d010n0u0S010406050i0F0U0U0B0t0H040s0J0g0F0:0J0K050b0`0|0~100^0S04051g191j0b1g0^0e0u0k0(0*0,0.0*0K0v0F0B0v0C0r0S0H0n0M170P0M0u0v0M0g1L0M0n0?050Z0A0g0C1s0+0-011K1M1O1M0n1U1W1S0n0t1h1G0(130i0S0B0K0.0l011Y1u010p0#0C0K0B0U0C1S1@1_1~1!211W24260?0a0P0D0t0J0S0J0i0u160K0P0X1=0t0t0C0Q2r19290K1h0b1G2E1.1:1/1T0e2b1v0u0K232o1S1p1r0)1Z2O2Q0K0J2U1S0S2x1h2C2E2+0_1^2s2W1 2!0t0}0g1S0B1J2x0p0.030o0o0Q2#0C1O2Z0J0r0w0r0V0?0V190B2,2/0@2.2a2;1!2?2^2`2|0C2~01303234362R390r1|040l3f3h1_3j2C2N013o0B2_1h2{0M2}2 31330X3y2!3A0j0?0j3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0L0?0L3%1a3)3k2:1t3n0J2@3N3q3R3s3T3w3W3_3Y3a0x0?0x3 2+3*2/3K3.493=3v3V354f383a0O0?0O4l413+443-463p3P3r3t4t3^373A0z0?0z4C3H1k2)192U2H0e1:2M3,014u2T1q1h2(0C2*3i3(4U4u4/2a0u0e0.312C3A3c4J4_4{4d4v4O3a3c0P2f0C524u3X4x3b1S0b3g423K0N0?0X0p4;2D0P5j4%0K0p0?1.0u0o0i352y2A404U4E2X010=040f5p4@435H0K5w0B1V0C0B0F5M5s4F5I0?0G0E5M0^5E2D5j51014|2/3A3C3:0P5-3@4e553B1}595b4N3`5|2E3g0P655r5G1 5l040p465M674o5t0?0u6e5Y5H0J0R6i185*046f3l5Z0K0A0?0t1_1B5X681!5J5L6r6l2=6x042e6C6g5Z6F6N6u5P5R5T5V6R5O1 5J0G6k6D0.0J0?0r6$6O5H0U0u3d6X3K6!5%6r5)2-3J5^5z5:3a3!504`5.535d3Z5}255a745c4w77636s667h6I3n6i0o6/0K6j6r6t6Y1!6)040d6,6S2=6i5(6=6}4}3{3q6}7c5{3|58795 5`613|7f7h7i6%016a6c0t7x7s3-0?0I7Z3K6n6p7(5t6K6z1x0C6=4%6Q6H7U5Q047p2+7r7)0?0h7,5Z6/6;7^6-6Z0?0q825P6K6M867y6E0?6G6{877k041+5U5W8f7!5!040G5$7B8r5@735/1_3A4i727N54614i7L268G764h5g647S8R7j0.6a0u5o7q8T3L6U1W6W8y7?0?0y7=6v7$8,5H5J0T8b1 7u020g0n0c8?8m8o8%8k8g0.5J8+8(8-7{7m2P7|4:7U8;6^4m7C8A6~8C4y7G9i7I614z8K7a5_8H4g0r4z7R8R9z658Z7`5y7n9b3H7~4%7u7w8Y7_8.6_9h527E0r4Q8F7b609v4Q9r8M7d3a9U3F9A9C8#8p8/880495918s9D9.8h040T8a9M8l7#8n5S8$8q9=6?8*9^9 9E9aa78t8=9}92019K8}9 8 a39c9~8t9;amaf9D997oab8;9|7}9+a06Val5Fan94ab9@968:0?ad7}9I5Z0Q4 030P0m0Q0M6A7;9P6H0b4?4V4.4X4+190n4!a*2K2Fa1a%0b4Y5)0X0Z0#0i04.

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

.128013/;=d(èls30Ov2t_f,-Srig85[7baeP:u)yjon4hk6 cwp]m1050e0D0o0C0v0h0i0Q0R0h0C0i0i0d010o0v0T010406050i0G0V0V0C0u0I040t0K0h0G0;0K0L050b0{0}0 110_0T04051h1a1k0b1h0_0e0v0m0)0+0-0/0+0L0w0G0C0w0D0s0T0I0o0N180Q0N0v0w0N0h1M0N0o0@050!0B0h0D1t0,0.011L1N1P1N0o1V1X1T0o0u1i1H0)140i0T0C0L0/0n011Z1v010q0$0D0L0C0V0D1T1^1`1 1#221X25270@0a0Q0E0u0K0T0K0i0v170L0Q0Y1?0u0u0D0R2s1a2a0L1i0b1H2F1/1;1:1U0e2c1w0v0L242p1T1q1s0*1!2P2R0L0K2V1T0T2y1i2D2F2,0`1_2t2X202#0u0~0h1T0C1K2y0q0/030p0p0R2$0D1P2!0K0s0W0k3a0@0W1a0C2-2:0^2/2b2=1#2@2_2{2}0D2 01313335372S3a3c1}040n3g3i1`3k2D2O013p0C2`1i2|0N2~3032340Y3z2#3B0s0j0@0j3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0s0M0@0M3)1b3+3l2;1u3o0K2^3O3r3S3t3U3x3X3{3Z3}0y0@0y422,3,2:3L3:4c3@3w3W364i393}0P0@0P4o443-473/493q3Q3s3u4w3`383!0A0@0A4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0x0@0x4W2E1l2*1a2V2I0e1;2N3.014x2U1r1i2)0D2+3j3*3I054x572b0v0e0/322D3!0W3r5f5h4g4y4-3c5l0Q2g0D5o4x3Y4A5s1T0b3h453L0O0@0Y0q592E0Q5F4 0L0q0@1/0v0p2Q0i0D0u2B435a4H2Y010?040f5L5d465(0L5S0C1W0D0C0G5-5O4!5*0H0F5-0_5#4?3K5n015i2:3!3D3=0Q664+5q3|3C1~5v5x4Q6h0s6b5D040Q6s5N5%205H040q495-6u4r5P0@0v6B5|5(0K0S6F19636r6I2?0B0@0u1`1C5{6v1#5*5,6O6Q1#0V0v3e6X6D5}0@0r6H6Y3/6S042f6,4Z5(6!6`5/2?5=5@5_6~3L5~5 61746e0p5j3}3$4M7a5y4z3!3$5u265w675p5z7j5C3h6t7u6C6{70040m3O0D0G0u0p0C5V0L5X2y0u6;6-6J0@0d7M7x3o711X736$6=5)0@0z746E046G7X7N205*0U787*5e5g7o7c3c3 7f7=6f7q3}3 7l276l4,6n7_3G7v6t6%3/0@0J7R6 1#0K7P8d4s6F7/2.657{7b694k5m8o7h5r0s4l807n7|7i8r2F7t877w8e0/6x0S1L1X8i7%8c6O8G3L8g04020w0o0c8N4!6)0@0k8Z6J6L041`0e8(7y1,5^5`7:8H7Z047#8?8j048P2,8R4 8T0s8.6(6*043f8{4 7-940/8T8V8X9c3M0@7A1X7D7F7H7J5Y7$6.04606O628m4r7a7@0s4C7`826g4j3c4C8y9E7}9H7s6r8F7u899i048:7W9x7S0/5*8`9W8@5;8}9r6|0@7.8Q9R8T7Q9-7Y9%9U8=9#757!9)7y8~3j904!929h8#979|6Z9+8l588n5o9A4T9D7o8u6n4T9Jag6m9G0sae869P889=8b9h9/9h9%9~3Ia07O04939;7+956+9v798o9A4/af8A8v4/akaP6naNaq879R9?5?7V9^aaaG9Y9{994!aya6a)049,8 9.8haF9X9S9k7C7E7G5W5Y9qa^8@0R5l04030Q0l2t5W0g2ya95a0b5c4@564_531a0o4|bm2L2Ga!bj0b4`620Y0!0$0i04.

Évaluations restantes : 5/5

.128013/;=d(ls30v2t_f,-Srig85[7baeP:u)yjon4hk6 cwp]m1050e0B0m0A0t0g0h0O0P0g0A0h0h0d010m0t0R010406050h0E0T0T0A0s0G040r0I0g0E0/0I0J050b0_0{0}0 0@0R04051f181i0b1f0@0e0t0k0%0)0+0-0)0J0u0E0A0u0B0q0R0G0m0L160O0L0t0u0L0g1K0L0m0=050Y0z0g0B1r0*0,011J1L1N1L0m1T1V1R0m0s1g1F0%120h0R0A0J0-0l011X1t010o0!0B0J0A0T0B1R1?1^1}1Z201V23250=0a0O0C0s0I0R0I0h0t150J0O0W1;0s0s0B0P2q18280J1g0b1F2D1-1/1.1S0e2a1u0t0J222n1R1o1q0(1Y2N2P0J0I2T1R0R2w1g2B2D2*0^1@2r2V1~2Z0s0|0g1R0A1I2w0o0-030n0n0P2!0B1N2Y0I0q0U0U380=0U180A2+2.0?2-292:1Z2=2@2_2{0B2}012 3133352Q383a1{040l3e3g1^3i2B2M013n0A2^1g2`0L2|2~30320W3x2Z3z0q0i0=0i3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390q0K0=0K3%193)3j2/1s3m0I2?3M3p3Q3r3S3v3V3_3X3{0w0=0w402*3*2.3J3.4a3=3u3U344g373{0N0=0N4m423+453-473o3O3q3s4u3^363Y0y0=0y4D3G4o3k4G3K4I494K4b4M3@4f4P3{0v0=0v4U2C1j2(182T2G0e1/2L3,014v2S1p1g2%0B2)3h3(3G054v55290t0e0-302B3Y0U3p5d5f4e4w4+3a5j0O2e0B5m4v3W4y5q1R0b3f433J0M0=0W0o572C0O5D4}0J0o0=1-0t0n2O0h0B0s2z41584F2W010;040f5J5b445$0J5Q0A1U0B0A0E5+5M4Y5(0F0D5+0@5Z4;3I5l015g2.3Y3B3:0O644)5o3`3A1|5t5v4O6f0q695B040O6q5L5#1~5F040o475+6s4p5N0=0t6z5`5$0I0Q6D17616p6G2;0z0=0s1^1A5_6t1Z5(5*6M6O1Z0T0t3c6V6B5{0=0p6F6W3-6Q042d6*4X5$6Y6^5-2;5:5=5@6|3J5|5}5 726c0n5h3{3!4K785w4x3Y3!5s245u655n5x7h5A3f6r7s6A6_6~040k3M0B0E0s0n0A5T0J5V2w0s6/6+6H0=0d7K7v3m6 1V716!6:5%0=0x726C046E7V7L1~5(0S767(5c5e7m7a3a3}7d7:6d7o3{3}7j256j4*6l7@3E7t6r6#3-0=0H7P6}1Z0I7N8b4q6D7-2,637_79674i5k8m7f5p0q4j7~7l7`7g8p2D7r857u8c0-6v0Q1J1V8g7#8a6M8E3J8e04020u0m0c8L4Y6%0=0j8X6H6J041^0e8$7w1*5?5^7.8F7X047Z8;8h048N2*8P4}8R0q8,6$6(043d8_4}7+920-8R8T8V9a3K0=7y1V7B7D7F7H5W7!6,045~6M608k4p787=0q4A7^806e4h3a4A8w9C7{9F7q6p8D7s879g048.7U9v7Q0-5(8^9U8=5/8{9p6`0=7,8O9P8R7O9+7W9#9S8:9Z737Y9%7w8|3h8~4Y909f8Z959`6X9)8j568l5m9y4R9B7m8s6l4R9Hae6k9E0qac849N869:899f9-9f9#9|3G9~7M04919/7)936)9t778m9y4-ad8y8t4-aiaN6laLao859P9;5;7T9?a8aE9W9_974Yawa4a%049*8}9,8faD9V9Q9i7A7C7E5U5W9oaH6!0b5a4=544@51180m4`b82J2EaYb50b4^600W0Y0!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$.