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

.1280133i}6z/hwnêlcefÀO5,^PyoF:xLurvt= d9s1Aaq4_IèRéT0+kùmp[b{;2Dà7-Sg]N8)(.050H0n0E0M0c0l0J0G0m0l0M0J0J0F010E0c0!010406050J0B0Z0Z0M0C0v040.0w0l0B190w0j0G020M0Z0!0(0G0S0n1j0C0N0B0n0J050g1g1i1k1m1e0!04051R1K1U0g1R1e0H0c0D11131517130j0/0B0M0/0n0-0!0v0E0h1t0G0h0c0/0h0l1}0h0E1c050|0$0l0n1%1416011|1~201~0E2628240E0C1S1^111p0J0!0M0j170)012a1)010o0~0n0j1x0n242s2u2z2c2C282F0Z2H040a0G0u0C0w0!0w0J0c1s1u0`2q0C0C0n0m2$1K2J0j1S0g1^2=2m2o2n250H2L1*0c0j2E2Z241!1$122b2 310j0w35240!2+1S2:2=3i1f2t1u372A3b0C1j0l240M1{2+0o17030P0P0m3c0n203a0w0-0V0-0K1c0G0K1K0M3j3m1d3l2K3o2c3q3s3u3w0n3y013A3C3E3G323J0-2x040G0)3Q3S2u3U2:2~013Z0M3t1S3v0h3x3z3B3D0`3-3b3/0b3N0b3^2/3T1e3|3X173 410543453)473,303.3K0O3N0O4g1L4i3V3n1(3Y0w3r403#443%463+494v4b3K0r3N0r4B3i4j3m3}4n4L4r3*483F4R3I3K0e3N0e4X4D4k4G4m4I3!423$3(4)4u3H3/0,3N0,4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0=3N0=562;584F385b4J4o4q4N4s4P4+5j0-0I3N0I5o3{4!4l5t4{4p4}4O4*4a4-3L0V1c0K0V5G5q4#5c5v5N5y5P4,3/0K3M045+5X4E5Z5u4%5x4 5i4w3L3;0K3@0g3R4h3`1V3g1K352^0H2o2}5J4*341#1S3f0n3h3T612;054*6i2K0c0H173B2:5*3#6q6s5z5Q6v0G2P0n6y5(5B5,4g4@5s0X1c0`0o6k6o5r2A0i3N6Q5:5J0j0o6N0c0m1_0E0w0Z0c0n6W6K2A1b040@6.5I5a0j1c3b0Z0$2+1J4C626/2c6;0s6Q0G6X6_1c0m0c276-716l73176;0?0y6Q1e7g6R0G6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0G7M795s6`040`0$1r777O2A0w1c0F7V7i016+1c5W7p7o3k3|7z0P6u3K4d4|7/6G5`4d7E2Q7G5_4S0-7?3^7M7N7$7Q2C0j7#6^5s7Y047!7p78860$1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0?8a8n7X1c0-8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040i1|288I4#6N0n7T0E8^5J8d020l0E0(8f3i8-8E8t04888O5J6;7m7+8O7/7;0-4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200n0B8~5a8d953T978J018p9c7a9a309H8c1c0W9U3p8`8|9Q8o8B9$8F040g0g9)2c8L5~4Y9h9n9j4/9m9t8Y0-4/8!9{9p9}7J8+9y858.2c8:0c6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0#9.9B049D6,9G8r7$6;0:9f9=aE4!9i8T0-539`8$7H80539 aR7 5RaP9xa58,ad8:2+0E0B0C89aiau010X0m1c0U0C1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900/93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0J7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0x40c8b#0m5,030G2!0G1`0j02030b0I0(3v2t102m0w0B0D0TcL6j0g6n636h656e1K0E68dj2{2?0M7e2=661Q7q5J2+0Z0P0o0M0X0n0P0h7?1C1E1G1I0Gce6l1X3U353}0M0H0Z1t2#0c1`300o8d1QdQdSdU2$0-190E2k041C6%0n0Cd:0G2t0C0G1!6%0w6)6+7f1Y1T040Q0lc_001/2#d`000B1u400/4I2#0h2Q2L0cdI0^0G0A292j0n0M0Bd@0C0c102Ed@1k1x0R2m290H0we91fd61,040w271}0M6)0cdw2E0E0G0keE0G2m0cda1LeK0/040^1V3U1R0p110h0MdI7r0E0T0CeQdW0j0sc{1uc8d`1D2u2(c`130G0D409Fd_0meUe`280G1IeV0T0/fa0G0+0Gf76m3E04bhah6ndKe,1e0B0l3U2004c`d70ce~1`2+0j0DeH290c1i0T1!eQ1DeU786na@a_ddfs1KfD1efDc`3be}110{0E29fu29fic_eHeV7mfAfC0cfE0B0!e_aC2+fnfp3vf928a+f-0j2mfm0y7re5dz1re:d;d:d_0H2u10f7d^19eF2W2#eFeueret0G6?6n7Sgi0F0Gbxeu0W3O1K6n8C0gf%05fDdYg1fb29fof7g7fbgagcfgge0~0GgheVglgld`gog5eA0Cgs0Gfl0Bd?0Hgxdp28gzgBfs880GgFgH0G0-gKf!0`04gNgP0gf{7ohdhfe20A3v0f1teF292+g,0h290@0l000T0m1keVfe29frhacxfw0{fWfsgD8}h96h0?c_hpfR0Be9fo6%e=1He@e_e{1`gefF1u88e9d^0G0MfMeShIhE301v921AhKgLfse~0m00f?e?fq6nf;h`ha6Ch~0JeVd4g.0jgpeqg}es0Ben0qf04IeV2(f70$d712f=eVfKh.hC6nc/0 7f6ne+dN7ods0_1#d$dT0jdVdX6Zd!1TiId(e|d*2#d-0;8vg31j0zfP40f2eZd70C102(ipg_2870e11R2V32ic0Gec0Ghxhzea30d{fOiK19i$hD6hh2h7h_hM3=fki$foad1keh1jf/0z1c090@5V0t0I09gN3ie~0@fd0G1G0cfhi8jx1.0j2}0Z0kej2m0R100/e`jE0?iCi;040*g/fg0!eSho10hy0JfI0Yg:f;i6f?ia3f0Tc8gb0nfI1u0C0T40exeqd7idd5i)i+29i-ir102Y15ag1IjQ3UhifD0Leu6gd d_6)a+j=h,i_1ui|g=fhfLeS1`2(jfew1^ji0njk04jm090oe`0m0%jo0I0d0%0)0djr6Qh|i7eVfo1!g3ku7$jgkxfTkAjm0r0G09192Q10jo0=kO8rgOf}f(f}kdf20Bi!0RjIi)kk3vi`kohAkr2W2%hCkXkweik!jl0@kDkF0%k%k)fPdJk-kKkMk/96h}f?kTjXcv5skYlajjlc0)lhk*lk0V0t0,lodcgPkc30c`f5hSf/0G0^lRf$k=gQk@gxfK19k|j{kje kll1hykp0Hh~l41`kvjhlbkBldkE0MkGkIlm0t0%0b0V0dkNjs9LlqjBlskVl-0Dks1u0KiChhfBdt0LlLfHib10ec2920i8hoeZ0}0lfgl:kZlyl?kIlH3`e~ezgz0!1qeyl.1ul i(a+101`0J0}eVf6hw0l0T2Qgbh:6hi3jajAi9j@j/0Ek9iE6eiE0{mt0J04.

Évaluations restantes : 5/5

.1280133i}6z/hwnêlcefÀO5,^PyoF:xLurvt= d9s1Aaq4_IèRéT0+kùmp[b{;2Dà7-Sg]N8)(.050H0n0E0M0c0l0J0G0m0l0M0J0J0F010E0c0!010406050J0B0Z0Z0M0C0v040.0w0l0B190w0j0G020M0Z0!0(0G0S0n1j0C0N0B0n0J050g1g1i1k1m1e0!04051R1K1U0g1R1e0H0c0D11131517130j0/0B0M0/0n0-0!0v0E0h1t0G0h0c0/0h0l1}0h0E1c050|0$0l0n1%1416011|1~201~0E2628240E0C1S1^111p0J0!0M0j170)012a1)010o0~0n0j1x0n242s2u2z2c2C282F0Z2H040a0G0u0C0w0!0w0J0c1s1u0`2q0C0C0n0m2$1K2J0j1S0g1^2=2m2o2n250H2L1*0c0j2E2Z241!1$122b2 310j0w35240!2+1S2:2=3i1f2t1u372A3b0C1j0l240M1{2+0o17030P0P0m3c0n203a0w0-0K3J1c0G0K1K0M3j3m1d3l2K3o2c3q3s3u3w0n3y013A3C3E3G323J0-2x040G0)3P3R2u3T2:2~013Y0M3t1S3v0h3x3z3B3D0`3,3b3.0b3M0b3@2/3S1e3{3W173~400542443(463+303-3K0O3M0O4f1L4h3U3n1(3X0w3r3 3!433$453*484u4a3K0r3M0r4A3i4i3m3|4m4K4q3)473F4Q3I3K0e3M0e4W4C4j4F4l4H3Z413#3%4(4t3H3.0,3M0,4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0=3M0=552;574E385a4I4n4p4M4r4O4*5i0-0I3M0I5n3`4Z4k5s4`4o4|4N4)494,3J0V1c0K0V5F5p4!5b5u5M5x5O4+3.0K0K5T3O0g3Q4g564D5Y5t4$5w4~5h4v3J3:0K3?5.3^2;1V3g1K352^0H2o2}5I4)341#1S3f0n3h3S5:634)6j2K0c0H173B2:5)3!6q6s5y5P6v0G2P0n6y5%5A5+2=5/4?5r0X1c0`0o6l6o5q2A0i3M6R5=5I0j0o6O0c0m1_0E0w0Z0c0n6X6L2A1b040@6/5H590j1c3b0Z0$2+1J4B3_6Y596=0s6R0G745r6{040m0c276.72636:2c6=0?0y6R1e7i6S0G6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610G7N797k4l6O0n0$1r787a2A0w1c0F7W7Q016,1c5V7r7q3k3{7B0P6u3K4c4{7:6G5|4c7G2Q7I5{4R0-7@3@7O7P6_7b1c2C0j7$877Y7!8c587b0$1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0?8g8z177Z040-8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040i1|288J6Z7S7U0E8^598G020l0E0(7#7r868n8t048a8P5I6=7o7,8P7:7=0-4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200n0B8}5r8G943i968E016=8q7.8d989a958.018G0W9F3p8`7V8r7%7m9b8~1c0g0g9)5r8L608O9$4Z9h8U0-4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0c6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0#9.9Z049B6-9E9?au9M1c0:9e9=at1u9^2u518W9}9o0-528#aR5A528+a7a79U8:2+0E0B0C8bad9Q8/0m1c0U0C1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0/92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0J7hb?9c1cbF5;bHaN0j5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0c5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0Xa:040x3 c8cN3k0g6n646i666f1K0E69c~2{2?0M7g2=671Q7s5I2+0Z0P0o0M0X0n0P0h7@1C1E1G1I0Gcd631X3T353|0M0H0Z1t2#0c1`300o8G1Qdvdxdz2$0-190E2k041C6(0n0CdR0G2t0C0G1!6(0w6*6,7h1Y1T040Q0l0G0J001/2#dY000B1u3 0/4H2#0h2Q2L0cdn0^0G0A292j0n0M0BdV0C0c102EdV1k1x0R2m290H0wd=1f2m1t0/040w271}0M6*0cdb2E0E0G0kek0G2m0c0T2/eq1,040^1V3T1R0p110h0Mdn7t0E0T0CexdB0j0s0G1`c8dY1D2u2(2!0G130G0D3 9DdX0meBe!280G1IeC0T0/e^0G0+e;3v056nbh7h6ndpeP1e0B0l3T2004e:0w0B0ce(1`2+0j0Den290c1i0T1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0E29fbe 0JeC0JeneC7ofhfj0cfl0B0!eZaC2+f5f7e?e^a*fR0j2mf40y7td-de1reTdSdRdX0H2u10e=dW19el2W2#eleae7e90G6@6nbZg00F0Gb+ea0W3N1K6n8C0gfL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0Gf eCg3g3dYg6f;g96-0Gf30BdU0Hgfd428ghgjfJ8a0Ggngp0G0-gsfI0`04gvgx0gf%7qg|g~d*0A3v0f1tel292+gS0h290@0l000T0m1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0?d.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0G0MfuezfEhn1u9092e,b!hx04e(0m00f00GeWe=ht6ifbhpg_6Ch,fXeg10g50jg7e6g)e80Be30q1ufZ0CeC2(e=0$fn12290{0GfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0jdAdC6!dF1TixdJe$dL2#dO0;br291j0zfx3 e,eGfn0Ch}29idg#2871d)1R2V32h 0Gd^0Ghghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0z1c090@5U0t0I09gv3ie(0@e{h.fofWeC2m0R100/e!0j0H0?iri$040*gVe~0!ezh710hh0Jfq0Yf;fV0jh`eC2t103f0Tc8f_0nfq1u0C0T3 ede6fni0106*a*iW0GiYifjS2Z2!7g0Jjy3Th1fk0Lea6hd%dXj,0CjYhTi+1ui.i9e ftez1`2(j4ec1^j70nj904jb090oe!0m0%jd0I0d0%0)0djg6Rh*jPf:1!f/kf7%j5kifBkljb0r0G09192Q10jd0=kz8rgwf)fMf)j~e,0BiP0Rd k3k53vi,k9hjkc2W2%hlkHkhd~kKja0@kokq0%kNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0)l1kQl40V0t0,l86kkXf(040L30e:e/hD290^lC1Kgxj}gffs19k)j(a*k,k7i-hhka0Hh,k;1`kgj6k{kmk}kp0Mkrktl60t0%0b0V0dkyjhamlah{lcjFd?2E0Dkd1u0Kirh0fid8lwh fpgUi*d^2920fXh7eG0}0le~lWkJlilZktlr3_e(efgh0!1qeelU1ul,iTj-e)i70}fY0ce;hf0l0T2Qf_hXg_h?h(joebjUeBj`it6fit0{me0J04.

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

.1280133i6/hîwEnlcCefO5,yPo:xLurvt= ds91aq4_IèRéT0+kmp[b;2D*à7-Sg]N8)(.050E0n0B0I0c0k0F0D0l0k0I0F0F0C010B0c0V010406050F0y0U0U0I0z0s040)0u0k0y140u0j0D020I0U0V0Y0D0O0n1e0z0J0y0n0F050e1b1d1f1h190V04051M1F1P0e1M190E0c0A0|0~10120~0j0*0y0I0*0n0(0V0s0B0f1o0D0f0c0*0f0k1^0f0B17050@0X0k0n1Y0 11011@1_1{1_0B21231 0B0z1N1:0|1k0F0V0I0j120Z01251!010o0_0n0j1s0n1 2n2p2u272x232A0U2C040a0D0t0z0u0V0u0F0c1n1p0=2l0z0z0n0l2X1F2E0j1N0e1:2-2h2j2i200E2G1#0c0j2z2U1 1V1X0}262`2|0j0u301 0V2$1N2+2-3d1a2o1p322v360z1e0k1 0I1?2$0o12030L0L0l370n1{350u0(0Z0(0H170D0H1F0I3e3h183g2F3j273l3n3p3r0n3t013v3x3z3B2}3E3E3I0Z3L3N2p3P2+2_013U0I3o1N3q0f3s3u3w3y0=3(363*0b3I0b3.2*3O193=3S123^3`053|3~3!403%2{3)3F0K3I0K491G4b3Q3i1Z3T0u3m3_3W3}3Y3 3$424o443F0q3I0q4u3d4c3h3?4g4E4k3#413A4K3D3F0d3I0d4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0%3I0%4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0-3I0-4 2,514y33544C4h4j4G4l4I4!5c0(0G3I0G5h3;4T4e5m4;4i4?4H4Z434$3G0R170H0R5z5j4U555o5G5r5I4#3*0H3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0e3M4a3:1Q3b1F302:0E2j2^5C4Z2 1W1N3a0n3c3O5`2,054Z6b2F0c0E123w2+5Z3W6j6l5s5J6o0D2K0n6r5X5u5#494-5l0T170=0o6d6h5k2v0h3I6J5)5C0j0o172{1V0l0n6P6D2v16040/6Z5B530j172e0n0I0y6)525l6$0r6J0D6Q6+170l0c226Y4v5{6!276$0.0v6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040D7z6{754f6G0n0X1m6`6|5l0u170C7I7C010U0c175P7c3P7V5)7m0L6n3F464=7Z6z5:467r2L7t5/4L0(7%3.7A7B6*5l6,042x0j7O7`2v7L047N7V7_6?3k0X172J6=6L76176(7X7P7|6.6:8d3?77808827830(8q8e127R5N7a8n7Z7#0(4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040h1@238v4U7E7G0B8#5C83020k0B0Y853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0n6;869l12838;3O8?8o8g8{6}040=8(8*53830S9G7{8_2{9B6@170.9K82170e0e9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0c6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0W9O3k9n0_0c9qan8f040+8~9$8i4T8C9*0(4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0(5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0I718mazaX01alataea$asbm8@6$aw8Abu0DaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0B0y0z7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0F72aibn8}byb~1pbB0j5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0H7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010T0l170,1ob}4w7X0e6g5|6a5~671F0B61c@2?2.bj232-5 1L6K3?2$0U0L0o0I0T0n0L0f7%1x1z1B1D0Dax6c1S3P303?0I0E0U1o2W0c1=2{0o831Ldodqds2X0(140B2f041x0l0f0n0zdK246W1;0B0u7RdgbA0B0P0z0I140A240v0D0$2l0j2A0g2h721T1O040M0k0D0F001*2W0D2Z0kd{0k0*4B2W0f2Ld~242$dOdNdLd~0cdK0udSdU1C2G0cdg0:1Q7Wd00;1WdAdr0jdtdv6Sdy1OeudCduc5dFdH0x3qeadLecdP24e06VefdP0y0Db!epd10x240l3_0l0yd^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0u0c0{dg0kdg0{3y1d2z0@0c2$0F0:0D0M6 0D1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10p0z0rd~2pf0dMf40j0{flfn0{2Zfe0*dZ1I2X2lf20D230D0mf,0~0Df40kg30=0{f3ar0zgd0F0Bg20c7RdX0nf80meZe#e%6{4Zfk2pfm1+1-0sfq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0V9qgj2o0zdxe{0D0n0w0l0P0=0z0|0?0Be?0^gaeOgle=f80i1p3Y0o0?f,2Vg2dh0=0y0wbA0j6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0F1ogjf|2p0E0Fg69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0Dg?1md~0P2o10dMg23q0A3_h/gkgmgoeWd=0!f.h40|0 fc3igsg3ePhreRe-eUcteT2z0D1maq0F2pgjg70~0z1+bUe8g2e*0jh60zimh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0Pb|iZh.ic2R220Ne72|d_242Tb|iciye!f+g}1p0t1/1;0jh.gdiZgf0{0j00h(jMf_h70_iChbh6f80Q0ue^g{h-0D0)0ciX1=0Iimd}1eew0Ve%0Pe8j!dT0Xf60D0o0keh0@iZf?jJjD0kjF24b|dZd}0I0Vg_eTf1e7g_g}0w1y0Vg38~d;dn5Cdpevexhf0w1skz2MdzkEdBewdDeG2M0ikx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0m1oh%g30)1D2V1o6P696K3/6ec/cDb(7i0b3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0*6$020*8/ltlvlu1vbqaTi|jggLg,6T9!0:7Uj6gK0#0#fY5$0R0Z48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0Yl^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0l5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0Eig261yf3m!kp0Im%k4kcggiWg7h;2Ln37Ymjl80(9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040-0:0G0-0-0K0d0q0d0%0K0b5!0q0-0n0S0b0R4~lT3fjnc;1S5}0eerp4677bp50=g90F04.

Évaluations restantes : 5/5

.1280133i6/hîwEnlcCefO5,yPo:xLurvt= ds91aq4_IèRéT0+kmp[b;2D*à7-Sg]N8)(.050E0n0B0I0c0k0F0D0l0k0I0F0F0C010B0c0V010406050F0y0U0U0I0z0s040)0u0k0y140u0j0D020I0U0V0Y0D0O0n1e0z0J0y0n0F050e1b1d1f1h190V04051M1F1P0e1M190E0c0A0|0~10120~0j0*0y0I0*0n0(0V0s0B0f1o0D0f0c0*0f0k1^0f0B17050@0X0k0n1Y0 11011@1_1{1_0B21231 0B0z1N1:0|1k0F0V0I0j120Z01251!010o0_0n0j1s0n1 2n2p2u272x232A0U2C040a0D0t0z0u0V0u0F0c1n1p0=2l0z0z0n0l2X1F2E0j1N0e1:2-2h2j2i200E2G1#0c0j2z2U1 1V1X0}262`2|0j0u301 0V2$1N2+2-3d1a2o1p322v360z1e0k1 0I1?2$0o12030L0L0l370n1{350u0(0K0(0H170D0H1F0I3e3h183g2F3j273l3n3p3r0n3t013v3x3z3B2}3E0(2s040D0Z3L3N2p3P2+2_013U0I3o1N3q0f3s3u3w3y0=3(363*0b3I0b3:2*3O193@3S123`3|053~403!423%2{3)3F0K3I0K4b1G4d3Q3i1Z3T0u3m3{3W3 3Y413$444q463F0q3I0q4w3d4e3h3^4i4G4m3#433A4M3D3F0d3I0d4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0%3I0%4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0-3I0-512,534A33564E4j4l4I4n4K4$5e0(0G3I0G5j3?4V4g5o4?4k4^4J4#454(3G0R170H0R5B5l4W575q5I5t5K4%3*0H3H045$5S4z5U5p4Y5s4`5d4r3G3,0H3/0e3M4c3=1Q3b1F302:0E2j2^5E4#2 1W1N3a0n3c3O5|2,054#6d2F0c0E123w2+5#3W6l6n5u5L6q0D2K0n6t5Z5w5%4b4/5n0T170=0o6f6j5m2v0h3I6L5+5E0j0o172{1V0l0n6R6F2v16040/6#5D550j172e0n0I0y6+545n6(0r6L0D6S6-170l0c226!4x5}6$276(0.0v6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0D7B6~5n6.040=0X1m6|7D2v0u170C7K77120U0c175R7e3P7X5+7o0L6p3F484@7#6B5=487t2L7v5;4N0(7)3:7B7C7R3_172x0j7Q6,5n7N047P7X6}7|0j0X172J6@6N78176*7Z896/0I736=8e3^79816^7M170(8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040h1@238x4W6I0n7I0B8(5E84020k0B0Y863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0n6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840S8.6 047 8 558r9N9J9z170e0e9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0c6K9Y8{4h70728%a69E8:8=0Y9(3k8l8n9w9Ia79F170W9V7E179t0c9var6%170+929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0(aI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0(5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0B0y0z80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0F74bF8q17aB4ybubH0j5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0T0l170,1oc19Cb60l5%030D0)0c0D1=0j02030b0G0Y3q0zav1p2h0u0y0A0PbE6e0e6i5~6c60691F0B63di2?2.8m232-611L6M3^2$0U0L0o0I0T0n0L0f7)1x1z1B1D0Dc55}1S3P303^0I0E0U1o2W0c1=2{0o841LdPdRdT2X0(140B2f041x0l0f0n0zd/246Y1;0B0u7TdH0D2W0P0z0I140A240v0D0$2l0j2A0g2h741T1O040M0k0D0F001*2W0D2Z0kem0k0*4D2W0f2Lep242$d?d=d:ep0cd/0ud`d|1C2G0cdH0:1Q7Ydr0;1Wd#dS0jdUdW6UdZ1OeVd%dVc9d*d,0xd12%d:eDd@24er6XeGd@0y0Db(eQds0x240l3{0l0yejeq00e^6Zepe{b(e|e02W24d`1m3Y0u0c0{dH0kdH0{3y1d2z0@0c2$0F0:0D0M71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe}cu8u85bg9Gax9K8+9Mc$cWcCfZ9r9Ubu90170.cs9#9%f/a.049,db6iePdMds0p0z0rep2pfrd;fv0j0{fMfO0{2ZfF0*e11I2X2lft0D230D0mg70~0Dfv0kgr0=0{fuav0zgB0F0Bgq0c7T0B0P0nfz0mf1f3f56}4#fL2pfN1+1-0sfR2a1|1~dtbmcwbyf_f#f|ao6)f(a87Gf*8-g/f.f,an7Ff;c2f?04f^g`f`cD8Af dL6i0D0V9vgH2o0zdYfm0D0n0w0l0P0=0z0|0?0Bfh0^gye?gJfgfz0i1p3Y0o0?g72VgqdI0=0y0wd~0j6YdIfJ2Z5EfM1)gYfQ291`g%fVg}cqf+g03z3-0?gTfKhSgWhUfPg!hXfTg(cpaXc#h(0=3-0F1ogHgk2p0E0Fgu9vhph gphQf155hTfOgZg#hY2ch!9E7F9Lg_g|ad179Qg/g~aY3fdch)hbhdep0P2o10d;gq3q0A3{i7gIgKgNe~eg0!g9hq0|0 fDiT0kf4gre@hNe_fbe|bx9vhj1p1mbx0F2pgHgv0~0z1+bZezgqf80jhs0ziIhvdJh,hRidh/ifhWfShZg)b%i)cy3-b6ctipbving-isjih19HbAfW8}h{bkjga,ith$iojqan9XjncBh5g/cEh86gixh}g2ef1MiQgdhHiT0{3a0Pc0i}i6hb2R220Ney2|ek242Tc0hbiUf2g6i+2P1/1;0ji6gBi}gD0{0j00i0j-ghht0_iZhxhsfz0Qd6hshhi5c?c^er1=0IiIeo1eeX0Vf50Pezj}d{0Xfx0D0o0keI0@i}gej*j!0kj$24c0e1eo0I0Vhfe{92efdO5EdQeWeYhB0w1s0Vd,d!kRd$eXd(e+2M0i0w1ykYeedNeUh.1%h:gZ3y1ph?jab62I2z2B170tj?1=0m1oh gr0)1D2V1o6R6b6M3;6gdd96b,7k0q3Gb/cR4|lm3Hb?bM46lr2t5a5Jce0(lwb`b60*6(020*8?lHlJlI1vg=7}g@crh4g.jD9)6Vf~0:7WlUf!0#0#h65P0R0Z4acGc7a?99lmcKd~cMlAl;chb:3)l_5X5:b1lB3+7y5{7|lF17lK0Ym8m86}f=9Sg 9C7{f-7OcDlW0ZlYg-l$l(5(l*l,l!27g{c.7|cE3Kl-c2c8m17^cLl{lv7@l`lpl|mJl~cjmM7^7zlElGlMmalMmch09SjklSjmmxjrh`6|cA5nc:17c=0EiC261yfui`f22o71gLda76aEl/c9lm8S7nl@aLm14tltcNn8lx4ZmPmIn4mSm584dXm~7fn0lkl:lBlonf3Dlm9gcQntm19gly5Yl^nrlDm5mUlLnIlNmd6_8hlOimg^jlbgiujtnnjBf@g-f{muf}jI7Ac/c;iBiDc02Li}m_kK0Im|kpkxgEi`gvi92LnmdtmDlm9~mGmLmI4*nanDo5nBl 6vo0m3jb5neu6W6Un}7!n1m1aSo2nylmaNnxlunuaRnd5/opovnFcWm604mWnJmYjAiljynRg/f%nLaim*lS8wjxlQh%m nWh2nYmqn$94oHl?npn2a}bLnblm5go6n7o-ow5botm1b3nioB840-0:0G0-0-0K0d0q0d0%0K0b5$0q0-0n0S0b0R50mBh|df1S5 0eeSpm697dpn0=gx0F04.

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

.1280133dsi6/h1wajn4_lcef5,+kmyPop[b;2:7-uSgrv]t=)( 050c0r0P0k0e0p0d0T0q0p0k0d0d0Q010P0e0B010406050d0J0x0x0k0M0y040K0A0p0J0.0A0m050g0^0`0|0~0?0B04051e171h0g1e0?0c0e0N0$0(0*0,0(0m0L0J0k0L0r0I0B0y0P0h150T0h0e0L0h0p1J0h0P0;050X0D0p0r1q0)0+011I1K1M1K0P1S1U1Q0P0M1f1E0$110d0B0k0m0,0F011W1s010s0Z0r0m0k0x0r1Q1=1@1|1Y1 1U22240;0a0T0z0M0A0B0A0d0e140m0T0V1:0M0M0r0q2p17270m1f0g1E2C1,1.1-1R0c291t0e0m212m1Q1n1p0%1X2M2O0m0A2S1Q0B2v1f2A2C2)0@1?2q2U1}2Y0M0{0p1Q0k1H2v0s0,030o0o0q2Z0r1M2X0A0I0H0I0i0;0i170k2*2-0=2,282/1Y2;2?2^2`0r2|012~3032342P370I1`040F3d3f1@3h2A2L013m0k2@1f2_0h2{2}2 310V3w2Y3y0b0;0b3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380n0;0n3#183%3i2.1r3l0A2=3L3o3P3q3R3u3U3@3W380t0;0t3}2)3(2-3I3,473:3t3T334d36380f0;0f4j3 3)423+443n3N3p3r4r3?353y0H0;0H4A3F1i2%172S2F0c1.2K3*014s2R1o1f2$0r2(3g3$4S4s4-280e0c0,2 2A3y3a4H4@4_4b4t4M383a0T2d0r504s3V4v391Q0g3e403I0w0;0V0s4/2B5h4#0j0;0T5n4=412V3J0s0;1,0e0o0d332w2y3~4S4C5x0:040S5u5p4D3J5A0k1T0r0k0J5P5K1}5M0R0G5u0?5I5o3H4 014`2-3y3A3.0T5.3=4c533z1{57594L3^5}2C3e0T665t5!1Y5j040s445u684m4#0m0;0e6f5Q5x0A5r042N6m693+0D0;0M1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0R6t6C6o0;0I6%6N5x0x0e3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0o6/0m6l6G6g6-1}0A0;0Q6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0I7J3D7i7j6S6b6d0M7y4n0;0l7%4#6p6k167r7k6v6x6z0r6{4#6E7_5R6j7B7:6S7v040v7+5R6/6;7D6(6@0u855x0m6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0m3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0e5m808a7A6V8r8m3I5M0C8s2:7)8,8k0;0O8d7u0;020p0P0E8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0O5(8w6{8A4{4w3o8A7d5|4x8K7R8N9l648Q8S9x7;6T5C7o9b3g8T3I827x8Z936T7*9h8(9j70379m7F9o624O9r8G7M7T4O9v9y6S7~8$6X9c8)0;8+8(6i6k96019e8c9J8U9)8 6W9?959:7}7m9C9 8;8}0,9Ha76T9*a5049/9,9;98a4a18t040O9_2)9Fahacak6@af4.9(9=at8:am7C2+0g4;4T4,4V4)170P4YaK2I2D9}2C4W5*0V0X0Z0d04.

Évaluations restantes : 5/5

.1280133dsi6/h1wajn4_lcefé5,+kmyPop[b;2:7-uSgrv]t=8)( 050c0r0Q0k0e0p0d0V0q0p0k0d0d0R010Q0e0C010406050d0K0y0y0k0N0z040L0B0p0K0:0B0m050g0`0|0~100^0C04051g191j0g1g0^0c0e0O0(0*0,0.0*0m0M0K0k0M0r0J0C0z0Q0h170V0h0e0M0h0p1L0h0Q0?050Z0E0p0r1s0+0-011K1M1O1M0Q1U1W1S0Q0N1h1G0(130d0C0k0m0.0G011Y1u010s0#0r0m0k0y0r1S1@1_1~1!211W24260?0a0V0A0N0B0C0B0d0e160m0V0X1=0N0N0r0q2r19290m1h0g1G2E1.1:1/1T0c2b1v0e0m232o1S1p1r0)1Z2O2Q0m0B2U1S0C2x1h2C2E2+0_1^2s2W1 2!0N0}0p1S0k1J2x0s0.030o0o0q2#0r1O2Z0B0J0S0J0i0?0i190k2,2/0@2.2a2;1!2?2^2`2|0r2~01303234362R390J1|040G3f3h1_3j2C2N013o0k2_1h2{0h2}2 31330X3y2!3A0b0?0b3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0n0?0n3%1a3)3k2:1t3n0B2@3N3q3R3s3T3w3W3_3Y3a0u0?0u3 2+3*2/3K3.493=3v3V354f383a0f0?0f4l413+443-463p3P3r3t4t3^373A0I0?0I4C3H1k2)192U2H0c1:2M3,014u2T1q1h2(0r2*3i3(4U4u4/2a0e0c0.312C3A3c4J4_4{4d4v4O3a3c0V2f0r524u3X4x3b1S0g3g423K0x0?0X0s4;2D5j4%0j0?0V5p4@432X3L0s0?1.0e0o0d352y2A404U4E5z0=040U5w5r4F3L5C0k1V0r0k0K5R5M1 5O0T0H5w0^5K5q3J51014|2/3A3C3:0V5:3@4e553B1}595b4N3`5 2E3g0V685v5$1!5l040s465w6a4o4%0m0?0e6h5S5z0B5t042P6o6b3-0E0?0N1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0T6v6E6q0?0J6)6P5z0y0e3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0o6;0m6n6I6i6/1 0B0?0R6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0J7L3F7k7l6U6d6f0N7A4p0?0l7)4%6r6m187t7m6x6z6B0r6}4%6G7{5T6l7D7=6U7x040w7-5T6;6?7F6*6_0v875z0m6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0m3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0e5o828c7C6X8t8o3K5O0D8u2=7+8.8m0?0P8f7w0?020p0Q0F8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0P5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720J4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040P9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0q4 030V0t0q0h7_7E2-0g4?4V4.4X4+190Q4!a!2K2Fa02E4Y5,0X0Z0#0d04.

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

.1280133dsi6/h1wajn4_lcèefO50,kmyPop[b;2:7-uSgrv]t=8)( 050c0s0R0k0e0p0d0W0q0p0k0d0d0S010R0e0D010406050d0L0z0z0k0O0A040M0C0p0L0;0C0m050g0{0}0 110_0D04051h1a1k0g1h0_0c0e0P0)0+0-0/0+0m0N0L0k0N0s0K0D0A0R0h180W0h0e0N0h0p1M0h0R0@050!0F0p0s1t0,0.011L1N1P1N0R1V1X1T0R0O1i1H0)140d0D0k0m0/0H011Z1v010t0$0s0m0k0z0s1T1^1`1 1#221X25270@0a0W0B0O0C0D0C0d0e170m0W0Y1?0O0O0s0q2s1a2a0m1i0g1H2F1/1;1:1U0c2c1w0e0m242p1T1q1s0*1!2P2R0m0C2V1T0D2y1i2D2F2,0`1_2t2X202#0O0~0p1T0k1K2y0t0/030o0o0q2$0s1P2!0C0K0i0w3a0@0i1a0k2-2:0^2/2b2=1#2@2_2{2}0s2 01313335372S3a3c1}040H3g3i1`3k2D2O013p0k2`1i2|0h2~3032340Y3z2#3B0K0b0@0b3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0K0n0@0n3)1b3+3l2;1u3o0C2^3O3r3S3t3U3x3X3{3Z3}0v0@0v422,3,2:3L3:4c3@3w3W364i393}0f0@0f4o443-473/493q3Q3s3u4w3`383!0J0@0J4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0T0@0T4W2E1l2*1a2V2I0c1;2N3.014x2U1r1i2)0s2+3j3*3I054x572b0e0c0/322D3!0i3r5f5h4g4y4-3c5l0W2g0s5o4x3Y4A5s1T0g3h453L0y0@0Y0t594?4H2Y010j0@0W5L5d465O0m0t0@1/0e0o2Q0d0s0O2B435a5N200?040V5T5F4 0m5Z0k1W0s0k0L5?5.1#5:0U0I5T0_5,5M4r5n015i2:3!3D3=0W6b4+5q3|3C1~5v5x4Q6m0K6g5D040W6x5S610/5H040t495T6z4r5^0@0e6G5@4!0C5Q042Q6M6A3M0F0@0O1`1C606I4!5:5=685U3L0z0e3e6#4Z5O5:0x6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0U64666~6i5g6c0o5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0P3O0s0L0O0o0k5$0m5(2y0O6^7H1#0C0@0S7W6 3o5`5|5~7h4 5:0E7,4!756L7a6U5:0Q7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040l7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0j1L1X8m6J8k8W6O0@020N0R0G8Z5O6-0@0w8*206P0@1`0c8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0K8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0K4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0K4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0q5l04030W0u2t5%0r2yaL4?0g5c4@564_531a0R4|bn2L2G8{bk0g4`670Y0!0$0d04.

Évaluations restantes : 5/5

.1280133dsi6/h1wajn4_lcef5,0kmyPop[b;2:7-uSgrv]t=8)( 050c0r0P0k0e0p0d0U0q0p0k0d0d0Q010P0e0B010406050d0J0x0x0k0M0y040K0A0p0J0/0A0m050g0_0{0}0 0@0B04051f181i0g1f0@0c0e0N0%0)0+0-0)0m0L0J0k0L0r0I0B0y0P0h160U0h0e0L0h0p1K0h0P0=050Y0D0p0r1r0*0,011J1L1N1L0P1T1V1R0P0M1g1F0%120d0B0k0m0-0F011X1t010s0!0r0m0k0x0r1R1?1^1}1Z201V23250=0a0U0z0M0A0B0A0d0e150m0U0W1;0M0M0r0q2q18280m1g0g1F2D1-1/1.1S0c2a1u0e0m222n1R1o1q0(1Y2N2P0m0A2T1R0B2w1g2B2D2*0^1@2r2V1~2Z0M0|0p1R0k1I2w0s0-030o0o0q2!0r1N2Y0A0I0i0i380=0i180k2+2.0?2-292:1Z2=2@2_2{0r2}012 3133352Q383a1{040F3e3g1^3i2B2M013n0k2^1g2`0h2|2~30320W3x2Z3z0I0b0=0b3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390I0n0=0n3%193)3j2/1s3m0A2?3M3p3Q3r3S3v3V3_3X3{0t0=0t402*3*2.3J3.4a3=3u3U344g373{0f0=0f4m423+453-473o3O3q3s4u3^363Y0H0=0H4D3G4o3k4G3K4I494K4b4M3@4f4P3{0R0=0R4U2C1j2(182T2G0c1/2L3,014v2S1p1g2%0r2)3h3(3G054v55290e0c0-302B3Y0i3p5d5f4e4w4+3a5j0U2e0r5m4v3W4y5q1R0g3f433J0w0=0W0s574;4F2W010j0=0U5J5b445M0m0s0=1-0e0o2O0d0r0M2z41585L1~0;040T5R5D4}0m5X0k1U0r0k0J5;5,1Z5.0S0G5R0@5*5K4p5l015g2.3Y3B3:0U694)5o3`3A1|5t5v4O6k0I6e5B040U6v5Q5 0-5F040s475R6x4p5?0=0e6E5=4Y0A5O042O6K6y3K0D0=0M1^1A5~6G4Y5.5:665S3J0x0e3c6Z4X5M5.0u6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0S62646|6g5e6a0o5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0N3M0r0J0M0o0k5!0m5$2w0M6?7F1Z0A0=0Q7U6}3m5^5`5|7f4}5.0C7*4Y736J786S5.0O7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040l7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0j1J1V8k6H8i8U6M0=020L0P0E8X5M6+0=0v8(1~6N0=1^0c8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0I8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0I4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0I4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0g5a4=544@51180P4`b92J2E8_b60g4^650W0Y0!0d04.

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