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
vest égal à l'élément se trouvant au milieu de la liste liste[milieu] , l'entiervest 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.
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 ]ik[vN8o-)yqxb.I+g=Dmz}TÀ4rsù97f,{d :F5hwtcOl0p_PL3(a;R/àeèS612éênu^A 050J0*0Q0#0c0T0C0K0R0T0#0C0C0t010Q0c0V010406050C0?0v0v0#0B0l040,0i0T0?190i0=0K020#0v0V0$0K0%0*1j0B0m0?0*0C050(1g1i1k1m1e0V04051R1K1U0(1R1e0J0c0f11131517130=0s0?0#0s0*0j0V0l0Q0O1t0K0O0c0s0O0T1}0O0Q1c050|0o0T0*1%1416011|1~201~0Q2628240Q0B1S1^111p0C0V0#0=170/012a1)010G0~0*0=1x0*242s2u2z2c2C282F0v2H040a0K0X0B0i0V0i0C0c1s1u0`2q0B0B0*0R2$1K2J0=1S0(1^2=2m2o2n250J2L1*0c0=2E2Z241!1$122b2 310=0i35240V2+1S2:2=3i1f2t1u372A3b0B1j0T240#1{2+0G17030W0W0R3c0*203a0i0j0U0j0.1c0K0.1K0#3j3m1d3l2K3o2c3q3s3u3w0*3y013A3C3E3G323J0j2x040K0/3Q3S2u3U2:2~013Z0#3t1S3v0O3x3z3B3D0`3-3b3/0Z3N0Z3^2/3T1e3|3X173 410543453)473,303.3K0A3N0A4g1L4i3V3n1(3Y0i3r403#443%463+494v4b3K0N3N0N4B3i4j3m3}4n4L4r3*483F4R3I3K0-3N0-4X4D4k4G4m4I3!423$3(4)4u3H3/0F3N0F4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0h3N0h562;584F385b4J4o4q4N4s4P4+5j0j0E3N0E5o3{4!4l5t4{4p4}4O4*4a4-3L0U1c0.0U5G5q4#5c5v5N5y5P4,3/0.3M045+5X4E5Z5u4%5x4 5i4w3L3;0.3@0(3R4h3`1V3g1K352^0J2o2}5J4*341#1S3f0*3h3T612;054*6i2K0c0J173B2:5*3#6q6s5z5Q6v0K2P0*6y5(5B5,4g4@5s0d1c0`0G6k6o5r2A0P3N6Q5:5J0=0G6N0c0R1_0Q0i0v0c0*6W6K2A1b040!6.5I5a0=1c3b0v0o2+1J4C626/2c6;0H6Q0K6X6_1c0R0c276-716l73176;0k0L6Q1e7g6R0K6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0K7M795s6`040`0o1r777O2A0i1c0t7V7i016+1c5W7p7o3k3|7z0W6u3K4d4|7/6G5`4d7E2Q7G5_4S0j7?3^7M7N7$7Q2C0=7#6^5s7Y047!7p78860o1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0k8a8n7X1c0j8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040P1|288I4#6N0*7T0Q8^5J8d020T0Q0$8f3i8-8E8t04888O5J6;7m7+8O7/7;0j4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200*0?8~5a8d953T978J018p9c7a9a309H8c1c0r9U3p8`8|9Q8o8B9$8F040(0(9)2c8L5~4Y9h9n9j4/9m9t8Y0j4/8!9{9p9}7J8+9y858.2c8:0c6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0e9.9B049D6,9G8r7$6;0b9f9=aE4!9i8T0j539`8$7H80539 aR7 5RaP9xa58,ad8:2+0Q0?0B89aiau010d0R1c0y0B1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900s93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0C7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0M40c8b#0R5,030K2!0K1`0=02030Z0E0$3v2t102m0i0?0f0:cL6j0(6n636h656e1K0Q68dj2{2?0#7e2=661Q7q5J2+0v0W0G0#0d0*0W0O7?1C1E1G1I0Kce6l1X3U353}0#0J0v1t2#0c1`300G8d1QdQdSdU2$0j190Q2k041C6%0*0Bd:0K2t0B0K1!6%0i6)6+7f1Y1T040q0Tc_001/2#d`000?1u400s4I2#0O2Q2L0cdI0p0K0Y292j0*0#0?d@0B0c102Ed@1k1x0+2m290J0ie91fd61,040i271}0#6)0cdw2E0Q0K0;eE0K2m0cda1LeK0s040p1V3U1R0z110O0#dI7r0Q0:0BeQdW0=0Hc{1uc8d`1D2u2(c`130K0f409Fd_0ReUe`280K1IeV0:0sfa0K0)0Kf76m3E04bhah6ndKe,1e0?0T3U2004c`d70ce~1`2+0=0feH290c1i0:1!eQ1DeU786na@a_ddfs1KfD1efDc`3be}110{0Q29fu29fic_eHeV7mfAfC0cfE0?0Ve_aC2+fnfp3vf928a+f-0=2mfm0L7re5dz1re:d;d:d_0J2u10f7d^19eF2W2#eFeueret0K6?6n7Sgi0t0Kbxeu0r3O1K6n8C0(f%05fDdYg1fb29fof7g7fbgagcfgge0~0KgheVglgld`gog5eA0Bgs0Kfl0?d?0Jgxdp28gzgBfs880KgFgH0K0jgKf!0`04gNgP0(f{7ohdhfe20Y3v0w1teF292+g,0O290!0T000:0R1keVfe29frhacxfw0{fWfsgD8}h96h0kc_hpfR0?e9fo6%e=1He@e_e{1`gefF1u88e9d^0K0#fMeShIhE301v921AhKgLfse~0R00f?e?fq6nf;h`ha6Ch~0CeVd4g.0=gpeqg}es0?en0Sf04IeV2(f70od712f=eVfKh.hC6nc/0 7f6ne+dN7ods0_1#d$dT0=dVdX6Zd!1TiId(e|d*2#d-0g8vg31j0nfP40f2eZd70B102(ipg_2870e11R2V32ic0Kec0Khxhzea30d{fOiK19i$hD6hh2h7h_hM3=fki$foad1keh1jf/0n1c090!5V0@0E09gN3ie~0!fd0K1G0cfhi8jx1.0=2}0v0;ej2m0+100se`jE0kiCi;040ug/fg0VeSho10hy0CfI0Dg:f;i6f?ia3f0:c8gb0*fI1u0B0:40exeqd7idd5i)i+29i-ir102Y15ag1IjQ3UhifD0^eu6gd d_6)a+j=h,i_1ui|g=fhfLeS1`2(jfew1^ji0*jk04jm090Ge`0R0Ijo0E0x0I0/0xjr6Qh|i7eVfo1!g3ku7$jgkxfTkAjm0N0K09192Q10jo0hkO8rgOf}f(f}kdf20?i!0+jIi)kk3vi`kohAkr2W2%hCkXkweik!jl0!kDkF0Ik%k)fPdJk-kKkMk/96h}f?kTjXcv5skYlajjlc0/lhk*lk0U0@0FlodcgPkc30c`f5hSf/0K0plRf$k=gQk@gxfK19k|j{kje kll1hykp0Jh~l41`kvjhlbkBldkE0#kGkIlm0@0I0Z0U0xkNjs9LlqjBlskVl-0fks1u0.iChhfBdt0^lLfHib10ec2920i8hoeZ0}0Tfgl:kZlyl?kIlH3`e~ezgz0V1qeyl.1ul i(a+101`0C0}eVf6hw0T0:2Qgbh:6hi3jajAi9j@j/0Qk9iE6eiE0{mt0C04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 ]ik[vN8o-)yqxb.I+g=Dmz}TÀ4rsù97f,{d :F5hwtcOl0p_PL3(a;R/àeèS612éênu^A 050J0*0Q0#0c0T0C0K0R0T0#0C0C0t010Q0c0V010406050C0?0v0v0#0B0l040,0i0T0?190i0=0K020#0v0V0$0K0%0*1j0B0m0?0*0C050(1g1i1k1m1e0V04051R1K1U0(1R1e0J0c0f11131517130=0s0?0#0s0*0j0V0l0Q0O1t0K0O0c0s0O0T1}0O0Q1c050|0o0T0*1%1416011|1~201~0Q2628240Q0B1S1^111p0C0V0#0=170/012a1)010G0~0*0=1x0*242s2u2z2c2C282F0v2H040a0K0X0B0i0V0i0C0c1s1u0`2q0B0B0*0R2$1K2J0=1S0(1^2=2m2o2n250J2L1*0c0=2E2Z241!1$122b2 310=0i35240V2+1S2:2=3i1f2t1u372A3b0B1j0T240#1{2+0G17030W0W0R3c0*203a0i0j0.3J1c0K0.1K0#3j3m1d3l2K3o2c3q3s3u3w0*3y013A3C3E3G323J0j2x040K0/3P3R2u3T2:2~013Y0#3t1S3v0O3x3z3B3D0`3,3b3.0Z3M0Z3@2/3S1e3{3W173~400542443(463+303-3K0A3M0A4f1L4h3U3n1(3X0i3r3 3!433$453*484u4a3K0N3M0N4A3i4i3m3|4m4K4q3)473F4Q3I3K0-3M0-4W4C4j4F4l4H3Z413#3%4(4t3H3.0F3M0F4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0h3M0h552;574E385a4I4n4p4M4r4O4*5i0j0E3M0E5n3`4Z4k5s4`4o4|4N4)494,3J0U1c0.0U5F5p4!5b5u5M5x5O4+3.0.0.5T3O0(3Q4g564D5Y5t4$5w4~5h4v3J3:0.3?5.3^2;1V3g1K352^0J2o2}5I4)341#1S3f0*3h3S5:634)6j2K0c0J173B2:5)3!6q6s5y5P6v0K2P0*6y5%5A5+2=5/4?5r0d1c0`0G6l6o5q2A0P3M6R5=5I0=0G6O0c0R1_0Q0i0v0c0*6X6L2A1b040!6/5H590=1c3b0v0o2+1J4B3_6Y596=0H6R0K745r6{040R0c276.72636:2c6=0k0L6R1e7i6S0K6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610K7N797k4l6O0*0o1r787a2A0i1c0t7W7Q016,1c5V7r7q3k3{7B0W6u3K4c4{7:6G5|4c7G2Q7I5{4R0j7@3@7O7P6_7b1c2C0=7$877Y7!8c587b0o1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0k8g8z177Z040j8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040P1|288J6Z7S7U0Q8^598G020T0Q0$7#7r868n8t048a8P5I6=7o7,8P7:7=0j4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200*0?8}5r8G943i968E016=8q7.8d989a958.018G0r9F3p8`7V8r7%7m9b8~1c0(0(9)5r8L608O9$4Z9h8U0j4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0c6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0e9.9Z049B6-9E9?au9M1c0b9e9=at1u9^2u518W9}9o0j528#aR5A528+a7a79U8:2+0Q0?0B8bad9Q8/0R1c0y0B1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0s92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0C7hb?9c1cbF5;bHaN0=5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0c5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0da:040M3 c8cN3k0(6n646i666f1K0Q69c~2{2?0#7g2=671Q7s5I2+0v0W0G0#0d0*0W0O7@1C1E1G1I0Kcd631X3T353|0#0J0v1t2#0c1`300G8G1Qdvdxdz2$0j190Q2k041C6(0*0BdR0K2t0B0K1!6(0i6*6,7h1Y1T040q0T0K0C001/2#dY000?1u3 0s4H2#0O2Q2L0cdn0p0K0Y292j0*0#0?dV0B0c102EdV1k1x0+2m290J0id=1f2m1t0s040i271}0#6*0cdb2E0Q0K0;ek0K2m0c0:2/eq1,040p1V3T1R0z110O0#dn7t0Q0:0BexdB0=0H0K1`c8dY1D2u2(2!0K130K0f3 9DdX0ReBe!280K1IeC0:0se^0K0)e;3v056nbh7h6ndpeP1e0?0T3T2004e:0i0?0ce(1`2+0=0fen290c1i0:1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0Q29fbe 0CeC0CeneC7ofhfj0cfl0?0VeZaC2+f5f7e?e^a*fR0=2mf40L7td-de1reTdSdRdX0J2u10e=dW19el2W2#eleae7e90K6@6nbZg00t0Kb+ea0r3N1K6n8C0(fL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0Kf eCg3g3dYg6f;g96-0Kf30?dU0Jgfd428ghgjfJ8a0Kgngp0K0jgsfI0`04gvgx0(f%7qg|g~d*0Y3v0w1tel292+gS0O290!0T000:0R1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0kd.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0K0#fuezfEhn1u9092e,b!hx04e(0R00f00KeWe=ht6ifbhpg_6Ch,fXeg10g50=g7e6g)e80?e30S1ufZ0BeC2(e=0ofn12290{0KfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0=dAdC6!dF1TixdJe$dL2#dO0gbr291j0nfx3 e,eGfn0Bh}29idg#2871d)1R2V32h 0Kd^0Khghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0n1c090!5U0@0E09gv3ie(0!e{h.fofWeC2m0+100se!0=0J0kiri$040ugVe~0Vezh710hh0Cfq0Df;fV0=h`eC2t103f0:c8f_0*fq1u0B0:3 ede6fni0106*a*iW0KiYifjS2Z2!7g0Cjy3Th1fk0^ea6hd%dXj,0BjYhTi+1ui.i9e ftez1`2(j4ec1^j70*j904jb090Ge!0R0Ijd0E0x0I0/0xjg6Rh*jPf:1!f/kf7%j5kifBkljb0N0K09192Q10jd0hkz8rgwf)fMf)j~e,0?iP0+d k3k53vi,k9hjkc2W2%hlkHkhd~kKja0!kokq0IkNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0/l1kQl40U0@0Fl86kkXf(040^30e:e/hD290plC1Kgxj}gffs19k)j(a*k,k7i-hhka0Jh,k;1`kgj6k{kmk}kp0#krktl60@0I0Z0U0xkyjhamlah{lcjFd?2E0fkd1u0.irh0fid8lwh fpgUi*d^2920fXh7eG0}0Te~lWkJlilZktlr3_e(efgh0V1qeelU1ul,iTj-e)i70}fY0ce;hf0T0:2Qf_hXg_h?h(joebjUeBj`it6fit0{me0C04.
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.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 ]ik[vN8o-)yqxb.I+g=DmT4r*s97f,d :C5hwtcOl0p_PL3(a;ER/àeîèS612énu 050F0%0M0X0c0P0A0G0N0P0X0A0A0t010M0c0R010406050A0:0v0v0X0y0l040*0i0P0:140i0/0G020X0v0R0Y0G0!0%1e0y0m0:0%0A050#1b1d1f1h190R04051M1F1P0#1M190F0c0f0|0~10120~0/0s0:0X0s0%0j0R0l0M0K1o0G0K0c0s0K0P1^0K0M17050@0o0P0%1Y0 11011@1_1{1_0M21231 0M0y1N1:0|1k0A0R0X0/120-01251!010D0_0%0/1s0%1 2n2p2u272x232A0v2C040a0G0T0y0i0R0i0A0c1n1p0=2l0y0y0%0N2X1F2E0/1N0#1:2-2h2j2i200F2G1#0c0/2z2U1 1V1X0}262`2|0/0i301 0R2$1N2+2-3d1a2o1p322v360y1e0P1 0X1?2$0D12030S0S0N370%1{350i0j0-0j0,170G0,1F0X3e3h183g2F3j273l3n3p3r0%3t013v3x3z3B2}3E3E3I0-3L3N2p3P2+2_013U0X3o1N3q0K3s3u3w3y0=3(363*0V3I0V3.2*3O193=3S123^3`053|3~3!403%2{3)3F0x3I0x491G4b3Q3i1Z3T0i3m3_3W3}3Y3 3$424o443F0J3I0J4u3d4c3h3?4g4E4k3#413A4K3D3F0+3I0+4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0C3I0C4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0h3I0h4 2,514y33544C4h4j4G4l4I4!5c0j0B3I0B5h3;4T4e5m4;4i4?4H4Z434$3G0Q170,0Q5z5j4U555o5G5r5I4#3*0,3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0#3M4a3:1Q3b1F302:0F2j2^5C4Z2 1W1N3a0%3c3O5`2,054Z6b2F0c0F123w2+5Z3W6j6l5s5J6o0G2K0%6r5X5u5#494-5l0d170=0D6d6h5k2v0L3I6J5)5C0/0D172{1V0N0%6P6D2v16040W6Z5B530/172e0%0X0:6)525l6$0E6J0G6Q6+170N0c226Y4v5{6!276$0k0H6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040G7z6{754f6G0%0o1m6`6|5l0i170t7I7C010v0c175P7c3P7V5)7m0S6n3F464=7Z6z5:467r2L7t5/4L0j7%3.7A7B6*5l6,042x0/7O7`2v7L047N7V7_6?3k0o172J6=6L76176(7X7P7|6.6:8d3?77808827830j8q8e127R5N7a8n7Z7#0j4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040L1@238v4U7E7G0M8#5C83020P0M0Y853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0%6;869l12838;3O8?8o8g8{6}040=8(8*53830r9G7{8_2{9B6@170k9K82170#0#9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0c6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0e9O3k9n0_0c9qan8f040b8~9$8i4T8C9*0j4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0j5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0X718mazaX01alataea$asbm8@6$aw8Abu0GaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0M0:0y7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0A72aibn8}byb~1pbB0/5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0,7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010d0N170g1ob}4w7X0#6g5|6a5~671F0M61c@2?2.bj232-5 1L6K3?2$0v0S0D0X0d0%0S0K7%1x1z1B1D0Gax6c1S3P303?0X0F0v1o2W0c1=2{0D831Ldodqds2X0j140M2f041x0N0K0%0ydK246W1;0M0i7RdgbA0M0.0y0X140f240H0G0$2l0/2A0(2h721T1O040q0P0G0A001*2W0G2Z0Pd{0P0s4B2W0K2Ld~242$dOdNdLd~0cdK0idSdU1C2G0cdg0p1Q7Wd00;1WdAdr0/dtdv6Sdy1OeudCduc5dFdH0U3qeadLecdP24e06VefdP0:0Gb!epd10U240N3_0N0:d^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0i0c0{dg0Pdg0{3y1d2z0@0c2$0A0p0G0q6 0G1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10O0y0Ed~2pf0dMf40/0{flfn0{2Zfe0sdZ1I2X2lf20G230G0If,0~0Gf40Pg30=0{f3ar0ygd0A0Mg20c7RdX0%f80IeZe#e%6{4Zfk2pfm1+1-0lfq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0R9qgj2o0ydxe{0G0%0n0N0.0=0y0|0?0Me?0^gaeOgle=f80Z1p3Y0D0?f,2Vg2dh0=0:0nbA0/6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0A1ogjf|2p0F0Ag69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0Gg?1md~0.2o10dMg23q0f3_h/gkgmgoeWd=0uf.h40|0 fc3igsg3ePhreRe-eUcteT2z0G1maq0A2pgjg70~0y1+bUe8g2e*0/h60yimh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0.b|iZh.ic2R220)e72|d_242Tb|iciye!f+g}1p0T1/1;0/h.gdiZgf0{0/00h(jMf_h70_iChbh6f80w0ie^g{h-0G0*0ciX1=0Ximd}1eew0Re%0.e8j!dT0of60G0D0Peh0@iZf?jJjD0PjF24b|dZd}0X0Rg_eTf1e7g_g}0n1y0Rg38~d;dn5Cdpevexhf0n1skz2MdzkEdBewdDeG2M0Zkx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0I1oh%g30*1D2V1o6P696K3/6ec/cDb(7i0V3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0s6$020s8/ltlvlu1vbqaTi|jggLg,6T9!0p7Uj6gK0z0zfY5$0Q0-48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0Yl^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0N5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0Fig261yf3m!kp0Xm%k4kcggiWg7h;2Ln37Ymjl80j9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040h0p0B0h0h0x0+0J0+0C0x0V5!0J0h0%0r0V0Q4~lT3fjnc;1S5}0#erp4677bp50=g90A04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 ]ik[vN8o-)yqxb.I+g=DmT4r*s97f,d :C5hwtcOl0p_PL3(a;ER/àeîèS612énu 050F0%0M0X0c0P0A0G0N0P0X0A0A0t010M0c0R010406050A0:0v0v0X0y0l040*0i0P0:140i0/0G020X0v0R0Y0G0!0%1e0y0m0:0%0A050#1b1d1f1h190R04051M1F1P0#1M190F0c0f0|0~10120~0/0s0:0X0s0%0j0R0l0M0K1o0G0K0c0s0K0P1^0K0M17050@0o0P0%1Y0 11011@1_1{1_0M21231 0M0y1N1:0|1k0A0R0X0/120-01251!010D0_0%0/1s0%1 2n2p2u272x232A0v2C040a0G0T0y0i0R0i0A0c1n1p0=2l0y0y0%0N2X1F2E0/1N0#1:2-2h2j2i200F2G1#0c0/2z2U1 1V1X0}262`2|0/0i301 0R2$1N2+2-3d1a2o1p322v360y1e0P1 0X1?2$0D12030S0S0N370%1{350i0j0x0j0,170G0,1F0X3e3h183g2F3j273l3n3p3r0%3t013v3x3z3B2}3E0j2s040G0-3L3N2p3P2+2_013U0X3o1N3q0K3s3u3w3y0=3(363*0V3I0V3:2*3O193@3S123`3|053~403!423%2{3)3F0x3I0x4b1G4d3Q3i1Z3T0i3m3{3W3 3Y413$444q463F0J3I0J4w3d4e3h3^4i4G4m3#433A4M3D3F0+3I0+4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0C3I0C4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0h3I0h512,534A33564E4j4l4I4n4K4$5e0j0B3I0B5j3?4V4g5o4?4k4^4J4#454(3G0Q170,0Q5B5l4W575q5I5t5K4%3*0,3H045$5S4z5U5p4Y5s4`5d4r3G3,0,3/0#3M4c3=1Q3b1F302:0F2j2^5E4#2 1W1N3a0%3c3O5|2,054#6d2F0c0F123w2+5#3W6l6n5u5L6q0G2K0%6t5Z5w5%4b4/5n0d170=0D6f6j5m2v0L3I6L5+5E0/0D172{1V0N0%6R6F2v16040W6#5D550/172e0%0X0:6+545n6(0E6L0G6S6-170N0c226!4x5}6$276(0k0H6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0G7B6~5n6.040=0o1m6|7D2v0i170t7K77120v0c175R7e3P7X5+7o0S6p3F484@7#6B5=487t2L7v5;4N0j7)3:7B7C7R3_172x0/7Q6,5n7N047P7X6}7|0/0o172J6@6N78176*7Z896/0X736=8e3^79816^7M170j8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040L1@238x4W6I0%7I0M8(5E84020P0M0Y863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0%6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840r8.6 047 8 558r9N9J9z170#0#9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0c6K9Y8{4h70728%a69E8:8=0Y9(3k8l8n9w9Ia79F170e9V7E179t0c9var6%170b929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0jaI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0j5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0M0:0y80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0A74bF8q17aB4ybubH0/5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0d0N170g1oc19Cb60N5%030G0*0c0G1=0/02030V0B0Y3q0yav1p2h0i0:0f0.bE6e0#6i5~6c60691F0M63di2?2.8m232-611L6M3^2$0v0S0D0X0d0%0S0K7)1x1z1B1D0Gc55}1S3P303^0X0F0v1o2W0c1=2{0D841LdPdRdT2X0j140M2f041x0N0K0%0yd/246Y1;0M0i7TdH0G2W0.0y0X140f240H0G0$2l0/2A0(2h741T1O040q0P0G0A001*2W0G2Z0Pem0P0s4D2W0K2Lep242$d?d=d:ep0cd/0id`d|1C2G0cdH0p1Q7Ydr0;1Wd#dS0/dUdW6UdZ1OeVd%dVc9d*d,0Ud12%d:eDd@24er6XeGd@0:0Gb(eQds0U240N3{0N0:ejeq00e^6Zepe{b(e|e02W24d`1m3Y0i0c0{dH0PdH0{3y1d2z0@0c2$0A0p0G0q71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe}cu8u85bg9Gax9K8+9Mc$cWcCfZ9r9Ubu90170kcs9#9%f/a.049,db6iePdMds0O0y0Eep2pfrd;fv0/0{fMfO0{2ZfF0se11I2X2lft0G230G0Ig70~0Gfv0Pgr0=0{fuav0ygB0A0Mgq0c7T0M0.0%fz0If1f3f56}4#fL2pfN1+1-0lfR2a1|1~dtbmcwbyf_f#f|ao6)f(a87Gf*8-g/f.f,an7Ff;c2f?04f^g`f`cD8Af dL6i0G0R9vgH2o0ydYfm0G0%0n0N0.0=0y0|0?0Mfh0^gye?gJfgfz0Z1p3Y0D0?g72VgqdI0=0:0nd~0/6YdIfJ2Z5EfM1)gYfQ291`g%fVg}cqf+g03z3-0?gTfKhSgWhUfPg!hXfTg(cpaXc#h(0=3-0A1ogHgk2p0F0Agu9vhph gphQf155hTfOgZg#hY2ch!9E7F9Lg_g|ad179Qg/g~aY3fdch)hbhdep0.2o10d;gq3q0f3{i7gIgKgNe~eg0ug9hq0|0 fDiT0Pf4gre@hNe_fbe|bx9vhj1p1mbx0A2pgHgv0~0y1+bZezgqf80/hs0yiIhvdJh,hRidh/ifhWfShZg)b%i)cy3-b6ctipbving-isjih19HbAfW8}h{bkjga,ith$iojqan9XjncBh5g/cEh86gixh}g2ef1MiQgdhHiT0{3a0.c0i}i6hb2R220)ey2|ek242Tc0hbiUf2g6i+2P1/1;0/i6gBi}gD0{0/00i0j-ghht0_iZhxhsfz0wd6hshhi5c?c^er1=0XiIeo1eeX0Rf50.ezj}d{0ofx0G0D0PeI0@i}gej*j!0Pj$24c0e1eo0X0Rhfe{92efdO5EdQeWeYhB0n1s0Rd,d!kRd$eXd(e+2M0Z0n1ykYeedNeUh.1%h:gZ3y1ph?jab62I2z2B170Tj?1=0I1oh gr0*1D2V1o6R6b6M3;6gdd96b,7k0J3Gb/cR4|lm3Hb?bM46lr2t5a5Jce0jlwb`b60s6(020s8?lHlJlI1vg=7}g@crh4g.jD9)6Vf~0p7WlUf!0z0zh65P0Q0-4acGc7a?99lmcKd~cMlAl;chb:3)l_5X5:b1lB3+7y5{7|lF17lK0Ym8m86}f=9Sg 9C7{f-7OcDlW0-lYg-l$l(5(l*l,l!27g{c.7|cE3Kl-c2c8m17^cLl{lv7@l`lpl|mJl~cjmM7^7zlElGlMmalMmch09SjklSjmmxjrh`6|cA5nc:17c=0FiC261yfui`f22o71gLda76aEl/c9lm8S7nl@aLm14tltcNn8lx4ZmPmIn4mSm584dXm~7fn0lkl:lBlonf3Dlm9gcQntm19gly5Yl^nrlDm5mUlLnIlNmd6_8hlOimg^jlbgiujtnnjBf@g-f{muf}jI7Ac/c;iBiDc02Li}m_kK0Xm|kpkxgEi`gvi92LnmdtmDlm9~mGmLmI4*nanDo5nBl 6vo0m3jb5neu6W6Un}7!n1m1aSo2nylmaNnxlunuaRnd5/opovnFcWm604mWnJmYjAiljynRg/f%nLaim*lS8wjxlQh%m nWh2nYmqn$94oHl?npn2a}bLnblm5go6n7o-ow5botm1b3nioB840h0p0B0h0h0x0+0J0+0C0x0V5$0J0h0%0r0V0Q50mBh|df1S5 0#eSpm697dpn0=gx0A04.
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
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.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 w]itkc[vo-)ylbp_P3(a;j+g=/m4rse7Sf,d 612:5nuh 050K0F0e0u0d0n0E0L0g0n0u0E0E0z010e0d0p010406050E0S0B0B0u0D0m040H0j0n0S0.0j0R050A0^0`0|0~0?0p04051e171h0A1e0?0K0d0i0$0(0*0,0(0R0y0S0u0y0F0k0p0m0e0T150L0T0d0y0T0n1J0T0e0;050X0o0n0F1q0)0+011I1K1M1K0e1S1U1Q0e0D1f1E0$110E0p0u0R0,0O011W1s010I0Z0F0R0u0B0F1Q1=1@1|1Y1 1U22240;0a0L0r0D0j0p0j0E0d140R0L0V1:0D0D0F0g2p17270R1f0A1E2C1,1.1-1R0K291t0d0R212m1Q1n1p0%1X2M2O0R0j2S1Q0p2v1f2A2C2)0@1?2q2U1}2Y0D0{0n1Q0u1H2v0I0,030q0q0g2Z0F1M2X0j0k0G0k0N0;0N170u2*2-0=2,282/1Y2;2?2^2`0F2|012~3032342P370k1`040O3d3f1@3h2A2L013m0u2@1f2_0T2{2}2 310V3w2Y3y0s0;0s3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380C0;0C3#183%3i2.1r3l0j2=3L3o3P3q3R3u3U3@3W380Q0;0Q3}2)3(2-3I3,473:3t3T334d36380M0;0M4j3 3)423+443n3N3p3r4r3?353y0G0;0G4A3F1i2%172S2F0K1.2K3*014s2R1o1f2$0F2(3g3$4S4s4-280d0K0,2 2A3y3a4H4@4_4b4t4M383a0L2d0F504s3V4v391Q0A3e403I0f0;0V0I4/2B5h4#0b0;0L5n4=412V3J0I0;1,0d0q0E332w2y3~4S4C5x0:040t5u5p4D3J5A0u1T0F0u0S5P5K1}5M0l0P5u0?5I5o3H4 014`2-3y3A3.0L5.3=4c533z1{57594L3^5}2C3e0L665t5!1Y5j040I445u684m4#0R0;0d6f5Q5x0j5r042N6m693+0o0;0D1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0l6t6C6o0;0k6%6N5x0B0d3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0q6/0R6l6G6g6-1}0j0;0z6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0k7J3D7i7j6S6b6d0D7y4n0;0w7%4#6p6k167r7k6v6x6z0F6{4#6E7_5R6j7B7:6S7v040x7+5R6/6;7D6(6@0J855x0R6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0R3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0d5m808a7A6V8r8m3I5M0h8s2:7)8,8k0;0c8d7u0;020n0e0v8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0c5(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;98a4a18t040c9_2)9Fahacak6@af4.9(9=at8:am7C2+0A4;4T4,4V4)170e4YaK2I2D9}2C4W5*0V0X0Z0E04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 w]itkc[v8o-)ylbp_P3(a;j+g=/m4rse7Sf,d 612:é5nuh 050L0G0e0v0d0o0F0M0g0o0v0F0F0A010e0d0q010406050F0U0C0C0v0E0n040I0k0o0U0:0k0T050B0`0|0~100^0q04051g191j0B1g0^0L0d0i0(0*0,0.0*0T0z0U0v0z0G0l0q0n0e0V170M0V0d0z0V0o1L0V0e0?050Z0p0o0G1s0+0-011K1M1O1M0e1U1W1S0e0E1h1G0(130F0q0v0T0.0P011Y1u010J0#0G0T0v0C0G1S1@1_1~1!211W24260?0a0M0s0E0k0q0k0F0d160T0M0X1=0E0E0G0g2r19290T1h0B1G2E1.1:1/1T0L2b1v0d0T232o1S1p1r0)1Z2O2Q0T0k2U1S0q2x1h2C2E2+0_1^2s2W1 2!0E0}0o1S0v1J2x0J0.030r0r0g2#0G1O2Z0k0l0j0l0O0?0O190v2,2/0@2.2a2;1!2?2^2`2|0G2~01303234362R390l1|040P3f3h1_3j2C2N013o0v2_1h2{0V2}2 31330X3y2!3A0t0?0t3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0D0?0D3%1a3)3k2:1t3n0k2@3N3q3R3s3T3w3W3_3Y3a0S0?0S3 2+3*2/3K3.493=3v3V354f383a0N0?0N4l413+443-463p3P3r3t4t3^373A0H0?0H4C3H1k2)192U2H0L1:2M3,014u2T1q1h2(0G2*3i3(4U4u4/2a0d0L0.312C3A3c4J4_4{4d4v4O3a3c0M2f0G524u3X4x3b1S0B3g423K0f0?0X0J4;2D5j4%0b0?0M5p4@432X3L0J0?1.0d0r0F352y2A404U4E5z0=040u5w5r4F3L5C0v1V0G0v0U5R5M1 5O0m0Q5w0^5K5q3J51014|2/3A3C3:0M5:3@4e553B1}595b4N3`5 2E3g0M685v5$1!5l040J465w6a4o4%0T0?0d6h5S5z0k5t042P6o6b3-0p0?0E1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0m6v6E6q0?0l6)6P5z0C0d3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0r6;0T6n6I6i6/1 0k0?0A6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0l7L3F7k7l6U6d6f0E7A4p0?0x7)4%6r6m187t7m6x6z6B0G6}4%6G7{5T6l7D7=6U7x040y7-5T6;6?7F6*6_0K875z0T6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0T3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0d5o828c7C6X8t8o3K5O0h8u2=7+8.8m0?0c8f7w0?020o0e0w8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0c5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720l4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040c9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0g4 030M0R0g0V7_7E2-0B4?4V4.4X4+190e4!a!2K2Fa02E4Y5,0X0Z0#0F04.
Utiliser La fonction tri_selection
Exécuter le script suivant :
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
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
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.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 w]itkc[v8o-)Oyl0bp_P3(a;jg=/m4rseè7Sf,d 612:5nuh 050N0H0e0x0d0p0G0O0g0p0x0G0G0B010e0d0s010406050G0V0D0D0x0F0o040K0k0p0V0;0k0U050C0{0}0 110_0s04051h1a1k0C1h0_0N0d0i0)0+0-0/0+0U0A0V0x0A0H0l0s0o0e0W180O0W0d0A0W0p1M0W0e0@050!0r0p0H1t0,0.011L1N1P1N0e1V1X1T0e0F1i1H0)140G0s0x0U0/0R011Z1v010L0$0H0U0x0D0H1T1^1`1 1#221X25270@0a0O0u0F0k0s0k0G0d170U0O0Y1?0F0F0H0g2s1a2a0U1i0C1H2F1/1;1:1U0N2c1w0d0U242p1T1q1s0*1!2P2R0U0k2V1T0s2y1i2D2F2,0`1_2t2X202#0F0~0p1T0x1K2y0L0/030t0t0g2$0H1P2!0k0l0Q0q3a0@0Q1a0x2-2:0^2/2b2=1#2@2_2{2}0H2 01313335372S3a3c1}040R3g3i1`3k2D2O013p0x2`1i2|0W2~3032340Y3z2#3B0l0v0@0v3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0l0E0@0E3)1b3+3l2;1u3o0k2^3O3r3S3t3U3x3X3{3Z3}0T0@0T422,3,2:3L3:4c3@3w3W364i393}0P0@0P4o443-473/493q3Q3s3u4w3`383!0J0@0J4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0j0@0j4W2E1l2*1a2V2I0N1;2N3.014x2U1r1i2)0H2+3j3*3I054x572b0d0N0/322D3!0Q3r5f5h4g4y4-3c5l0O2g0H5o4x3Y4A5s1T0C3h453L0f0@0Y0L594?4H2Y010b0@0O5L5d465O0U0L0@1/0d0t2Q0G0H0F2B435a5N200?040w5T5F4 0U5Z0x1W0H0x0V5?5.1#5:0m0S5T0_5,5M4r5n015i2:3!3D3=0O6b4+5q3|3C1~5v5x4Q6m0l6g5D040O6x5S610/5H040L495T6z4r5^0@0d6G5@4!0k5Q042Q6M6A3M0r0@0F1`1C606I4!5:5=685U3L0D0d3e6#4Z5O5:0M6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0m64666~6i5g6c0t5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0i3O0H0V0F0t0x5$0U5(2y0F6^7H1#0k0@0B7W6 3o5`5|5~7h4 5:0h7,4!756L7a6U5:0c7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040z7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0b1L1X8m6J8k8W6O0@020A0e0y8Z5O6-0@0q8*206P0@1`0N8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0l8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0l4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0l4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0g5l04030O0n2t5%0I2yaL4?0C5c4@564_531a0e4|bn2L2G8{bk0C4`670Y0!0$0G04.
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
.128013 w]itkc[v8o-)yl0bp_P3(a;jg=/m4rse7Sf,d 612:5nuh 050L0G0e0w0d0o0F0M0g0o0w0F0F0A010e0d0r010406050F0T0C0C0w0E0n040I0k0o0T0/0k0S050B0_0{0}0 0@0r04051f181i0B1f0@0L0d0i0%0)0+0-0)0S0z0T0w0z0G0l0r0n0e0U160M0U0d0z0U0o1K0U0e0=050Y0q0o0G1r0*0,011J1L1N1L0e1T1V1R0e0E1g1F0%120F0r0w0S0-0P011X1t010J0!0G0S0w0C0G1R1?1^1}1Z201V23250=0a0M0t0E0k0r0k0F0d150S0M0W1;0E0E0G0g2q18280S1g0B1F2D1-1/1.1S0L2a1u0d0S222n1R1o1q0(1Y2N2P0S0k2T1R0r2w1g2B2D2*0^1@2r2V1~2Z0E0|0o1R0w1I2w0J0-030s0s0g2!0G1N2Y0k0l0O0O380=0O180w2+2.0?2-292:1Z2=2@2_2{0G2}012 3133352Q383a1{040P3e3g1^3i2B2M013n0w2^1g2`0U2|2~30320W3x2Z3z0l0u0=0u3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390l0D0=0D3%193)3j2/1s3m0k2?3M3p3Q3r3S3v3V3_3X3{0R0=0R402*3*2.3J3.4a3=3u3U344g373{0N0=0N4m423+453-473o3O3q3s4u3^363Y0H0=0H4D3G4o3k4G3K4I494K4b4M3@4f4P3{0j0=0j4U2C1j2(182T2G0L1/2L3,014v2S1p1g2%0G2)3h3(3G054v55290d0L0-302B3Y0O3p5d5f4e4w4+3a5j0M2e0G5m4v3W4y5q1R0B3f433J0f0=0W0J574;4F2W010b0=0M5J5b445M0S0J0=1-0d0s2O0F0G0E2z41585L1~0;040v5R5D4}0S5X0w1U0G0w0T5;5,1Z5.0m0Q5R0@5*5K4p5l015g2.3Y3B3:0M694)5o3`3A1|5t5v4O6k0l6e5B040M6v5Q5 0-5F040J475R6x4p5?0=0d6E5=4Y0k5O042O6K6y3K0q0=0E1^1A5~6G4Y5.5:665S3J0C0d3c6Z4X5M5.0K6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0m62646|6g5e6a0s5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0i3M0G0T0E0s0w5!0S5$2w0E6?7F1Z0k0=0A7U6}3m5^5`5|7f4}5.0h7*4Y736J786S5.0c7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040y7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0b1J1V8k6H8i8U6M0=020z0e0x8X5M6+0=0p8(1~6N0=1^0L8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0l8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0l4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0l4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0B5a4=544@51180e4`b92J2E8_b60B4^650W0Y0!0F04.
Utiliser La fonction tri_insertion
Exécuter le script suivant :
###(Dés-)Active le code après la ligne
(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
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\).
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)