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_4:L2-.Sw3z/]+7ÀbpPiNqI{oFê1tl(9^ ;=vTm6u8RsèfrO}gàe[hcDé05a,nkydx)050?0$0F0.0w0G0U0K0)0G0.0U0U0M010F0w0u010406050U0R0P0P0.0X0=040k0B0G0R190B0:0K020.0P0u0L0K0T0$1j0X0y0R0$0U050o1g1i1k1m1e0u04051R1K1U0o1R1e0?0w0N11131517130:0!0R0.0!0$0i0u0=0F0(1t0K0(0w0!0(0G1}0(0F1c050|0t0G0$1%1416011|1~201~0F2628240F0X1S1^111p0U0u0.0:170h012a1)010W0~0$0:1x0$242s2u2z2c2C282F0P2H040a0K0v0X0B0u0B0U0w1s1u0`2q0X0X0$0)2$1K2J0:1S0o1^2=2m2o2n250?2L1*0w0:2E2Z241!1$122b2 310:0B35240u2+1S2:2=3i1f2t1u372A3b0X1j0G240.1{2+0W17030d0d0)3c0$203a0B0i0,0i0E1c0K0E1K0.3j3m1d3l2K3o2c3q3s3u3w0$3y013A3C3E3G323J0i2x040K0h3Q3S2u3U2:2~013Z0.3t1S3v0(3x3z3B3D0`3-3b3/0m3N0m3^2/3T1e3|3X173 410543453)473,303.3K0e3N0e4g1L4i3V3n1(3Y0B3r403#443%463+494v4b3K0-3N0-4B3i4j3m3}4n4L4r3*483F4R3I3K0Q3N0Q4X4D4k4G4m4I3!423$3(4)4u3H3/0r3N0r4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0S3N0S562;584F385b4J4o4q4N4s4P4+5j0i0I3N0I5o3{4!4l5t4{4p4}4O4*4a4-3L0,1c0E0,5G5q4#5c5v5N5y5P4,3/0E3M045+5X4E5Z5u4%5x4 5i4w3L3;0E3@0o3R4h3`1V3g1K352^0?2o2}5J4*341#1S3f0$3h3T612;054*6i2K0w0?173B2:5*3#6q6s5z5Q6v0K2P0$6y5(5B5,4g4@5s0;1c0`0W6k6o5r2A0l3N6Q5:5J0:0W6N0w0)1_0F0B0P0w0$6W6K2A1b040H6.5I5a0:1c3b0P0t2+1J4C626/2c6;0/6Q0K6X6_1c0)0w276-716l73176;0^0f6Q1e7g6R0K6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0K7M795s6`040`0t1r777O2A0B1c0M7V7i016+1c5W7p7o3k3|7z0d6u3K4d4|7/6G5`4d7E2Q7G5_4S0i7?3^7M7N7$7Q2C0:7#6^5s7Y047!7p78860t1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0^8a8n7X1c0i8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040l1|288I4#6N0$7T0F8^5J8d020G0F0L8f3i8-8E8t04888O5J6;7m7+8O7/7;0i4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200$0R8~5a8d953T978J018p9c7a9a309H8c1c0q9U3p8`8|9Q8o8B9$8F040o0o9)2c8L5~4Y9h9n9j4/9m9t8Y0i4/8!9{9p9}7J8+9y858.2c8:0w6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0%9.9B049D6,9G8r7$6;0p9f9=aE4!9i8T0i539`8$7H80539 aR7 5RaP9xa58,ad8:2+0F0R0X89aiau010;0)1c0O0X1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900!93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0U7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0C40c8b#0)5,030K2!0K1`0:02030m0I0L3v2t102m0B0R0N0+cL6j0o6n636h656e1K0F68dj2{2?0.7e2=661Q7q5J2+0P0d0W0.0;0$0d0(7?1C1E1G1I0Kce6l1X3U353}0.0?0P1t2#0w1`300W8d1QdQdSdU2$0i190F2k041C6%0$0Xd:0K2t0X0K1!6%0B6)6+7f1Y1T040z0Gc_001/2#d`000R1u400!4I2#0(2Q2L0wdI0j0K0g292j0$0.0Rd@0X0w102Ed@1k1x0V2m290?0Be91fd61,040B271}0.6)0wdw2E0F0K0DeE0K2m0wda1LeK0!040j1V3U1R0s110(0.dI7r0F0+0XeQdW0:0/c{1uc8d`1D2u2(c`130K0N409Fd_0)eUe`280K1IeV0+0!fa0K0#0Kf76m3E04bhah6ndKe,1e0R0G3U2004c`d70we~1`2+0:0NeH290w1i0+1!eQ1DeU786na@a_ddfs1KfD1efDc`3be}110{0F29fu29fic_eHeV7mfAfC0wfE0R0ue_aC2+fnfp3vf928a+f-0:2mfm0f7re5dz1re:d;d:d_0?2u10f7d^19eF2W2#eFeueret0K6?6n7Sgi0M0Kbxeu0q3O1K6n8C0of%05fDdYg1fb29fof7g7fbgagcfgge0~0KgheVglgld`gog5eA0Xgs0Kfl0Rd?0?gxdp28gzgBfs880KgFgH0K0igKf!0`04gNgP0of{7ohdhfe20g3v0n1teF292+g,0(290H0G000+0)1keVfe29frhacxfw0{fWfsgD8}h96h0^c_hpfR0Re9fo6%e=1He@e_e{1`gefF1u88e9d^0K0.fMeShIhE301v921AhKgLfse~0)00f?e?fq6nf;h`ha6Ch~0UeVd4g.0:gpeqg}es0Ren0Yf04IeV2(f70td712f=eVfKh.hC6nc/0 7f6ne+dN7ods0_1#d$dT0:dVdX6Zd!1TiId(e|d*2#d-0x8vg31j0@fP40f2eZd70X102(ipg_2870e11R2V32ic0Kec0Khxhzea30d{fOiK19i$hD6hh2h7h_hM3=fki$foad1keh1jf/0@1c090H5V0J0I09gN3ie~0Hfd0K1G0wfhi8jx1.0:2}0P0Dej2m0V100!e`jE0^iCi;040*g/fg0ueSho10hy0UfI0bg:f;i6f?ia3f0+c8gb0$fI1u0X0+40exeqd7idd5i)i+29i-ir102Y15ag1IjQ3UhifD0ceu6gd d_6)a+j=h,i_1ui|g=fhfLeS1`2(jfew1^ji0$jk04jm090We`0)0Ajo0I0Z0A0h0Zjr6Qh|i7eVfo1!g3ku7$jgkxfTkAjm0-0K09192Q10jo0SkO8rgOf}f(f}kdf20Ri!0VjIi)kk3vi`kohAkr2W2%hCkXkweik!jl0HkDkF0Ak%k)fPdJk-kKkMk/96h}f?kTjXcv5skYlajjlc0hlhk*lk0,0J0rlodcgPkc30c`f5hSf/0K0jlRf$k=gQk@gxfK19k|j{kje kll1hykp0?h~l41`kvjhlbkBldkE0.kGkIlm0J0A0m0,0ZkNjs9LlqjBlskVl-0Nks1u0EiChhfBdt0clLfHib10ec2920i8hoeZ0}0Gfgl:kZlyl?kIlH3`e~ezgz0u1qeyl.1ul i(a+101`0U0}eVf6hw0G0+2Qgbh:6hi3jajAi9j@j/0Fk9iE6eiE0{mt0U04.

Évaluations restantes : 5/5

.128013ùA_4:L2-.Sw3z/]+7ÀbpPiNqI{oFê1tl(9^ ;=vTm6u8RsèfrO}gàe[hcDé05a,nkydx)050?0$0F0.0w0G0U0K0)0G0.0U0U0M010F0w0u010406050U0R0P0P0.0X0=040k0B0G0R190B0:0K020.0P0u0L0K0T0$1j0X0y0R0$0U050o1g1i1k1m1e0u04051R1K1U0o1R1e0?0w0N11131517130:0!0R0.0!0$0i0u0=0F0(1t0K0(0w0!0(0G1}0(0F1c050|0t0G0$1%1416011|1~201~0F2628240F0X1S1^111p0U0u0.0:170h012a1)010W0~0$0:1x0$242s2u2z2c2C282F0P2H040a0K0v0X0B0u0B0U0w1s1u0`2q0X0X0$0)2$1K2J0:1S0o1^2=2m2o2n250?2L1*0w0:2E2Z241!1$122b2 310:0B35240u2+1S2:2=3i1f2t1u372A3b0X1j0G240.1{2+0W17030d0d0)3c0$203a0B0i0E3J1c0K0E1K0.3j3m1d3l2K3o2c3q3s3u3w0$3y013A3C3E3G323J0i2x040K0h3P3R2u3T2:2~013Y0.3t1S3v0(3x3z3B3D0`3,3b3.0m3M0m3@2/3S1e3{3W173~400542443(463+303-3K0e3M0e4f1L4h3U3n1(3X0B3r3 3!433$453*484u4a3K0-3M0-4A3i4i3m3|4m4K4q3)473F4Q3I3K0Q3M0Q4W4C4j4F4l4H3Z413#3%4(4t3H3.0r3M0r4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0S3M0S552;574E385a4I4n4p4M4r4O4*5i0i0I3M0I5n3`4Z4k5s4`4o4|4N4)494,3J0,1c0E0,5F5p4!5b5u5M5x5O4+3.0E0E5T3O0o3Q4g564D5Y5t4$5w4~5h4v3J3:0E3?5.3^2;1V3g1K352^0?2o2}5I4)341#1S3f0$3h3S5:634)6j2K0w0?173B2:5)3!6q6s5y5P6v0K2P0$6y5%5A5+2=5/4?5r0;1c0`0W6l6o5q2A0l3M6R5=5I0:0W6O0w0)1_0F0B0P0w0$6X6L2A1b040H6/5H590:1c3b0P0t2+1J4B3_6Y596=0/6R0K745r6{040)0w276.72636:2c6=0^0f6R1e7i6S0K6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610K7N797k4l6O0$0t1r787a2A0B1c0M7W7Q016,1c5V7r7q3k3{7B0d6u3K4c4{7:6G5|4c7G2Q7I5{4R0i7@3@7O7P6_7b1c2C0:7$877Y7!8c587b0t1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0^8g8z177Z040i8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040l1|288J6Z7S7U0F8^598G020G0F0L7#7r868n8t048a8P5I6=7o7,8P7:7=0i4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200$0R8}5r8G943i968E016=8q7.8d989a958.018G0q9F3p8`7V8r7%7m9b8~1c0o0o9)5r8L608O9$4Z9h8U0i4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0w6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0%9.9Z049B6-9E9?au9M1c0p9e9=at1u9^2u518W9}9o0i528#aR5A528+a7a79U8:2+0F0R0X8bad9Q8/0)1c0O0X1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0!92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0U7hb?9c1cbF5;bHaN0:5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0w5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0;a:040C3 c8cN3k0o6n646i666f1K0F69c~2{2?0.7g2=671Q7s5I2+0P0d0W0.0;0$0d0(7@1C1E1G1I0Kcd631X3T353|0.0?0P1t2#0w1`300W8G1Qdvdxdz2$0i190F2k041C6(0$0XdR0K2t0X0K1!6(0B6*6,7h1Y1T040z0G0K0U001/2#dY000R1u3 0!4H2#0(2Q2L0wdn0j0K0g292j0$0.0RdV0X0w102EdV1k1x0V2m290?0Bd=1f2m1t0!040B271}0.6*0wdb2E0F0K0Dek0K2m0w0+2/eq1,040j1V3T1R0s110(0.dn7t0F0+0XexdB0:0/0K1`c8dY1D2u2(2!0K130K0N3 9DdX0)eBe!280K1IeC0+0!e^0K0#e;3v056nbh7h6ndpeP1e0R0G3T2004e:0B0R0we(1`2+0:0Nen290w1i0+1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0F29fbe 0UeC0UeneC7ofhfj0wfl0R0ueZaC2+f5f7e?e^a*fR0:2mf40f7td-de1reTdSdRdX0?2u10e=dW19el2W2#eleae7e90K6@6nbZg00M0Kb+ea0q3N1K6n8C0ofL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0Kf eCg3g3dYg6f;g96-0Kf30RdU0?gfd428ghgjfJ8a0Kgngp0K0igsfI0`04gvgx0of%7qg|g~d*0g3v0n1tel292+gS0(290H0G000+0)1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0^d.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0K0.fuezfEhn1u9092e,b!hx04e(0)00f00KeWe=ht6ifbhpg_6Ch,fXeg10g50:g7e6g)e80Re30Y1ufZ0XeC2(e=0tfn12290{0KfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0:dAdC6!dF1TixdJe$dL2#dO0xbr291j0@fx3 e,eGfn0Xh}29idg#2871d)1R2V32h 0Kd^0Khghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0@1c090H5U0J0I09gv3ie(0He{h.fofWeC2m0V100!e!0:0?0^iri$040*gVe~0uezh710hh0Ufq0bf;fV0:h`eC2t103f0+c8f_0$fq1u0X0+3 ede6fni0106*a*iW0KiYifjS2Z2!7g0Ujy3Th1fk0cea6hd%dXj,0XjYhTi+1ui.i9e ftez1`2(j4ec1^j70$j904jb090We!0)0Ajd0I0Z0A0h0Zjg6Rh*jPf:1!f/kf7%j5kifBkljb0-0K09192Q10jd0Skz8rgwf)fMf)j~e,0RiP0Vd k3k53vi,k9hjkc2W2%hlkHkhd~kKja0Hkokq0AkNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0hl1kQl40,0J0rl86kkXf(040c30e:e/hD290jlC1Kgxj}gffs19k)j(a*k,k7i-hhka0?h,k;1`kgj6k{kmk}kp0.krktl60J0A0m0,0Zkyjhamlah{lcjFd?2E0Nkd1u0Eirh0fid8lwh fpgUi*d^2920fXh7eG0}0Ge~lWkJlilZktlr3_e(efgh0u1qeelU1ul,iTj-e)i70}fY0we;hf0G0+2Qf_hXg_h?h(joebjUeBj`it6fit0{me0U04.

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_4:L2-.Sw3/]+7bpPiNqIo1tl(9î ;=vTm6u8Rs*èCfrOgàe[hEcDé05a,nkydx)050.0W0y0)0s0z0N0D0!0z0)0N0N0F010y0s0q010406050N0K0I0I0)0S0-040i0w0z0K140w0+0D020)0I0q0E0D0M0W1e0S0u0K0W0N050l1b1d1f1h190q04051M1F1P0l1M190.0s0G0|0~10120~0+0U0K0)0U0W0g0q0-0y0Y1o0D0Y0s0U0Y0z1^0Y0y17050@0p0z0W1Y0 11011@1_1{1_0y21231 0y0S1N1:0|1k0N0q0)0+120f01251!010R0_0W0+1s0W1 2n2p2u272x232A0I2C040a0D0r0S0w0q0w0N0s1n1p0=2l0S0S0W0!2X1F2E0+1N0l1:2-2h2j2i200.2G1#0s0+2z2U1 1V1X0}262`2|0+0w301 0q2$1N2+2-3d1a2o1p322v360S1e0z1 0)1?2$0R12030b0b0!370W1{350w0g0f0g0x170D0x1F0)3e3h183g2F3j273l3n3p3r0W3t013v3x3z3B2}3E3E3I0f3L3N2p3P2+2_013U0)3o1N3q0Y3s3u3w3y0=3(363*0k3I0k3.2*3O193=3S123^3`053|3~3!403%2{3)3F0c3I0c491G4b3Q3i1Z3T0w3m3_3W3}3Y3 3$424o443F0(3I0(4u3d4c3h3?4g4E4k3#413A4K3D3F0J3I0J4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0o3I0o4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0L3I0L4 2,514y33544C4h4j4G4l4I4!5c0g0B3I0B5h3;4T4e5m4;4i4?4H4Z434$3G0%170x0%5z5j4U555o5G5r5I4#3*0x3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0l3M4a3:1Q3b1F302:0.2j2^5C4Z2 1W1N3a0W3c3O5`2,054Z6b2F0s0.123w2+5Z3W6j6l5s5J6o0D2K0W6r5X5u5#494-5l0,170=0R6d6h5k2v0j3I6J5)5C0+0R172{1V0!0W6P6D2v16040A6Z5B530+172e0W0)0K6)525l6$0*6J0D6Q6+170!0s226Y4v5{6!276$0:0d6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040D7z6{754f6G0W0p1m6`6|5l0w170F7I7C010I0s175P7c3P7V5)7m0b6n3F464=7Z6z5:467r2L7t5/4L0g7%3.7A7B6*5l6,042x0+7O7`2v7L047N7V7_6?3k0p172J6=6L76176(7X7P7|6.6:8d3?77808827830g8q8e127R5N7a8n7Z7#0g4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040j1@238v4U7E7G0y8#5C83020z0y0E853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0W6;869l12838;3O8?8o8g8{6}040=8(8*53830n9G7{8_2{9B6@170:9K82170l0l9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0s6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0X9O3k9n0_0s9qan8f040m8~9$8i4T8C9*0g4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0g5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0)718mazaX01alataea$asbm8@6$aw8Abu0DaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0y0K0S7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0N72aibn8}byb~1pbB0+5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0x7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010,0!170t1ob}4w7X0l6g5|6a5~671F0y61c@2?2.bj232-5 1L6K3?2$0I0b0R0)0,0W0b0Y7%1x1z1B1D0Dax6c1S3P303?0)0.0I1o2W0s1=2{0R831Ldodqds2X0g140y2f041x0!0Y0W0SdK246W1;0y0w7RdgbA0y0$0S0)140G240d0D0V2l0+2A0C2h721T1O040v0z0D0N001*2W0D2Z0zd{0z0U4B2W0Y2Ld~242$dOdNdLd~0sdK0wdSdU1C2G0sdg0h1Q7Wd00;1WdAdr0+dtdv6Sdy1OeudCduc5dFdH0e3qeadLecdP24e06VefdP0K0Db!epd10e240!3_0!0Kd^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0w0s0{dg0zdg0{3y1d2z0@0s2$0N0h0D0v6 0D1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10T0S0*d~2pf0dMf40+0{flfn0{2Zfe0UdZ1I2X2lf20D230D0Qf,0~0Df40zg30=0{f3ar0Sgd0N0yg20s7RdX0Wf80QeZe#e%6{4Zfk2pfm1+1-0-fq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0q9qgj2o0Sdxe{0D0W0/0!0$0=0S0|0?0ye?0^gaeOgle=f80Z1p3Y0R0?f,2Vg2dh0=0K0/bA0+6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0N1ogjf|2p0.0Ng69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0Dg?1md~0$2o10dMg23q0G3_h/gkgmgoeWd=0#f.h40|0 fc3igsg3ePhreRe-eUcteT2z0D1maq0N2pgjg70~0S1+bUe8g2e*0+h60Simh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0$b|iZh.ic2R220Pe72|d_242Tb|iciye!f+g}1p0r1/1;0+h.gdiZgf0{0+00h(jMf_h70_iChbh6f80H0we^g{h-0D0i0siX1=0)imd}1eew0qe%0$e8j!dT0pf60D0R0zeh0@iZf?jJjD0zjF24b|dZd}0)0qg_eTf1e7g_g}0/1y0qg38~d;dn5Cdpevexhf0/1skz2MdzkEdBewdDeG2M0Zkx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0Q1oh%g30i1D2V1o6P696K3/6ec/cDb(7i0k3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0U6$020U8/ltlvlu1vbqaTi|jggLg,6T9!0h7Uj6gK0O0OfY5$0%0f48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0El^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0!5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0.ig261yf3m!kp0)m%k4kcggiWg7h;2Ln37Ymjl80g9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040L0h0B0L0L0c0J0(0J0o0c0k5!0(0L0W0n0k0%4~lT3fjnc;1S5}0lerp4677bp50=g90N04.

