Tri avec une pile⚓︎
L'objectif est de trier les éléments d'un tableau. On suppose que les éléments contenus dans le tableau peuvent être comparés avec l'opérateur <.
Le tri est effectué suivant l'ordre croissant. Donc, lorsque le tableau est trié, les éléments y sont rangés du plus petit au plus grand. Un tableau vide est trié.
On se sert d'une pile et pour la représenter on utilise simplement une liste Python avec uniquement les méthodes append, pop et la fonction len. Attention, on ne peut pas utiliser d'indice avec une pile.
1. Insertion dans une pile
Écrire une fonction récursive insertion qui insère un élément x à la bonne place dans une pile où les éléments sont empilés du plus grand au plus petit. L'élément x et la pile sont les paramètres de la fonction. Cette pile est modifiée par la fonction qui ne renvoie rien.
Exemple
>>> p = [8, 7, 5, 4, 3, 1]
>>> x = 6
>>> insertion(x, p)
>>> p
[8, 7, 6, 5, 4, 3, 1]
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 beqn,4é9vià3mo5_tLxR;Phklpwf(: cg.a=ry0S6u/72)As18d 050Z0c0r0J0k0z0W0F0G0z0J0W0W0K010r0k0A010406050W0Q0n0n0J0L0M040O0o0z0Q0@0o0e0F020J0n0A0v0F0u0c110L0d0Q0c0W050R0~1012140|0A04051z1s1C0R1z0|0Z0k0j0,0.0:0=0x0k0H0x0z1Q0x0r0`050%0b0z0c1L0/0;011P1R1T1R0r1Z1#1X0r0L1A0r0x0,170W0A0J0e0=0T011%1N010C0)0c0e1f0c1X1}1 241)271#2a0n2c040a0F0w0L0o0A0o0W0k1a1c0#1{0L0L0c0G2x1s2e0e1A0R1_2J1?1^1@1Y0Z2g0=1T0e292u1X1I1K0-1(2T0k2V0e0o2Z1X0A2C1A2H2J2;0}1~1c2#252*0L110z0`0F0X2G2^0{2@2f2`1)2|2~300T331 352H2S013a0J2 040F0m3e2I0|3h380=3k3m0F0g3q3g2^3i3w300p3A3s3C3u3j0o2}3l300P3H362_1M393M3b3n0S3R3t3U3v3W3O3n0Y3!3J3$3L3N3x0i3,373.3E040X0N3?3T2$3/3X0X321t341D2/1s2Z2M0Z1^2R3K0G2+2m0!1J1A2.0c2:45443f054f0#4n3@3 0y0`0#0C3A3S3i0B304B3#3 0e0C0`2(0W0c0L2F4p2I4C3K0_040D4G3-4I0`0t4Y4v254V0f3A0F4T3^0`0A284%3~4)0`0U0E3H0F4}4-4H254x040k4A4R3n4.4I0b0`2j4?3i4V4X56582{4:4=5h501)4V0U4,5i1)0o0`0K0K5r5n0=0n0k0`3|5m4Z4^044{56064~5M4 5G395k1#5d3K5u040I5T4/040J0A0A290Z5Y3 5f5*5j044$5F4(5o4_4|4~5s0=520c0*0c5-5?5I5^5N5O5=3v0`0M5y5P0=5V5x56654@5Q044;5S5;6h6c0`5X6m3D4:2s600=5f5q5K644}5`0152546a663j4#6G6n015V020H0r0v6K6s04696r4U0`5J2;5L6A5M6C0e4L0e4N4P0k1b6v015,6W5Z5:2?5z6;0`4+6f6(5R5 6?5+5@6z6$5_6`6)6j5l6_6b6M6p6:795#5%0e5)725H5g7c6H796V7p6L5p635N6C5|5~6:4V6Z346#766g6T6k717t3i5V6q7L3K7h5$5(7B0`7o4578687U046y6!7G6B7Y7a6l7P3.7N7g0`7i7T7m617W4q7*6^7X7d7v5K1s4s4m46830R491s0r4b882P2K0J1!85491y4u6L2C0n0q0C0J0y0c0q0x0m0`1k1m1o1q0F7D4q1F351z0V1/292x0F0l0F0e00190)0k6,0F0J0j2D0F0.0F7J0F8y8X8z0n0h1_4g0+4r4g5!7S7k818/0f4-826j6u0R8`0F0$8X0J0F0C1b2E6.1c8.4t5c8}8/0I0F0s8O0@1T0W0J8J0Z002(1I0G1$8N1q0r8Z0/8Z2u2v8f6q1G480$0(0*04.
2. Tri d'un tableau
Écrire une fonction tri qui prend en paramètre un tableau à trier, insère les éléments de ce tableau dans une pile à l'aide de la fonction insertion et lorsque tous les éléments ont été insérés, les retire de la pile et les place un à un (à la bonne place) dans le tableau qui est alors trié suivant l'ordre croissant. Le tableau est modifié et la fonction ne renvoie rien.
Exemple
>>> t = [8, 5, 9, 3, 8, 2, 7, 1, 5]
>>> tri(t)
>>> t
[1, 2, 3, 5, 5, 7, 8, 8, 9]
###(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 beqên,4évi[3mo5_tLxR;PhkMlpwf(: cg.a=ryù0S6]-u/72)s1d 050#0c0r0K0k0A0Z0G0H0A0K0Z0Z0L010r0k0B010406050Z0U0n0n0K0M0N040Q0o0A0U0_0o0f0G020K0n0B0v0G0u0c130M0d0U0c0Z050V101214160~0B04051B1u1E0V1B0~0#0k0j0.0:0=0@0x0k0I0x0A1S0x0r0|050)0b0A0c1N0;0?011R1T1V1T0r1#1%1Z0r0M1C0r0x0.190Z0B0K0f0@0X011)1P010D0+0c0f1h0c1Z1 21261+291%2c0n2e040a0G0w0M0o0B0o0Z0k1c1e0%1}0M0M0c0H2z1u2g0f1C0V1{2L1^1`1_1!0#2i0@1V0f2b2w1Z1K1M0/1*2V0k2X0f0o2#1Z0B2E1C2J2L2?0 201e2%272,0M130A0|0!2I2`0}2_2h2|1+2~300|0X3421362J2U013b0K31040m3f2K0~3i390@3l3n0h3q3h2`3j3w0|0p3z3s3B3u3k0o2 3m0|0R3G372{1O3a3L3c040W3z1F2;1u2#2O0#1`2T3J0H2-2o0$1L1C2:0c2=353Z3-0%3^383T0@0y0|0%0D3Z3t3 010C0|0G453I470f0D0|1^0k4c3~2(010{040E4k3S4m0f4h0K0b4r3j4o0Y0F3G0G4E4b464t0|0f3z4G4d4m0o0|0L4L3R3C0b0|2l4y3J4o4q1v3_4H2}4v4x4$3g4T4Z0|0Y4D4F4.4e0|0B2a4S4(1+4P044R4,2K4M4l274o0l0S4=4E4@4m41040D3L4|4N4)044j5204544s270o495l4K5n5p4U0|0M210I0c4Y474!5E4I045v2^4}0@4A4C5n064F5S5x3J4u5u0Z0c0M2H5n5c560|4#5L5j3a4*5H5(040l5/5-5l5?5N0|0S0g5i555@4`1%5_4n4:5a5U475e5g0M5~5q5@5m2?674O5t2*6c5y045A0f5C635G5$5M3k4J6r4:5P2?5R5T5b6u5W1#6x5;635W6f4%5,5`04595w5%4~4Q6l5V4_4{6t6N014 0J6J4_2u6H0E4;5Q1u3{3@3!6;0V3%1u0r3)6_2R2M4w1%2L3%1A3}6d0@2E0n0q0D0K0y0c0q0x0m0|1m1o1q1s0G6z3_1H361B0s0K1}1i1%0t2y0i0G0#0U0G4i0G1s0r0G0:0G0n0e2n0G7k0.0c0A1%7A7C7E2*5Y5!0k1d2i0k7P0E2W0i0*2E7A210-7T2n0+1%0U0M7A7l0H0;0g7O0U0K0#5A0_7P0#7/7I1(4`7-0%0-7|0-0(7F1e0n0o0N2b2X0Y6%7p730z0*0-0K0j2F880G2:0o0I5A121(0#1d0f7z860f7:7t3-2D2F2z7~7T8a8F7{0;7F0Z7H0H7R0U0k0G0o0O880-0i0A0i2n0f0r0-7B7D6 0c0K7C2*2y0k3m0G0Z1d7H6o0I0i0-101L217H0A003L821(0H2t0k0=9c0J0G060Q8(7#930U0x0*0r1(2E1^0o0U8w7_1%0-7L2n8d8X7P8#0U0t7U7D0M8(7X5Z2z9p397%1r7~7#0B0c1b0G0i9j0k7-7J5g0f2G7!1e056:044i6/3.040*8L0k5P1I3:2$471-1U1W1Y743j2k2b2d0|2q0Q9,0B7H0w0N1{1d3Z3?742@3_9_6S40420c446Z5 0@5t4baB753k4g9`9S6+6(9`4w6H4B66aw6v5J6V474 516gaT0f4V044XaG4z5)aN6Ga*4/046-6A5Sa#6X626R6uaYaW4m576Qa?4?6u695ha{6!6Ka~5r6j5K356h2}a%965Da/5Fa,bk5Ibd4-a|0|0T630n0k326H5}b7aC6#bsbubw0433bn5:bza!6ubv0|0PaQ66a@6E0|9U7ZapbI1+6s5+bB6FaPbY6O5=b)aU6Lbq6!4o5|ba606Yb#aH4AaSb40|6ab?3vbUc06#bcc3a$5z5Bbjb_a+4paNbp2KaT5ObRb3b85.b,57aNb.cg6ub;c3a}bAaH5W61ca6MbB6$aN2v0B6+a=350~0Vav1H3#6@3;cK0%0)0+0Z04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)