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 ,:ag)LR1ikn9/àSAé=vmsuhb.84;y7ex62odt c0(wr5_P3qplf 050K0F0L0d0j0Y0v0M0N0Y0d0v0v0s010L0j0X010406050v0w0u0u0d0R0D040p0J0Y0w0@0J0l0M020d0u0X0C0M0h0F110R0W0w0F0v050n0~1012140|0X041s1z051C0n1C1E1z0|0K0j0t0,0.0:0=0x0j0e0x0Y1S0x0L0`050%0y0Y0F1N0/0;011R1T1V1T0L1#1%1Z0L0y0J0K141!0R1A0L0x0,170v0X0d0l0=0I011)1P010Z0)0F0l1f0F1Z24262b1+2e1%2h0u2j040a0M0U0R0J0X0J0v0j1a1c0#220R0R0F0N2E1s2l0l1A0n202Q0L1~1}1 0K2n0=1V0l2g2B1Z1K1M0-1*2!0j2$0l1`1L1Z0X2J1A2O2Q2{0}251c2,2c2;0R110Y0`0M0i2N2 0{2~2m311+3335370I3a263c2O2Z013h0d36040M0V3l2P0|3o3f0=3r3t0M0B3x3n2 3p3D370S3H3z3J3B3q0J343s370H3O3d301O3g3T3i3u0E3Y3A3#3C3%3V3u0A3+3Q3-3S3U3E0m3?3e3^3L040i0O3}3!2-3_3(0i391t3b1B2_1s2*2T0K2X3p0N1`2t0!1L1A2^0F2`4c4b3m054l0#4t3~460k0`0#0Z3H3Z3p0Q374H3,460l0Z0`2/0v0F0R2M4v2P4I3R0_040P4M3@4O0`0G4(4B2c4#0b3H0M4Z3 0`0X2f4-454/0`0f0c3O0M534?4N2c4D040j4G4X3u4@4O0y0`2q4|3p4#4%5c5e324_4{5n561+4#0f4=5o1+0J0`0s0s5x5t0=0u0j0`435s4)4~04515c06545S555M3g5q1%5j3R5A040z5Z4^040d0X0X2g0K5(465l5:5p044,5L4.5u4 52545y0=580F0*0F5?5|5O5~5T5U5{3C0`0D5E5V0=5#5D5c6b4}5W044`5Y5`6n6i0`5%6s3K4_2z660=5l5w5Q6a536001585a6g6c3q4+6M6t015#020e0L0C6Q6y046f6x4!0`5P2{5R6G5S6I0l4R0l4T4V0j1b6B015=6$5)5_2}5F6`0`4;6l6.5X656|5;5}6F6,5 706/6p5r6 6h6S6v6_7f5+5-0l5/785N5m7i6N7f6#7v6R5v695T6I62646_4#6)3b6+7c6m6Z6q777z3p5#6w7R3R7n5,5.7H0`7u4c7e6e7!046E6*7M6H7(7g6r7V3^7T7m0`7o7Z7s677$4w7:6~7%7j7B5Q1s4y4s4d890n4g1s0L4i8e2V2R1_1{2T0d1$8b4g1y4A6R2J0u0T0Z0d0k0F0T0x0V0`1k1m1o1q0M7J4w1F3c1z0q1;2g2E0M0o0M0l00190)0j6=0M0d0t2K0M0.0M7P0M8H8*8I0u0r204m0+4x4m5*7Y7q878{0b4?886p6A0n930M0$8*0d0M0Z1b2L6@1c8`4z5i968{0z0M0g8X0@1V0v0d8S0K002/1K0N1(8W1q0L8,0/8,2B2C8o6w1I4f0$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 :,êag)LR1iùkn/Sé=vmsuhb.4;y7e[x62o-dt cM(0w]r5_P3qplf 050K0D0L0e0k0!0u0M0N0!0e0u0u0r010L0k0Z010406050u0v0t0t0e0T0B040p0I0!0v0_0I0n0M020e0t0Z0A0M0i0D130T0Y0v0D0u050o101214160~0Z041u1B051E0o1E1G1B0~0K0k0s0.0:0=0@0w0k0f0w0!1U0w0L0|050)0x0!0D1P0;0?011T1V1X1V0L1%1)1#0L0x0I0K161$0T1C0L0w0.190u0Z0e0n0@0H011+1R010#0+0D0n1h0D1#26282d1-2g1)2j0t2l040a0M0W0T0I0Z0I0u0k1c1e0%240T0T0D0N2G1u2n0n1C0o222S0L201 210K2p0@1X0n2i2D1#1M1O0/1,2$0k2(0n1|1N1#0Z2L1C2Q2S2}0 271e2.2e2?0T130!0|0j2P310}302o331-35370|0H3b283d2Q2#013i0e38040X3m2R0~3p3g0@3s3u0z3x3o313q3D0|0U3G3z3I3B3r0I363t0|0G3N3e321Q3h3S3j040C3G1D2{1u2,2V0K2Z3q0N1|2v0$1N1C2`0D2|3c3*3?0%3~3f3!0@0m0|0%0#3*3A45010R0|0M4b3P4d0n0#0|2W0k4i442/010{040P4q3Z4s0n4n0e0x4x3q4u0g0b3N0M4K4h4c4z0|0n3G4M4j4s0I0|0r4R3Y3J0x0|2s4E3Q4u4w1v3 4N344B4D4,3n4Z4)0|0g4J4L4@4k0|0Z2h4Y4.1-4V044X4=2R4S4r2e4u0E0S4{4K4}4s47040#3S524T4/044p58045a4y2e0I4f5r4Q5t5v4!0|0T280f0D4(4d4*5K4O045B2 530@4G4I5t064L5Y5D3Q4A5A0u0D0T2O5t5i5c0|4+5R5p3h4:5N5.040E5^5?5r5|5T0|0S0c5o5b5}501)5 4t4_5g5!4d5k5m0T645w5}5s2}6d4U5z2;6i5E045G0n5I695M5,5S3r4P6x4_5V2}5X5Z5h6A5$1%6D5`695$6l4-5=60045f5C5-544W6r5#4 516z6T01550y6P4 2B6N0P4`5W1u413}3+6`0o3.1u0L3:6 2X2T1{1}2V4C1)2S3.1A436j0@2L0t0V0#0e0m0D0V0w0X0|1m1o1q1s0M6F3 1H3d1B0h0e241i1)0F2F0q0M0K0v0M4o0M1s0L0M0:0M0t0d2u0M7t0.0D0!1)7J7L7N2;5(5*0k1d2p0k7Y0P2%0q0*2L7J280-7$2u0+1)0v0T7J7u0N0;0c7X0v0e0K5G0_7Y0K7{7R1*507_0%0-850-0(7O1e0t0I0B2i2(0g6-7y7c0O0*0-0e0s2M8h0M2`0I0f5G121*0K1d0n7I8f0n7|7C3?2K2M2G877$8j8O840;7O0u7Q0N7!0v0k0M0I0l8h0-0q0!0q2u0n0L0-7K7M780D0e7L2;2F0k3t0M0u1d7Q6u0f0q0-101N287Q0!003S8b1*0N2A0k0=9l0y0M060p8;7.9c0v0w0*0L1*2L2W0I0v8F821)0-7U2u8m8*7Y8.0v0F7%7M0T8;7*5)2G9y3g7:1r877.0Z0D1b0M0q9s0k7_7S5m0n2N7-1e056_044o6^3@040*8U0k5V1K3_2-4d1/1W1Y1!7d3q2r2i2k0|2x0p9^0Z7Q0W0B221d3*3|7d2~3 a26Y46480D4a6)650@5z4haK7e3r4ma39#6;6.a34C6N4H6caF6B5P6#4d55576ma$0n4#044%aP4F5/aW6Ma?4^046?6G5Ya.6%686X6Aa+a)4s5d6Wa 4|6A6f5nb46*6Qb75x6p5Q3c6n34a:9f5Ja{5La^bt5Obm4?b50|0J690t0k396N63bgaL6+bBbDbF043abw5_bIa-6AbE0|0QaZ6cb06K0|9%7,aybR1-6y5;bK6LaYb+6U5{b=a%6Rbz6*4u62bj666(b.aQ4Ga#bd0|6gb 3Cb%c96+blcca/5F5Hbsc2a@4vaWby2Ra$5Ub!bcbh5@b^5daWb`cp6Ab}ccb6bJaQ5$67cj6SbK6,aW2C0Z6;a~3c0~0oaE1H3,6}3`cT0%0)0+0u04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)