Évaluations restantes : 5/5

.128013_4:L2-.Sw3/]+7bpPiNqIo1tl(9î ;=vTm6u8Rs*èCfrOgàe[hEcDé05a,nkydx)050.0W0y0)0s0z0N0D0!0z0)0N0N0F010y0s0q010406050N0K0I0I0)0S0-040i0w0z0K140w0+0D020)0I0q0E0D0M0W1e0S0u0K0W0N050l1b1d1f1h190q04051M1F1P0l1M190.0s0G0|0~10120~0+0U0K0)0U0W0g0q0-0y0Y1o0D0Y0s0U0Y0z1^0Y0y17050@0p0z0W1Y0 11011@1_1{1_0y21231 0y0S1N1:0|1k0N0q0)0+120f01251!010R0_0W0+1s0W1 2n2p2u272x232A0I2C040a0D0r0S0w0q0w0N0s1n1p0=2l0S0S0W0!2X1F2E0+1N0l1:2-2h2j2i200.2G1#0s0+2z2U1 1V1X0}262`2|0+0w301 0q2$1N2+2-3d1a2o1p322v360S1e0z1 0)1?2$0R12030b0b0!370W1{350w0g0c0g0x170D0x1F0)3e3h183g2F3j273l3n3p3r0W3t013v3x3z3B2}3E0g2s040D0f3L3N2p3P2+2_013U0)3o1N3q0Y3s3u3w3y0=3(363*0k3I0k3:2*3O193@3S123`3|053~403!423%2{3)3F0c3I0c4b1G4d3Q3i1Z3T0w3m3{3W3 3Y413$444q463F0(3I0(4w3d4e3h3^4i4G4m3#433A4M3D3F0J3I0J4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0o3I0o4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0L3I0L512,534A33564E4j4l4I4n4K4$5e0g0B3I0B5j3?4V4g5o4?4k4^4J4#454(3G0%170x0%5B5l4W575q5I5t5K4%3*0x3H045$5S4z5U5p4Y5s4`5d4r3G3,0x3/0l3M4c3=1Q3b1F302:0.2j2^5E4#2 1W1N3a0W3c3O5|2,054#6d2F0s0.123w2+5#3W6l6n5u5L6q0D2K0W6t5Z5w5%4b4/5n0,170=0R6f6j5m2v0j3I6L5+5E0+0R172{1V0!0W6R6F2v16040A6#5D550+172e0W0)0K6+545n6(0*6L0D6S6-170!0s226!4x5}6$276(0:0d6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0D7B6~5n6.040=0p1m6|7D2v0w170F7K77120I0s175R7e3P7X5+7o0b6p3F484@7#6B5=487t2L7v5;4N0g7)3:7B7C7R3_172x0+7Q6,5n7N047P7X6}7|0+0p172J6@6N78176*7Z896/0)736=8e3^79816^7M170g8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040j1@238x4W6I0W7I0y8(5E84020z0y0E863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0W6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840n8.6 047 8 558r9N9J9z170l0l9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0s6K9Y8{4h70728%a69E8:8=0E9(3k8l8n9w9Ia79F170X9V7E179t0s9var6%170m929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0gaI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0g5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0y0K0S80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0N74bF8q17aB4ybubH0+5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0,0!170t1oc19Cb60!5%030D0i0s0D1=0+02030k0B0E3q0Sav1p2h0w0K0G0$bE6e0l6i5~6c60691F0y63di2?2.8m232-611L6M3^2$0I0b0R0)0,0W0b0Y7)1x1z1B1D0Dc55}1S3P303^0)0.0I1o2W0s1=2{0R841LdPdRdT2X0g140y2f041x0!0Y0W0Sd/246Y1;0y0w7TdH0D2W0$0S0)140G240d0D0V2l0+2A0C2h741T1O040v0z0D0N001*2W0D2Z0zem0z0U4D2W0Y2Lep242$d?d=d:ep0sd/0wd`d|1C2G0sdH0h1Q7Ydr0;1Wd#dS0+dUdW6UdZ1OeVd%dVc9d*d,0ed12%d:eDd@24er6XeGd@0K0Db(eQds0e240!3{0!0Kejeq00e^6Zepe{b(e|e02W24d`1m3Y0w0s0{dH0zdH0{3y1d2z0@0s2$0N0h0D0v71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe}cu8u85bg9Gax9K8+9Mc$cWcCfZ9r9Ubu90170:cs9#9%f/a.049,db6iePdMds0T0S0*ep2pfrd;fv0+0{fMfO0{2ZfF0Ue11I2X2lft0D230D0Qg70~0Dfv0zgr0=0{fuav0SgB0N0ygq0s7T0y0$0Wfz0Qf1f3f56}4#fL2pfN1+1-0-fR2a1|1~dtbmcwbyf_f#f|ao6)f(a87Gf*8-g/f.f,an7Ff;c2f?04f^g`f`cD8Af dL6i0D0q9vgH2o0SdYfm0D0W0/0!0$0=0S0|0?0yfh0^gye?gJfgfz0Z1p3Y0R0?g72VgqdI0=0K0/d~0+6YdIfJ2Z5EfM1)gYfQ291`g%fVg}cqf+g03z3-0?gTfKhSgWhUfPg!hXfTg(cpaXc#h(0=3-0N1ogHgk2p0.0Ngu9vhph gphQf155hTfOgZg#hY2ch!9E7F9Lg_g|ad179Qg/g~aY3fdch)hbhdep0$2o10d;gq3q0G3{i7gIgKgNe~eg0#g9hq0|0 fDiT0zf4gre@hNe_fbe|bx9vhj1p1mbx0N2pgHgv0~0S1+bZezgqf80+hs0SiIhvdJh,hRidh/ifhWfShZg)b%i)cy3-b6ctipbving-isjih19HbAfW8}h{bkjga,ith$iojqan9XjncBh5g/cEh86gixh}g2ef1MiQgdhHiT0{3a0$c0i}i6hb2R220Pey2|ek242Tc0hbiUf2g6i+2P1/1;0+i6gBi}gD0{0+00i0j-ghht0_iZhxhsfz0Hd6hshhi5c?c^er1=0)iIeo1eeX0qf50$ezj}d{0pfx0D0R0zeI0@i}gej*j!0zj$24c0e1eo0)0qhfe{92efdO5EdQeWeYhB0/1s0qd,d!kRd$eXd(e+2M0Z0/1ykYeedNeUh.1%h:gZ3y1ph?jab62I2z2B170rj?1=0Q1oh gr0i1D2V1o6R6b6M3;6gdd96b,7k0(3Gb/cR4|lm3Hb?bM46lr2t5a5Jce0glwb`b60U6(020U8?lHlJlI1vg=7}g@crh4g.jD9)6Vf~0h7WlUf!0O0Oh65P0%0f4acGc7a?99lmcKd~cMlAl;chb:3)l_5X5:b1lB3+7y5{7|lF17lK0Em8m86}f=9Sg 9C7{f-7OcDlW0flYg-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_kK0)m|kpkxgEi`gvi92LnmdtmDlm9~mGmLmI4*nanDo5nBl 6vo0m3jb5neu6W6Un}7!n1m1aSo2nylmaNnxlunuaRnd5/opovnFcWm604mWnJmYjAiljynRg/f%nLaim*lS8wjxlQh%m nWh2nYmqn$94oHl?npn2a}bLnblm5go6n7o-ow5botm1b3nioB840L0h0B0L0L0c0J0(0J0o0c0k5$0(0L0W0n0k0%50mBh|df1S5 0leSpm697dpn0=gx0N04.

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

