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 tÀ=8fw2mP751,:cSs^ék /Nn9qiy_hDoaIL-v4pu(èFêr]z{[63;0ùdg)}+eRlbàxTOA. 050%0,0b0H0B0.0r0v0p0.0H0r0r0d010b0B0N010406050r0O0i0i0H0T0C040q0G0.0O190G0y0v020H0i0N0!0v0-0,1j0T0A0O0,0r050w1g1i1k1m1e0N04051R1K1U0w1R1e0%0B0L11131517130y0(0O0H0(0,0K0N0C0b0E1t0v0E0B0(0E0.1}0E0b1c050|0/0.0,1%1416011|1~201~0b2628240b0T1S1^111p0r0N0H0y170h012a1)010f0~0,0y1x0,242s2u2z2c2C282F0i2H040a0v0j0T0G0N0G0r0B1s1u0`2q0T0T0,0p2$1K2J0y1S0w1^2=2m2o2n250%2L1*0B0y2E2Z241!1$122b2 310y0G35240N2+1S2:2=3i1f2t1u372A3b0T1j0.240H1{2+0f17030D0D0p3c0,203a0G0K0#0K0m1c0v0m1K0H3j3m1d3l2K3o2c3q3s3u3w0,3y013A3C3E3G323J0K2x040v0h3Q3S2u3U2:2~013Z0H3t1S3v0E3x3z3B3D0`3-3b3/0Z3N0Z3^2/3T1e3|3X173 410543453)473,303.3K0M3N0M4g1L4i3V3n1(3Y0G3r403#443%463+494v4b3K0l3N0l4B3i4j3m3}4n4L4r3*483F4R3I3K0Y3N0Y4X4D4k4G4m4I3!423$3(4)4u3H3/0k3N0k4=3`4Z3W4^3~4`4K4|4M4~4t4Q513K0e3N0e562;584F385b4J4o4q4N4s4P4+5j0K0z3N0z5o3{4!4l5t4{4p4}4O4*4a4-3L0#1c0m0#5G5q4#5c5v5N5y5P4,3/0m3M045+5X4E5Z5u4%5x4 5i4w3L3;0m3@0w3R4h3`1V3g1K352^0%2o2}5J4*341#1S3f0,3h3T612;054*6i2K0B0%173B2:5*3#6q6s5z5Q6v0v2P0,6y5(5B5,4g4@5s0u1c0`0f6k6o5r2A0g3N6Q5:5J0y0f6N0B0p1_0b0G0i0B0,6W6K2A1b040P6.5I5a0y1c3b0i0/2+1J4C626/2c6;0n6Q0v6X6_1c0p0B276-716l73176;0)0o6Q1e7g6R0v6x016t3m3/3;5M7s5h5A5`2x6C2G6F507C245 3=0v7M795s6`040`0/1r777O2A0G1c0d7V7i016+1c5W7p7o3k3|7z0D6u3K4d4|7/6G5`4d7E2Q7G5_4S0K7?3^7M7N7$7Q2C0y7#6^5s7Y047!7p78860/1c2O6@595s6;6?7p7W3Y6{6*6~1I8m6S741c0)8a8n7X1c0K8D8z177(5-7n8y7r6r7t7:7v4x6w8Q7A6A8U7|6E8R7_804y2=3R848h8b2A6M040g1|288I4#6N0,7T0b8^5J8d020.0b0!8f3i8-8E8t04888O5J6;7m7+8O7/7;0K4U7@8W6z5)4T2y6D7~7B809l838,848s4m1c6+200,0O8~5a8d953T978J018p9c7a9a309H8c1c0+9U3p8`8|9Q8o8B9$8F040w0w9)2c8L5~4Y9h9n9j4/9m9t8Y0K4/8!9{9p9}7J8+9y858.2c8:0B6P8g9A3~7b7d8@ac7$9J9K3`9M8_046|8w707-a77j1c0X9.9B049D6,9G8r7$6;0U9f9=aE4!9i8T0K539`8$7H80539 aR7 5RaP9xa58,ad8:2+0b0O0T89aiau010u0p1c0=0T1H8NaK6p9@aN5laQ8Xa15laVb15Ba a!9ya%1c4+ab96ad7Q7c7e9Y2c900(93bjazaq6 ay9Oawbs7QaB9FbsaGaI4Da{1uaM2u3/5Db09o5B5Db4bK5`bIb8a#an6Y9!7Ua.98179JboaeaA0~aCb#8d9XbX9N8L3P9gbD8P6y9j5V8Va06H5TbN8%5Rb_8*7La5ba043F0r7fatbYbt04bB579?b@aN5+b`aW9uc03Mb~aScna3c3bSbT9R9bb-3}b!cybUb%9EaDbeaj8Gb#b/a`cabEa}bG3K5}ckb55`cRcpaX5*7x7Ka$7$a(0{a+a-cGa/a;1c0R40c8b#0p5,030v2!0v1`0y02030Z0z0!3v2t102m0G0O0L0tcL6j0w6n636h656e1K0b68dj2{2?0H7e2=661Q7q5J2+0i0D0f0H0u0,0D0E7?1C1E1G1I0vce6l1X3U353}0H0%0i1t2#0B1`300f8d1QdQdSdU2$0K190b2k041C6%0,0Td:0v2t0T0v1!6%0G6)6+7f1Y1T040I0.c_001/2#d`000O1u400(4I2#0E2Q2L0BdI0^0v0J292j0,0H0Od@0T0B102Ed@1k1x0Q2m290%0Ge91fd61,040G271}0H6)0Bdw2E0b0v0SeE0v2m0Bda1LeK0(040^1V3U1R0c110E0HdI7r0b0t0TeQdW0y0nc{1uc8d`1D2u2(c`130v0L409Fd_0peUe`280v1IeV0t0(fa0v0:0vf76m3E04bhah6ndKe,1e0O0.3U2004c`d70Be~1`2+0y0LeH290B1i0t1!eQ1DeU786na@a_ddfs1KfD1efDc`3be}110{0b29fu29fic_eHeV7mfAfC0BfE0O0Ne_aC2+fnfp3vf928a+f-0y2mfm0o7re5dz1re:d;d:d_0%2u10f7d^19eF2W2#eFeueret0v6?6n7Sgi0d0vbxeu0+3O1K6n8C0wf%05fDdYg1fb29fof7g7fbgagcfgge0~0vgheVglgld`gog5eA0Tgs0vfl0Od?0%gxdp28gzgBfs880vgFgH0v0KgKf!0`04gNgP0wf{7ohdhfe20J3v0V1teF292+g,0E290P0.000t0p1keVfe29frhacxfw0{fWfsgD8}h96h0)c_hpfR0Oe9fo6%e=1He@e_e{1`gefF1u88e9d^0v0HfMeShIhE301v921AhKgLfse~0p00f?e?fq6nf;h`ha6Ch~0reVd4g.0ygpeqg}es0Oen0?f04IeV2(f70/d712f=eVfKh.hC6nc/0 7f6ne+dN7ods0_1#d$dT0ydVdX6Zd!1TiId(e|d*2#d-0x8vg31j0;fP40f2eZd70T102(ipg_2870e11R2V32ic0vec0vhxhzea30d{fOiK19i$hD6hh2h7h_hM3=fki$foad1keh1jf/0;1c090P5V0s0z09gN3ie~0Pfd0v1G0Bfhi8jx1.0y2}0i0Sej2m0Q100(e`jE0)iCi;040Fg/fg0NeSho10hy0rfI0$g:f;i6f?ia3f0tc8gb0,fI1u0T0t40exeqd7idd5i)i+29i-ir102Y15ag1IjQ3UhifD0@eu6gd d_6)a+j=h,i_1ui|g=fhfLeS1`2(jfew1^ji0,jk04jm090fe`0p0Wjo0z0*0W0h0*jr6Qh|i7eVfo1!g3ku7$jgkxfTkAjm0l0v09192Q10jo0ekO8rgOf}f(f}kdf20Oi!0QjIi)kk3vi`kohAkr2W2%hCkXkweik!jl0PkDkF0Wk%k)fPdJk-kKkMk/96h}f?kTjXcv5skYlajjlc0hlhk*lk0#0s0klodcgPkc30c`f5hSf/0v0^lRf$k=gQk@gxfK19k|j{kje kll1hykp0%h~l41`kvjhlbkBldkE0HkGkIlm0s0W0Z0#0*kNjs9LlqjBlskVl-0Lks1u0miChhfBdt0@lLfHib10ec2920i8hoeZ0}0.fgl:kZlyl?kIlH3`e~ezgz0N1qeyl.1ul i(a+101`0r0}eVf6hw0.0t2Qgbh:6hi3jajAi9j@j/0bk9iE6eiE0{mt0r04.
###(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 tÀ=8fw2mP751,:cSs^ék /Nn9qiy_hDoaIL-v4pu(èFêr]z{[63;0ùdg)}+eRlbàxTOA. 050%0,0b0H0B0.0r0v0p0.0H0r0r0d010b0B0N010406050r0O0i0i0H0T0C040q0G0.0O190G0y0v020H0i0N0!0v0-0,1j0T0A0O0,0r050w1g1i1k1m1e0N04051R1K1U0w1R1e0%0B0L11131517130y0(0O0H0(0,0K0N0C0b0E1t0v0E0B0(0E0.1}0E0b1c050|0/0.0,1%1416011|1~201~0b2628240b0T1S1^111p0r0N0H0y170h012a1)010f0~0,0y1x0,242s2u2z2c2C282F0i2H040a0v0j0T0G0N0G0r0B1s1u0`2q0T0T0,0p2$1K2J0y1S0w1^2=2m2o2n250%2L1*0B0y2E2Z241!1$122b2 310y0G35240N2+1S2:2=3i1f2t1u372A3b0T1j0.240H1{2+0f17030D0D0p3c0,203a0G0K0m3J1c0v0m1K0H3j3m1d3l2K3o2c3q3s3u3w0,3y013A3C3E3G323J0K2x040v0h3P3R2u3T2:2~013Y0H3t1S3v0E3x3z3B3D0`3,3b3.0Z3M0Z3@2/3S1e3{3W173~400542443(463+303-3K0M3M0M4f1L4h3U3n1(3X0G3r3 3!433$453*484u4a3K0l3M0l4A3i4i3m3|4m4K4q3)473F4Q3I3K0Y3M0Y4W4C4j4F4l4H3Z413#3%4(4t3H3.0k3M0k4;3_4Y3V4@3}4_4J4{4L4}4s4P503K0e3M0e552;574E385a4I4n4p4M4r4O4*5i0K0z3M0z5n3`4Z4k5s4`4o4|4N4)494,3J0#1c0m0#5F5p4!5b5u5M5x5O4+3.0m0m5T3O0w3Q4g564D5Y5t4$5w4~5h4v3J3:0m3?5.3^2;1V3g1K352^0%2o2}5I4)341#1S3f0,3h3S5:634)6j2K0B0%173B2:5)3!6q6s5y5P6v0v2P0,6y5%5A5+2=5/4?5r0u1c0`0f6l6o5q2A0g3M6R5=5I0y0f6O0B0p1_0b0G0i0B0,6X6L2A1b040P6/5H590y1c3b0i0/2+1J4B3_6Y596=0n6R0v745r6{040p0B276.72636:2c6=0)0o6R1e7i6S0v6x016t3m3.3:5L7u5g5z5|2x6C2G6F4 7E24610v7N797k4l6O0,0/1r787a2A0G1c0d7W7Q016,1c5V7r7q3k3{7B0D6u3K4c4{7:6G5|4c7G2Q7I5{4R0K7@3@7O7P6_7b1c2C0y7$877Y7!8c587b0/1c2O6^8h6;1c6@7r7X3X6|6+6 1I8m6T7l1c0)8g8z177Z040K8D3|7)045-4X8y7t6r7v7;7x4w6w8R7C6A8V7}6E8S7`814x6J3;7O8s176N040g1|288J6Z7S7U0b8^598G020.0b0!7#7r868n8t048a8P5I6=7o7,8P7:7=0K4T7^8X6z5(4S2y6D7 7D819k84858-7%7c6,200,0O8}5r8G943i968E016=8q7.8d989a958.018G0+9F3p8`7V8r7%7m9b8~1c0w0w9)5r8L608O9$4Z9h8U0K4.9l9s8Z9`9q7H8%7J819{9w9x9K3|8:0B6Q9T9z1c7e7g9Y2c9H9I3Sa88_046}8w719P97176=0X9.9Z049B6-9E9?au9M1c0U9e9=at1u9^2u518W9}9o0K528#aR5A528+a7a79U8:2+0b0O0T8bad9Q8/0p1c0=0T1H7p9g9m9i5k9|a2805Q5kaVa~9tb07L3Qa!an598:4*ac9J9U7cag8@a-aF8 0(92ai7Rap8v70ay8A04axaE9L9A0~aCbtavaHaJ4Cbx8Q6y9i5Ca}8YaS5Cb2bN5AbLa6b8b988040`8{bo9V8fbjby1caB9Db#9Wb#8L8NbGaLbI8S9i5UaQb39~b`bQ9n6H5SaZa!a$1c3F0r7hb?9c1cbF5;bHaN0y5)6I7A9m8(5Q5*a07~b|aScoc3bVbWaz9Sbe7%9Hb#bz9CaDcza.b$8Hb/0B5Ta^cfa`9_5 b{bR5|cRb cm5)7z7M9ycHa%0{a*a,cGaF0ua:040R3 c8cN3k0w6n646i666f1K0b69c~2{2?0H7g2=671Q7s5I2+0i0D0f0H0u0,0D0E7@1C1E1G1I0vcd631X3T353|0H0%0i1t2#0B1`300f8G1Qdvdxdz2$0K190b2k041C6(0,0TdR0v2t0T0v1!6(0G6*6,7h1Y1T040I0.0v0r001/2#dY000O1u3 0(4H2#0E2Q2L0Bdn0^0v0J292j0,0H0OdV0T0B102EdV1k1x0Q2m290%0Gd=1f2m1t0(040G271}0H6*0Bdb2E0b0v0Sek0v2m0B0t2/eq1,040^1V3T1R0c110E0Hdn7t0b0t0TexdB0y0n0v1`c8dY1D2u2(2!0v130v0L3 9DdX0peBe!280v1IeC0t0(e^0v0:e;3v056nbh7h6ndpeP1e0O0.3T2004e:0G0O0Be(1`2+0y0Len290B1i0t1!ex1DeB796na=a@c^3E2=fk1efke:3be%110{0b29fbe 0reC0reneC7ofhfj0Bfl0O0NeZaC2+f5f7e?e^a*fR0y2mf40o7td-de1reTdSdRdX0%2u10e=dW19el2W2#eleae7e90v6@6nbZg00d0vb+ea0+3N1K6n8C0wfL05fkdDf-e_29f6e=e@28f@e{f_e}29f|0~0vf eCg3g3dYg6f;g96-0vf30OdU0%gfd428ghgjfJ8a0vgngp0v0KgsfI0`04gvgx0wf%7qg|g~d*0J3v0V1tel292+gS0E290P0.000t0p1keCe|29f9g-30gtfJe eChmg_gl8|g^6i0)d.h8fzfoeCf66(eV1HeXeZe#1`f|fm1u8ad=dW0v0HfuezfEhn1u9092e,b!hx04e(0p00f00veWe=ht6ifbhpg_6Ch,fXeg10g50yg7e6g)e80Oe30?1ufZ0TeC2(e=0/fn12290{0vfshVhl6nc:0 fcfJeOds7qd70_1#dHdy0ydAdC6!dF1TixdJe$dL2#dO0xbr291j0;fx3 e,eGfn0Th}29idg#2871d)1R2V32h 0vd^0vhghid?30dZfwiz19iRh;9930g=h$9#fdf2iRf69U1kd}1jfT0;1c090P5U0s0z09gv3ie(0Pe{h.fofWeC2m0Q100(e!0y0%0)iri$040FgVe~0Nezh710hh0rfq0$f;fV0yh`eC2t103f0tc8f_0,fq1u0T0t3 ede6fni0106*a*iW0viYifjS2Z2!7g0rjy3Th1fk0@ea6hd%dXj,0TjYhTi+1ui.i9e ftez1`2(j4ec1^j70,j904jb090fe!0p0Wjd0z0*0W0h0*jg6Rh*jPf:1!f/kf7%j5kifBkljb0l0v09192Q10jd0ekz8rgwf)fMf)j~e,0OiP0Qd k3k53vi,k9hjkc2W2%hlkHkhd~kKja0Pkokq0WkNkPfxdokTkvkxkV9Jh+h-f6kEk@cHkIk`j8k|0hl1kQl40#0s0kl86kkXf(040@30e:e/hD290^lC1Kgxj}gffs19k)j(a*k,k7i-hhka0%h,k;1`kgj6k{kmk}kp0Hkrktl60s0W0Z0#0*kyjhamlah{lcjFd?2E0Lkd1u0mirh0fid8lwh fpgUi*d^2920fXh7eG0}0.e~lWkJlilZktlr3_e(efgh0N1qeelU1ul,iTj-e)i70}fY0Be;hf0.0t2Qf_hXg_h?h(joebjUeBj`it6fit0{me0r04.
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 t=8fw2mP751,:cSsékE /Nn9qiyh_*DoaILî-v4pu(èr][63;0dg)+eRlbàCxTO. 050Z0%0b0H0A0)0q0u0o0)0H0q0q0c010b0A0O010406050q0P0h0h0H0S0B040p0G0)0P140G0x0u020H0h0O0X0u0(0%1e0S0z0P0%0q050v1b1d1f1h190O04051M1F1P0v1M190Z0A0M0|0~10120~0x0!0P0H0!0%0L0O0B0b0C1o0u0C0A0!0C0)1^0C0b17050@0*0)0%1Y0 11011@1_1{1_0b21231 0b0S1N1:0|1k0q0O0H0x120g01251!010e0_0%0x1s0%1 2n2p2u272x232A0h2C040a0u0i0S0G0O0G0q0A1n1p0=2l0S0S0%0o2X1F2E0x1N0v1:2-2h2j2i200Z2G1#0A0x2z2U1 1V1X0}262`2|0x0G301 0O2$1N2+2-3d1a2o1p322v360S1e0)1 0H1?2$0e12030D0D0o370%1{350G0L0g0L0l170u0l1F0H3e3h183g2F3j273l3n3p3r0%3t013v3x3z3B2}3E3E3I0g3L3N2p3P2+2_013U0H3o1N3q0C3s3u3w3y0=3(363*0W3I0W3.2*3O193=3S123^3`053|3~3!403%2{3)3F0N3I0N491G4b3Q3i1Z3T0G3m3_3W3}3Y3 3$424o443F0k3I0k4u3d4c3h3?4g4E4k3#413A4K3D3F0V3I0V4Q4w4d4z4f4B3V3{3X3Z4Y4n3C3*0j3I0j4+3:4S3R4.3@4:4D4=4F4@4m4J4`3F0d3I0d4 2,514y33544C4h4j4G4l4I4!5c0L0y3I0y5h3;4T4e5m4;4i4?4H4Z434$3G0Y170l0Y5z5j4U555o5G5r5I4#3*0l3H045!5Q4x5S5n4W5q4^5b4p3G2s5$3-0v3M4a3:1Q3b1F302:0Z2j2^5C4Z2 1W1N3a0%3c3O5`2,054Z6b2F0A0Z123w2+5Z3W6j6l5s5J6o0u2K0%6r5X5u5#494-5l0s170=0e6d6h5k2v0f3I6J5)5C0x0e172{1V0o0%6P6D2v16040Q6Z5B530x172e0%0H0P6)525l6$0m6J0u6Q6+170o0A226Y4v5{6!276$0#0n6J19736e3=6q016m3h3*5=5F7f5a5t5:2s6v2B6y4_7p1 5^040u7z6{754f6G0%0*1m6`6|5l0G170c7I7C010h0A175P7c3P7V5)7m0D6n3F464=7Z6z5:467r2L7t5/4L0L7%3.7A7B6*5l6,042x0x7O7`2v7L047N7V7_6?3k0*172J6=6L76176(7X7P7|6.6:8d3?77808827830L8q8e127R5N7a8n7Z7#0L4r7(6k7g6s5Y4q2t6w7/7o7;8F7@7A7J2v6F040f1@238v4U7E7G0b8#5C83020)0b0X853d878w3@177~8n5C6$797V7b3f7e8H7h2p3*4N8G8O6t4M8M7s8I7*7;978S7^7z8U3T177R1{0%6;869l12838;3O8?8o8g8{6}040=8(8*53830$9G7{8_2{9B6@170#9K82170v0v9S278y045@4R8B937!7i4%6p9(9f5K4(7-6x9e7u7;4(2-3M9j8T7P8W0A6I9s8j6~708!a2818s178-8/9X7D048l9r91a8126$0U9O3k9n0_0A9qan8f040T8~9$8i4T8C9*0L4|989?7:5K4|9;998KaD7w9{9|9j9t8^7}9Na78r9u7MadaT9oarah9xaS8ta!9Z3K8 9%6r8D5eaF7n9a0L5eaKaG8P5Ka?9iaR9~174!a18=aS7|6 71a!9v9w3:9y6R6-0H718mazaX01alataea$asbm8@6$aw8Abu0uaB953F5wa@8J5u5wa|a^aMbEb1aQbg538W2$0b0P0S7 aW8@7|bsa(50a:8I8D5O9,aL6A5MbJbG5:b*9`7yaQaS8W3A0q72aibn8}byb~1pbB0x5Z6B3q7)9@5K5!9c7.a}a_ccb?bO7^b88%7HbX3?9va!bZaqbtb77P9Ia,7S5$c16c92a;aC0l7kc89-ca5Z7q8NcfaMcGaOb@9kb304bSbUbWcvaj010s0o170w1ob}4w7X0v6g5|6a5~671F0b61c@2?2.bj232-5 1L6K3?2$0h0D0e0H0s0%0D0C7%1x1z1B1D0uax6c1S3P303?0H0Z0h1o2W0A1=2{0e831Ldodqds2X0L140b2f041x0o0C0%0SdK246W1;0b0G7RdgbA0b0r0S0H140M240n0u0+2l0x2A0K2h721T1O040I0)0u0q001*2W0u2Z0)d{0)0!4B2W0C2Ld~242$dOdNdLd~0AdK0GdSdU1C2G0Adg0:1Q7Wd00;1WdAdr0xdtdv6Sdy1OeudCduc5dFdH0J3qeadLecdP24e06VefdP0P0ub!epd10J240o3_0o0Pd^d 00eQ6Xd~eTb!eUdY2W24dS1m3Y0G0A0{dg0)dg0{3y1d2z0@0A2$0q0:0u0I6 0u1=3a2S2U246f3z3?1$1(1*1,1.1?1|2b1}2Dc!cs9pb#2,bP7KaZco8|9Abzbh9D7FcncZbncxfD9C8`fG538pfOfB049Vcy179#dk6geodld10/0S0md~2pf0dMf40x0{flfn0{2Zfe0!dZ1I2X2lf20u230u0,f,0~0uf40)g30=0{f3ar0Sgd0q0bg20A7RdX0%f80,eZe#e%6{4Zfk2pfm1+1-0Bfq2a1|1~d2fHeVfU9T84a!6$8hc28$fI9FgJa9049JgTaefQgPfE049RgX0183fXg(9Zf!5{c.3z7y0O9qgj2o0Sdxe{0u0%0-0o0r0=0S0|0?0be?0^gaeOgle=f80t1p3Y0e0?f,2Vg2dh0=0P0-bA0x6Wdhfi2Z5Cfl1)gzfp291`gEfubn7|9EfKf#g;g}gjhueZ53hxfngAgChC2chEbY9McYhJ0=7y0q1ogjf|2p0Z0qg69qh3h%g1hNgw1%hyfogBhBfsgFclgRhIbfa*17gWfLhXaUhZg/6g0ug?1md~0r2o10dMg23q0M3_h/gkgmgoeWd=0Ff.h40|0 fc3igsg3ePhreRe-eUcteT2z0u1maq0q2pgjg70~0S1+bUe8g2e*0xh60Simh9digufjhwgxh_hSh|hDgG9CgIi6cpfCi@fHhH8)g(fNi`fSfFg!fPaVj0fV8ug(hGfJi}j39Pg$bc9U9Wg,czg.6eg:h#f%d;1Miuf=hlix0{3a0rb|iZh.ic2R220Re72|d_242Tb|iciye!f+g}1p0i1/1;0xh.gdiZgf0{0x00h(jMf_h70_iChbh6f80.0Ge^g{h-0u0p0AiX1=0Himd}1eew0Oe%0re8j!dT0*f60u0e0)eh0@iZf?jJjD0)jF24b|dZd}0H0Og_eTf1e7g_g}0-1y0Og38~d;dn5Cdpevexhf0-1skz2MdzkEdBewdDeG2M0tkx1ta6kCeti+h^hR1.3y1pi/hVi;5l2I2z2B17jS1:1=0,1oh%g30p1D2V1o6P696K3/6ec/cDb(7i0W3Gb+cO4`l93Hb/9.7=la5V5.a~li6B7xaS0!6$020!8/ltlvlu1vbqaTi|jggLg,6T9!0:7Uj6gK0E0EfY5$0Y0g48a/bzc4licHbAcJaHlWcd9=bKld3+lkl(3)l97klp7Plraalylw0Xl^6{fR9Li86`cTc!cqlFfZlIlDlMlO5OlRlDi5a)7Pa-cB74aA9(6nl97?cIb,l-7=l$mo44ml2t585HcKmub?lqlsl@mD8/l{jdaoi0jcmdm1i4crhYl aS0o5#03ifihb|2LiZiWe!2o6 dXmg7dmicE95l98Rmnlcmp4rlgmy8Emv4Xl,mtm_mAl;83dwm)d2lVl99hm:m|3Dn6mrm;m}4Nl+b:necRmBl?lxnmlzl|6#j2cCfvcmmKi2cwmNj9mPnpaug%lKgUjinE8xjkmQ7PmS17mU0Zig261yf3m!kp0Hm%k4kcggiWg7h;2Ln37Ymjl80L9_7llZlml99:cNn9li9:mw5Wm^n.l:c!e36U6Sn)l694c5l9aEn/msnaaNm@l!o8m`5-n^ogm o0mCnnl`lAjagSnHg)nyotgNoqnAota+nzmJlAfToA9UlOjl7WgPn5a`lbojoNoen;oQn{ll6tl9b0n bno1040d0:0y0d0d0N0V0k0V0j0N0W5!0k0d0%0$0W0Y4~lT3fjnc;1S5}0verp4677bp50=g90q04.
###(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 t=8fw2mP751,:cSsékE /Nn9qiyh_*DoaILî-v4pu(èr][63;0dg)+eRlbàCxTO. 050Z0%0b0H0A0)0q0u0o0)0H0q0q0c010b0A0O010406050q0P0h0h0H0S0B040p0G0)0P140G0x0u020H0h0O0X0u0(0%1e0S0z0P0%0q050v1b1d1f1h190O04051M1F1P0v1M190Z0A0M0|0~10120~0x0!0P0H0!0%0L0O0B0b0C1o0u0C0A0!0C0)1^0C0b17050@0*0)0%1Y0 11011@1_1{1_0b21231 0b0S1N1:0|1k0q0O0H0x120g01251!010e0_0%0x1s0%1 2n2p2u272x232A0h2C040a0u0i0S0G0O0G0q0A1n1p0=2l0S0S0%0o2X1F2E0x1N0v1:2-2h2j2i200Z2G1#0A0x2z2U1 1V1X0}262`2|0x0G301 0O2$1N2+2-3d1a2o1p322v360S1e0)1 0H1?2$0e12030D0D0o370%1{350G0L0N0L0l170u0l1F0H3e3h183g2F3j273l3n3p3r0%3t013v3x3z3B2}3E0L2s040u0g3L3N2p3P2+2_013U0H3o1N3q0C3s3u3w3y0=3(363*0W3I0W3:2*3O193@3S123`3|053~403!423%2{3)3F0N3I0N4b1G4d3Q3i1Z3T0G3m3{3W3 3Y413$444q463F0k3I0k4w3d4e3h3^4i4G4m3#433A4M3D3F0V3I0V4S4y4f4B4h4D3V3}3X3Z4!4p3C3*0j3I0j4-3=4U3R4:3_4=4F4@4H4_4o4L4|3F0d3I0d512,534A33564E4j4l4I4n4K4$5e0L0y3I0y5j3?4V4g5o4?4k4^4J4#454(3G0Y170l0Y5B5l4W575q5I5t5K4%3*0l3H045$5S4z5U5p4Y5s4`5d4r3G3,0l3/0v3M4c3=1Q3b1F302:0Z2j2^5E4#2 1W1N3a0%3c3O5|2,054#6d2F0A0Z123w2+5#3W6l6n5u5L6q0u2K0%6t5Z5w5%4b4/5n0s170=0e6f6j5m2v0f3I6L5+5E0x0e172{1V0o0%6R6F2v16040Q6#5D550x172e0%0H0P6+545n6(0m6L0u6S6-170o0A226!4x5}6$276(0#0n6L19756g3@6s016o3h3*3,5H7h5c5v5=2s6x2B6A4{7r1 5`3-0u7B6~5n6.040=0*1m6|7D2v0G170c7K77120h0A175R7e3P7X5+7o0D6p3F484@7#6B5=487t2L7v5;4N0L7)3:7B7C7R3_172x0x7Q6,5n7N047P7X6}7|0x0*172J6@6N78176*7Z896/0H736=8e3^79816^7M170L8s8f7S7U5(7c8p7#7%3E6r6m7i6u5!4s2t6y7;7q7?4t2-3M7`88822v6H040f1@238x4W6I0%7I0b8(5E84020)0b0X863d8W8t3T7~2{8p5E6(7b7X7d3f7g8I7j2p3*4P7*978K5w4P7/6z8J7,7?9b7_8V7`7L8|047T1{0%6?879q12848^3O8`8y016(8i958X9r7H7J9x7|840$8.6 047 8 558r9N9J9z170v0v9R5n7T175_4T8D9d8F4*9c8P6v4)8N7u9j7w7?9;9n9o9D3^8Z0A6K9Y8{4h70728%a69E8:8=0X9(3k8l8n9w9Ia79F170U9V7E179t0A9var6%170T929-8j4V8E7k3F4~9=9{7=5M4~9h9?8L0LaI9 a09p8k9T8~ac3^9Aah9rauawaZ8/8va$8z5P8CaD6k9/aG0L5gaJ7p9@a^9_7:aK8Q5Ma_aT8V9y018Z4$a58_b67F7173a-019A9B3=a16Taj238oa;9E6(aqbq8)9s0_aval6e7|6(aAa:am1paF993F5ya`9e5=5yaOb0a|bKb4aUb68Z2$0b0P0S80a*9Sa(bz529.6t8F5Q8HaP6C5ObPa{aQb.8T7Aa0bV173A0q74bF8q17aB4ybubH0x5#6D3q7+9|5M5$a~9ib@6C6D7zaU9obc8*8,bga#b$asbw9ub)2,bl559Pbg9*8B93b+8Jb-7mcc9d9kcf7s8ObQb^7mcmaV9Zb717bXbZb#bb7|0s0o170w1oc19Cb60o5%030u0p0A0u1=0x02030W0y0X3q0Sav1p2h0G0P0M0rbE6e0v6i5~6c60691F0b63di2?2.8m232-611L6M3^2$0h0D0e0H0s0%0D0C7)1x1z1B1D0uc55}1S3P303^0H0Z0h1o2W0A1=2{0e841LdPdRdT2X0L140b2f041x0o0C0%0Sd/246Y1;0b0G7TdH0u2W0r0S0H140M240n0u0+2l0x2A0K2h741T1O040I0)0u0q001*2W0u2Z0)em0)0!4D2W0C2Lep242$d?d=d:ep0Ad/0Gd`d|1C2G0AdH0:1Q7Ydr0;1Wd#dS0xdUdW6UdZ1OeVd%dVc9d*d,0Jd12%d:eDd@24er6XeGd@0P0ub(eQds0J240o3{0o0Pejeq00e^6Zepe{b(e|e02W24d`1m3Y0G0A0{dH0)dH0{3y1d2z0@0A2$0q0:0u0I71c_1p3a2S2U246h3z3^1$1(1*1,1.1?1|2b1}2DcW7Fe}cu8u85bg9Gax9K8+9Mc$cWcCfZ9r9Ubu90170#cs9#9%f/a.049,db6iePdMds0/0S0mep2pfrd;fv0x0{fMfO0{2ZfF0!e11I2X2lft0u230u0,g70~0ufv0)gr0=0{fuav0SgB0q0bgq0A7T0b0r0%fz0,f1f3f56}4#fL2pfN1+1-0BfR2a1|1~dtbmcwbyf_f#f|ao6)f(a87Gf*8-g/f.f,an7Ff;c2f?04f^g`f`cD8Af dL6i0u0O9vgH2o0SdYfm0u0%0-0o0r0=0S0|0?0bfh0^gye?gJfgfz0t1p3Y0e0?g72VgqdI0=0P0-d~0x6YdIfJ2Z5EfM1)gYfQ291`g%fVg}cqf+g03z3-0?gTfKhSgWhUfPg!hXfTg(cpaXc#h(0=3-0q1ogHgk2p0Z0qgu9vhph gphQf155hTfOgZg#hY2ch!9E7F9Lg_g|ad179Qg/g~aY3fdch)hbhdep0r2o10d;gq3q0M3{i7gIgKgNe~eg0Fg9hq0|0 fDiT0)f4gre@hNe_fbe|bx9vhj1p1mbx0q2pgHgv0~0S1+bZezgqf80xhs0SiIhvdJh,hRidh/ifhWfShZg)b%i)cy3-b6ctipbving-isjih19HbAfW8}h{bkjga,ith$iojqan9XjncBh5g/cEh86gixh}g2ef1MiQgdhHiT0{3a0rc0i}i6hb2R220Rey2|ek242Tc0hbiUf2g6i+2P1/1;0xi6gBi}gD0{0x00i0j-ghht0_iZhxhsfz0.d6hshhi5c?c^er1=0HiIeo1eeX0Of50rezj}d{0*fx0u0e0)eI0@i}gej*j!0)j$24c0e1eo0H0Ohfe{92efdO5EdQeWeYhB0-1s0Od,d!kRd$eXd(e+2M0t0-1ykYeedNeUh.1%h:gZ3y1ph?jab62I2z2B170ij?1=0,1oh gr0p1D2V1o6R6b6M3;6gdd96b,7k0k3Gb/cR4|lm3Hb?bM46lr2t5a5Jce0Llwb`b60!6(020!8?lHlJlI1vg=7}g@crh4g.jD9)6Vf~0:7WlUf!0E0Eh65P0Y0g4acGc7a?99lmcKd~cMlAl;chb:3)l_5X5:b1lB3+7y5{7|lF17lK0Xm8m86}f=9Sg 9C7{f-7OcDlW0glYg-l$l(5(l*l,l!27g{c.7|cE3Kl-c2c8m17^cLl{lv7@l`lpl|mJl~cjmM7^7zlElGlMmalMmch09SjklSjmmxjrh`6|cA5nc:17c=0ZiC261yfui`f22o71gLda76aEl/c9lm8S7nl@aLm14tltcNn8lx4ZmPmIn4mSm584dXm~7fn0lkl:lBlonf3Dlm9gcQntm19gly5Yl^nrlDm5mUlLnIlNmd6_8hlOimg^jlbgiujtnnjBf@g-f{muf}jI7Ac/c;iBiDc02Li}m_kK0Hm|kpkxgEi`gvi92LnmdtmDlm9~mGmLmI4*nanDo5nBl 6vo0m3jb5neu6W6Un}7!n1m1aSo2nylmaNnxlunuaRnd5/opovnFcWm604mWnJmYjAiljynRg/f%nLaim*lS8wjxlQh%m nWh2nYmqn$94oHl?npn2a}bLnblm5go6n7o-ow5botm1b3nioB840d0:0y0d0d0N0V0k0V0j0N0W5$0k0d0%0$0W0Y50mBh|df1S5 0veSpm697dpn0=gx0q04.
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 vt4=wf2pmuP(j751:,cSsr]k[63; dg)/+niyelh_boa- 050E0M0c0S0K0N0v0D0t0N0S0v0v0e010c0K0i010406050v0k0j0j0S0w0L040u0R0N0k0.0R0J050H0^0`0|0~0?0i04051e171h0H1e0?0E0K0b0$0(0*0,0(0J0F0k0S0F0M0T0i0L0c0O150D0O0K0F0O0N1J0O0c0;050X0Q0N0M1q0)0+011I1K1M1K0c1S1U1Q0c0w1f1E0$110v0i0S0J0,0h011W1s010g0Z0M0J0S0j0M1Q1=1@1|1Y1 1U22240;0a0D0l0w0R0i0R0v0K140J0D0V1:0w0w0M0t2p17270J1f0H1E2C1,1.1-1R0E291t0K0J212m1Q1n1p0%1X2M2O0J0R2S1Q0i2v1f2A2C2)0@1?2q2U1}2Y0w0{0N1Q0S1H2v0g0,030P0P0t2Z0M1M2X0R0T0o0T0q0;0q170S2*2-0=2,282/1Y2;2?2^2`0M2|012~3032342P370T1`040h3d3f1@3h2A2L013m0S2@1f2_0O2{2}2 310V3w2Y3y0B0;0B3D2z3g0?3H3k0,3K3M053O3Q3s3S3v2N3x380d0;0d3#183%3i2.1r3l0R2=3L3o3P3q3R3u3U3@3W380p0;0p3}2)3(2-3I3,473:3t3T334d36380A0;0A4j3 3)423+443n3N3p3r4r3?353y0o0;0o4A3F1i2%172S2F0E1.2K3*014s2R1o1f2$0M2(3g3$4S4s4-280K0E0,2 2A3y3a4H4@4_4b4t4M383a0D2d0M504s3V4v391Q0H3e403I0y0;0V0g4/2B5h4#0f0;0D5n4=412V3J0g0;1,0K0P0v332w2y3~4S4C5x0:040m5u5p4D3J5A0S1T0M0S0k5P5K1}5M0G0r5u0?5I5o3H4 014`2-3y3A3.0D5.3=4c533z1{57594L3^5}2C3e0D665t5!1Y5j040g445u684m4#0J0;0K6f5Q5x0R5r042N6m693+0Q0;0w1@1z5Z6h5R5M5O5+5v4n6w042c6B3j6D0;6F2+6u5S041)5W5Y6G6n5#0;0G6t6C6o0;0T6%6N5x0j0K3b6M5w6!045%5)6=5^4^5/5D5;383Y4~6}5`52623Y5623586~5a4u3X5e65677i6Z3l6k0P6/0J6l6G6g6-1}0R0;0e6,6?7l6r6`6Y5-746 1@3y3`73605{623`79247L764e0T7J3D7i7j6S6b6d0w7y4n0;0n7%4#6p6k167r7k6v6x6z0M6{4#6E7_5R6j7B7:6S7v040I7+5R6/6;7D6(6@0s855x0J6J6L897t1Y7{8i7z3+5T5V5X7|5L6#6_6G5*6R4m5_7G0J3y4g7K7c617T4g7P7b755b8D7g047X8R7s8n016b0K5m808a7A6V8r8m3I5M0z8s2:7)8,8k0;0x8d7u0;020N0c0C8?8#5U1U8%8y8j0,8*8/8o6r7n2N7q928U5M0x5(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;98a4a18t040x9_2)9Fahacak6@af4.9(9=at8:am7C2+0H4;4T4,4V4)170c4YaK2I2D9}2C4W5*0V0X0Z0v04.
###(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 vt4=8fw2pmuP(j751:,cSsr]ék[63; dg)/+niyelh_boa- 050G0O0c0U0M0P0w0F0u0P0U0w0w0e010c0M0j010406050w0l0k0k0U0x0N040v0T0P0l0:0T0L050J0`0|0~100^0j04051g191j0J1g0^0G0M0b0(0*0,0.0*0L0H0l0U0H0O0V0j0N0c0Q170F0Q0M0H0Q0P1L0Q0c0?050Z0S0P0O1s0+0-011K1M1O1M0c1U1W1S0c0x1h1G0(130w0j0U0L0.0i011Y1u010g0#0O0L0U0k0O1S1@1_1~1!211W24260?0a0F0m0x0T0j0T0w0M160L0F0X1=0x0x0O0u2r19290L1h0J1G2E1.1:1/1T0G2b1v0M0L232o1S1p1r0)1Z2O2Q0L0T2U1S0j2x1h2C2E2+0_1^2s2W1 2!0x0}0P1S0U1J2x0g0.030R0R0u2#0O1O2Z0T0V0f0V0r0?0r190U2,2/0@2.2a2;1!2?2^2`2|0O2~01303234362R390V1|040i3f3h1_3j2C2N013o0U2_1h2{0Q2}2 31330X3y2!3A0D0?0D3F2B3i0^3J3m0.3M3O053Q3S3u3U3x2P3z3a0d0?0d3%1a3)3k2:1t3n0T2@3N3q3R3s3T3w3W3_3Y3a0q0?0q3 2+3*2/3K3.493=3v3V354f383a0C0?0C4l413+443-463p3P3r3t4t3^373A0p0?0p4C3H1k2)192U2H0G1:2M3,014u2T1q1h2(0O2*3i3(4U4u4/2a0M0G0.312C3A3c4J4_4{4d4v4O3a3c0F2f0O524u3X4x3b1S0J3g423K0A0?0X0g4;2D5j4%0h0?0F5p4@432X3L0g0?1.0M0R0w352y2A404U4E5z0=040n5w5r4F3L5C0U1V0O0U0l5R5M1 5O0I0s5w0^5K5q3J51014|2/3A3C3:0F5:3@4e553B1}595b4N3`5 2E3g0F685v5$1!5l040g465w6a4o4%0L0?0M6h5S5z0T5t042P6o6b3-0S0?0x1_1B5#6j5T5O5Q5-5x4p6y042e6D3l6F0?6H2-6w5U041+5Y5!6I6p5%0?0I6v6E6q0?0V6)6P5z0k0M3d6O5y6$045)5+6@5`4`5;5F5?3a3!506 5|54643!58255a705c4w3Z5g67697k6#3n6m0R6;0L6n6I6i6/1 0T0?0e6.6^7n6t6|6!5/76711_3A3|75625}643|7b267N784g0V7L3F7k7l6U6d6f0x7A4p0?0o7)4%6r6m187t7m6x6z6B0O6}4%6G7{5T6l7D7=6U7x040K7-5T6;6?7F6*6_0t875z0L6L6N8b7v1!7}8k7B3-5V5X5Z7~5N6%6{6I5,6T4o5{7I0L3A4i7M7e637V4i7R7d775d8F7i047Z8T7u8p016d0M5o828c7C6X8t8o3K5O0B8u2=7+8.8m0?0y8f7w0?020P0c0E8^8%5W1W8)8A8l0.8,8;8q6t7p2P7s948W5O0y5*8y6}8C4}4y3q8C7f5~4z8M7T8P9n668S8U9z7?6V5E7q9d3i8V3K847z8#956V7,9j8*9l720V4Q8H8O7g3a4Q9t8I7O7V9U7Y8U9B808(6Z9e8+0?8-8*6k6m98019g8e9L8W9,916Y9_979?7 7o9Ea28?8 0.9Jaa6V9-a8049=9/9@9aa7a48v040y9|2+9Hakafan6_ai4:6U809F5L8$96a97tat5T0u4 030F0z0u0Q7_7E2-0J4?4V4.4X4+190c4!a!2K2Fa02E4Y5,0X0Z0#0w04.
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 vt4=8fw2pmuP(jè751:,cSsr]k[63;0 dg)/niyelh_boaO- 050H0O0c0U0M0P0x0G0v0P0U0x0x0e010c0M0j010406050x0l0k0k0U0y0N040w0T0P0l0;0T0L050K0{0}0 110_0j04051h1a1k0K1h0_0H0M0b0)0+0-0/0+0L0I0l0U0I0O0W0j0N0c0Q180G0Q0M0I0Q0P1M0Q0c0@050!0S0P0O1t0,0.011L1N1P1N0c1V1X1T0c0y1i1H0)140x0j0U0L0/0i011Z1v010g0$0O0L0U0k0O1T1^1`1 1#221X25270@0a0G0m0y0T0j0T0x0M170L0G0Y1?0y0y0O0v2s1a2a0L1i0K1H2F1/1;1:1U0H2c1w0M0L242p1T1q1s0*1!2P2R0L0T2V1T0j2y1i2D2F2,0`1_2t2X202#0y0~0P1T0U1K2y0g0/030R0R0v2$0O1P2!0T0W0s0F3a0@0s1a0U2-2:0^2/2b2=1#2@2_2{2}0O2 01313335372S3a3c1}040i3g3i1`3k2D2O013p0U2`1i2|0Q2~3032340Y3z2#3B0W0D0@0D3G2C3j0_3K3n0/3N3P053R3T3v3V3y2Q3A3b0W0d0@0d3)1b3+3l2;1u3o0T2^3O3r3S3t3U3x3X3{3Z3}0r0@0r422,3,2:3L3:4c3@3w3W364i393}0C0@0C4o443-473/493q3Q3s3u4w3`383!0q0@0q4F3I4q3m4I3M4K4b4M4d4O3_4h4R3}0f0@0f4W2E1l2*1a2V2I0H1;2N3.014x2U1r1i2)0O2+3j3*3I054x572b0M0H0/322D3!0s3r5f5h4g4y4-3c5l0G2g0O5o4x3Y4A5s1T0K3h453L0A0@0Y0g594?4H2Y010h0@0G5L5d465O0L0g0@1/0M0R2Q0x0O0y2B435a5N200?040n5T5F4 0L5Z0U1W0O0U0l5?5.1#5:0J0t5T0_5,5M4r5n015i2:3!3D3=0G6b4+5q3|3C1~5v5x4Q6m0W6g5D040G6x5S610/5H040g495T6z4r5^0@0M6G5@4!0T5Q042Q6M6A3M0S0@0y1`1C606I4!5:5=685U3L0k0M3e6#4Z5O5:0u6T6$5W6W042f6:5V5/0@6)2.6U5_041,5}5 6*6N6=0@0J64666~6i5g6c0R5j3}3$4M6j5p5z3!3$5u265w7k5y4z7t5C3h6y7E6H6;2?0@0b3O0O0l0y0R0U5$0L5(2y0y6^7H1#0T0@0e7W6 3o5`5|5~7h4 5:0B7,4!756L7a6U5:0z7g7@6a7j6d1`3!3 7p7~7r7A3}3 7v276q4,6s823G7F6y7b7I040o7$3L7Z047#6*7G7%3/6K7{737}5o7m3c4l838b6l4j8B6o7w8E7s4k7C6w8g8s5G0@0h1L1X8m6J8k8W6O0@020I0c0E8Z5O6-0@0F8*206P0@1`0H8/7(765{1X7+7|7X0/7.7:5W0@8l8r8i7Y0@0W8^0/8,043f8~8t017_9b018o8$8(9k757K1X7N7P7R7T5)927004656*678x5e848A0W4C8D7y6r8G9I8I8a9L8c9N9J8f8P7E978u8`7*799E9h919g4s949y620@7`966U8o8q2,8Q8X778}9%3L9)9}8X959^9Y9l999k9d9fa06%9/8w583K7q9H4T9K6k8L3c4T897xak86am8N9W9X749,9;6_8:7!9paxa39=a6ay8 01a8ad5-8y7k9H4/aj855r0W4/ao8KaraUat8Pa4759{9$aeaz9.047/9*a19-90acaH9h9?aC049r7M7O7Q5%5)9xa@3L0v5l04030G0V2t5%0p2yaL4?0K5c4@564_531a0c4|bn2L2G8{bk0K4`670Y0!0$0x04.
###(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 vt4=8fw2pmuP(j751:,cSsr]k[63;0 dg)/niyelh_boa- 050G0N0c0T0L0O0w0F0u0O0T0w0w0e010c0L0j010406050w0l0k0k0T0x0M040v0S0O0l0/0S0K050J0_0{0}0 0@0j04051f181i0J1f0@0G0L0b0%0)0+0-0)0K0H0l0T0H0N0U0j0M0c0P160F0P0L0H0P0O1K0P0c0=050Y0R0O0N1r0*0,011J1L1N1L0c1T1V1R0c0x1g1F0%120w0j0T0K0-0i011X1t010g0!0N0K0T0k0N1R1?1^1}1Z201V23250=0a0F0m0x0S0j0S0w0L150K0F0W1;0x0x0N0u2q18280K1g0J1F2D1-1/1.1S0G2a1u0L0K222n1R1o1q0(1Y2N2P0K0S2T1R0j2w1g2B2D2*0^1@2r2V1~2Z0x0|0O1R0T1I2w0g0-030Q0Q0u2!0N1N2Y0S0U0r0r380=0r180T2+2.0?2-292:1Z2=2@2_2{0N2}012 3133352Q383a1{040i3e3g1^3i2B2M013n0T2^1g2`0P2|2~30320W3x2Z3z0U0C0=0C3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390U0d0=0d3%193)3j2/1s3m0S2?3M3p3Q3r3S3v3V3_3X3{0q0=0q402*3*2.3J3.4a3=3u3U344g373{0B0=0B4m423+453-473o3O3q3s4u3^363Y0p0=0p4D3G4o3k4G3K4I494K4b4M3@4f4P3{0f0=0f4U2C1j2(182T2G0G1/2L3,014v2S1p1g2%0N2)3h3(3G054v55290L0G0-302B3Y0r3p5d5f4e4w4+3a5j0F2e0N5m4v3W4y5q1R0J3f433J0z0=0W0g574;4F2W010h0=0F5J5b445M0K0g0=1-0L0Q2O0w0N0x2z41585L1~0;040n5R5D4}0K5X0T1U0N0T0l5;5,1Z5.0I0s5R0@5*5K4p5l015g2.3Y3B3:0F694)5o3`3A1|5t5v4O6k0U6e5B040F6v5Q5 0-5F040g475R6x4p5?0=0L6E5=4Y0S5O042O6K6y3K0R0=0x1^1A5~6G4Y5.5:665S3J0k0L3c6Z4X5M5.0t6R6!5U6U042d6.5T5-0=6%2,6S5@041*5{5}6(6L6:0=0I62646|6g5e6a0Q5h3{3!4K6h5n5x3Y3!5s245u7i5w4x7r5A3f6w7C6F6/2;0=0b3M0N0l0x0Q0T5!0K5$2w0x6?7F1Z0S0=0e7U6}3m5^5`5|7f4}5.0A7*4Y736J786S5.0y7e7=687h6b1^3Y3}7n7|7p7y3{3}7t256o4*6q803E7D6w797G040o7!3J7X047Z6(7E7#3-6I7_717{5m7k3a4j81896j4h8z6m7u8C7q4i7A6u8e8q5E0=0h1J1V8k6H8i8U6M0=020H0c0D8X5M6+0=0E8(1~6N0=1^0G8-7$745_1V7)7`7V0-7,7.5U0=8j8p8g7W0=0U8?0-8*043d8|8r017@99018m8!8$9i737I1V7L7N7P7R5%906~04636(658v5c828y0U4A8B7w6p8E9G8G889J8a9L9H8d8N7C958s8^7(779C9f8 9e4q929w600=7^946S8m8o2*8O8V758{9#3J9%9{8V939?9W9j979i9b9d9~6#9-8u563I7o9F4R9I6i8J3a4R877vai84ak8L9U9V729*9/6@8.7Y9nava19:a4aw8}01a6ab5+8w7i9F4-ah835p0U4-am8IapaSar8Na2739_9!acax9,047-9(9 9+8~aaaF9f9;aA049p7K7M7O5#5%9v9A5;0J5a4=544@51180c4`b92J2E8_b60J4^650W0Y0!0w04.
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)