.128013l( _4:;=vm26j-uSws3/]+fr7gebh[pPic5a,onkyd1)t050Q0B0T0K0H0b0s0d0I0b0K0s0s0i010T0H0F010406050s0p0k0k0K0y0P040q0M0b0p0.0M0N050u0^0`0|0~0?0F04051e171h0u1e0?0Q0H0j0$0(0*0,0(0N0A0p0K0A0B0o0F0P0T0D150d0D0H0A0D0b1J0D0T0;050X0C0b0B1q0)0+011I1K1M1K0T1S1U1Q0T0y1f1E0$110s0F0K0N0,0l011W1s010x0Z0B0N0K0k0B1Q1=1@1|1Y1 1U22240;0a0d0G0y0M0F0M0s0H140N0d0V1:0y0y0B0I2p17270N1f0u1E2C1,1.1-1R0Q291t0H0N212m1Q1n1p0%1X2M2O0N0M2S1Q0F2v1f2A2C2)0@1?2q2U1}2Y0y0{0b1Q0K1H2v0x0,030e0e0I2Z0B1M2X0M0o0z0o0R0;0R170K2*2-0=2,282/1Y2;2?2^2`0B2|012~3032342P370o1`040l3d3f1@3h2A2L013m0K2@1f2_0D2{2}2 310V3w2Y3y0t0;0t3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380f0;0f3#183%3i2.1r3l0M2=3L3o3P3q3R3u3U3@3W380J0;0J3}2)3(2-3I3,473:3t3T334d36380m0;0m4j3 3)423+443n3N3p3r4r3?353y0z0;0z4A3F1i2%172S2F0Q1.2K3*014s2R1o1f2$0B2(3g3$4S4s4-280H0Q0,2 2A3y3a4H4@4_4b4t4M383a0d2d0B504s3V4v391Q0u3e403I0O0;0V0x4/2B5h4#0r0;0d5n4=412V3J0x0;1,0H0e0s332w2y3~4S4C5x0:040c5u5p4D3J5A0K1T0B0K0p5P5K1}5M0S0g5u0?5I5o3H4 014`2-3y3A3.0d5.3=4c533z1{57594L3^5}2C3e0d665t5!1Y5j040x445u684m4#0N0;0H6f5Q5x0M5r042N6m693+0C0;0y1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0S6t6C6o0;0o6%6N5x0k0H3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0e6/0N6l6G6g6-1}0M0;0i6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0o7J3D7i7j6S6b6d0y7y4n0;0n7%4#6p6k167r7k6v6x6z0B6{4#6E7_5R6j7B7:6S7v040w7+5R6/6;7D6(6@0L855x0N6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0N3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0H5m808a7A6V8r8m3I5M0E8s2:7)8,8k0;0v8d7u0;020b0T0h8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0v5(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;98a4a18t040v9_2)9Fahacak6@af4.9(9=at8:am7C2+0u4;4T4,4V4)170T4YaK2I2D9}2C4W5*0V0X0Z0s04.

Évaluations restantes : 5/5

.128013l( _4:;=vm26j-uS8ws3/]+fr7gebh[pPicé5a,onkyd1)t050S0C0V0M0I0b0t0d0J0b0M0t0t0i010V0I0G010406050t0p0k0k0M0z0R040q0O0b0p0:0O0P050v0`0|0~100^0G04051g191j0v1g0^0S0I0j0(0*0,0.0*0P0B0p0M0B0C0o0G0R0V0E170d0E0I0B0E0b1L0E0V0?050Z0D0b0C1s0+0-011K1M1O1M0V1U1W1S0V0z1h1G0(130t0G0M0P0.0l011Y1u010y0#0C0P0M0k0C1S1@1_1~1!211W24260?0a0d0H0z0O0G0O0t0I160P0d0X1=0z0z0C0J2r19290P1h0v1G2E1.1:1/1T0S2b1v0I0P232o1S1p1r0)1Z2O2Q0P0O2U1S0G2x1h2C2E2+0_1^2s2W1 2!0z0}0b1S0M1J2x0y0.030e0e0J2#0C1O2Z0O0o0r0o0T0?0T190M2,2/0@2.2a2;1!2?2^2`2|0C2~01303234362R390o1|040l3f3h1_3j2C2N013o0M2_1h2{0E2}2 31330X3y2!3A0u0?0u3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0f0?0f3%1a3)3k2:1t3n0O2@3N3q3R3s3T3w3W3_3Y3a0L0?0L3 2+3*2/3K3.493=3v3V354f383a0m0?0m4l413+443-463p3P3r3t4t3^373A0A0?0A4C3H1k2)192U2H0S1:2M3,014u2T1q1h2(0C2*3i3(4U4u4/2a0I0S0.312C3A3c4J4_4{4d4v4O3a3c0d2f0C524u3X4x3b1S0v3g423K0Q0?0X0y4;2D5j4%0s0?0d5p4@432X3L0y0?1.0I0e0t352y2A404U4E5z0=040c5w5r4F3L5C0M1V0C0M0p5R5M1 5O0U0g5w0^5K5q3J51014|2/3A3C3:0d5:3@4e553B1}595b4N3`5 2E3g0d685v5$1!5l040y465w6a4o4%0P0?0I6h5S5z0O5t042P6o6b3-0D0?0z1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0U6v6E6q0?0o6)6P5z0k0I3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0e6;0P6n6I6i6/1 0O0?0i6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0o7L3F7k7l6U6d6f0z7A4p0?0n7)4%6r6m187t7m6x6z6B0C6}4%6G7{5T6l7D7=6U7x040x7-5T6;6?7F6*6_0N875z0P6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0P3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0I5o828c7C6X8t8o3K5O0F8u2=7+8.8m0?0w8f7w0?020b0V0h8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0w5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720o4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040w9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0J4 030d0K0J0E7_7E2-0v4?4V4.4X4+190V4!a!2K2Fa02E4Y5,0X0Z0#0t04.

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

.128013l( _4:;=vm26j-uS8ws3è/]fr7Ogebh[pPic05a,onkyd1)t050T0D0W0N0J0b0t0d0K0b0N0t0t0i010W0J0H010406050t0p0k0k0N0z0S040q0P0b0p0;0P0Q050w0{0}0 110_0H04051h1a1k0w1h0_0T0J0j0)0+0-0/0+0Q0C0p0N0C0D0o0H0S0W0F180d0F0J0C0F0b1M0F0W0@050!0E0b0D1t0,0.011L1N1P1N0W1V1X1T0W0z1i1H0)140t0H0N0Q0/0l011Z1v010y0$0D0Q0N0k0D1T1^1`1 1#221X25270@0a0d0I0z0P0H0P0t0J170Q0d0Y1?0z0z0D0K2s1a2a0Q1i0w1H2F1/1;1:1U0T2c1w0J0Q242p1T1q1s0*1!2P2R0Q0P2V1T0H2y1i2D2F2,0`1_2t2X202#0z0~0b1T0N1K2y0y0/030e0e0K2$0D1P2!0P0o0U0L3a0@0U1a0N2-2:0^2/2b2=1#2@2_2{2}0D2 01313335372S3a3c1}040l3g3i1`3k2D2O013p0N2`1i2|0F2~3032340Y3z2#3B0o0u0@0u3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0o0f0@0f3)1b3+3l2;1u3o0P2^3O3r3S3t3U3x3X3{3Z3}0M0@0M422,3,2:3L3:4c3@3w3W364i393}0m0@0m4o443-473/493q3Q3s3u4w3`383!0A0@0A4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0r0@0r4W2E1l2*1a2V2I0T1;2N3.014x2U1r1i2)0D2+3j3*3I054x572b0J0T0/322D3!0U3r5f5h4g4y4-3c5l0d2g0D5o4x3Y4A5s1T0w3h453L0R0@0Y0y594?4H2Y010s0@0d5L5d465O0Q0y0@1/0J0e2Q0t0D0z2B435a5N200?040c5T5F4 0Q5Z0N1W0D0N0p5?5.1#5:0V0g5T0_5,5M4r5n015i2:3!3D3=0d6b4+5q3|3C1~5v5x4Q6m0o6g5D040d6x5S610/5H040y495T6z4r5^0@0J6G5@4!0P5Q042Q6M6A3M0E0@0z1`1C606I4!5:5=685U3L0k0J3e6#4Z5O5:0O6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0V64666~6i5g6c0e5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0j3O0D0p0z0e0N5$0Q5(2y0z6^7H1#0P0@0i7W6 3o5`5|5~7h4 5:0G7,4!756L7a6U5:0x7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040n7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0s1L1X8m6J8k8W6O0@020C0W0h8Z5O6-0@0L8*206P0@1`0T8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0o8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0o4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0o4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0K5l04030d0B2t5%0v2yaL4?0w5c4@564_531a0W4|bn2L2G8{bk0w4`670Y0!0$0t04.

Évaluations restantes : 5/5

.128013l( _4:;=vm26j-uS8ws3/]fr7gebh[pPic05a,onkyd1)t050R0B0U0L0H0b0t0d0I0b0L0t0t0i010U0H0F010406050t0p0k0k0L0y0Q040q0N0b0p0/0N0O050v0_0{0}0 0@0F04051f181i0v1f0@0R0H0j0%0)0+0-0)0O0A0p0L0A0B0o0F0Q0U0D160d0D0H0A0D0b1K0D0U0=050Y0C0b0B1r0*0,011J1L1N1L0U1T1V1R0U0y1g1F0%120t0F0L0O0-0l011X1t010x0!0B0O0L0k0B1R1?1^1}1Z201V23250=0a0d0G0y0N0F0N0t0H150O0d0W1;0y0y0B0I2q18280O1g0v1F2D1-1/1.1S0R2a1u0H0O222n1R1o1q0(1Y2N2P0O0N2T1R0F2w1g2B2D2*0^1@2r2V1~2Z0y0|0b1R0L1I2w0x0-030e0e0I2!0B1N2Y0N0o0S0S380=0S180L2+2.0?2-292:1Z2=2@2_2{0B2}012 3133352Q383a1{040l3e3g1^3i2B2M013n0L2^1g2`0D2|2~30320W3x2Z3z0o0u0=0u3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390o0f0=0f3%193)3j2/1s3m0N2?3M3p3Q3r3S3v3V3_3X3{0K0=0K402*3*2.3J3.4a3=3u3U344g373{0m0=0m4m423+453-473o3O3q3s4u3^363Y0z0=0z4D3G4o3k4G3K4I494K4b4M3@4f4P3{0r0=0r4U2C1j2(182T2G0R1/2L3,014v2S1p1g2%0B2)3h3(3G054v55290H0R0-302B3Y0S3p5d5f4e4w4+3a5j0d2e0B5m4v3W4y5q1R0v3f433J0P0=0W0x574;4F2W010s0=0d5J5b445M0O0x0=1-0H0e2O0t0B0y2z41585L1~0;040c5R5D4}0O5X0L1U0B0L0p5;5,1Z5.0T0g5R0@5*5K4p5l015g2.3Y3B3:0d694)5o3`3A1|5t5v4O6k0o6e5B040d6v5Q5 0-5F040x475R6x4p5?0=0H6E5=4Y0N5O042O6K6y3K0C0=0y1^1A5~6G4Y5.5:665S3J0k0H3c6Z4X5M5.0M6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0T62646|6g5e6a0e5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0j3M0B0p0y0e0L5!0O5$2w0y6?7F1Z0N0=0i7U6}3m5^5`5|7f4}5.0E7*4Y736J786S5.0w7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040n7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0s1J1V8k6H8i8U6M0=020A0U0h8X5M6+0=0J8(1~6N0=1^0R8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0o8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0o4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0o4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0v5a4=544@51180U4`b92J2E8_b60v4^650W0Y0!0t04.

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