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 wl7;.à,a/: ALqr0npmx3_6kséRhf45(vtb=ocgeS19)2iPd8uy 050W0O0I0i0U0c0z0l0M0c0i0z0z0K010I0U0s010406050z0Y0t0t0i0p0Z040P0L0c0Y0@0L0r0l020i0t0s0e0l0B0O110p0o0Y0O0z050j0~1012140|0s041s1z051C0j1C1E1z0|0W0U0H0,0.0:0=0C0U0N0C0c1S0C0I0`050%0J0c0O1N0/0;011R1T1V1T0I1#1%1Z0I0J0L0W141!0p1A0I0C0,170z0s0i0r0=0T011)1P010D0)0O0r1f0O1Z24262b1+2e1%2h0t2j040a0l0V0p0L0s0L0z0U1a1c0#220p0p0O0M2E1s2l0r1A0j202Q0I1~1}1 0W2n0=1V0r2g2B1Z1K1M0-1*2!0U2$0r1`1L1Z0s2J1A2O2Q2{0}251c2,2c2;0p110c0`0l0Q2N2 0{2~2m311+3335370T3a263c2O2Z013h0i36040l0v3l2P0|3o3f0=3r3t0l0E3x3n2 3p3D370F3H3z3J3B3q0L343s370x3O3d301O3g3T3i3u0d3Y3A3#3C3%3V3u0X3+3Q3-3S3U3E0R3?3e3^3L040Q0q3}3!2-3_3(0Q391t3b1B2_1s2*2T0W2X3p0M1`2t0!1L1A2^0O2`4c4b3m054l0#4t3~460y0`0#0D3H3Z3p0b374H3,460r0D0`2/0z0O0p2M4v2P4I3R0_040G4M3@4O0`0u4(4B2c4#0h3H0l4Z3 0`0s2f4-454/0`0S0k3O0l534?4N2c4D040U4G4X3u4@4O0J0`2q4|3p4#4%5c5e324_4{5n561+4#0S4=5o1+0L0`0K0K5x5t0=0t0U0`435s4)4~04515c06545S555M3g5q1%5j3R5A040f5Z4^040i0s0s2g0W5(465l5:5p044,5L4.5u4 52545y0=580O0*0O5?5|5O5~5T5U5{3C0`0Z5E5V0=5#5D5c6b4}5W044`5Y5`6n6i0`5%6s3K4_2z660=5l5w5Q6a536001585a6g6c3q4+6M6t015#020N0I0e6Q6y046f6x4!0`5P2{5R6G5S6I0r4R0r4T4V0U1b6B015=6$5)5_2}5F6`0`4;6l6.5X656|5;5}6F6,5 706/6p5r6 6h6S6v6_7f5+5-0r5/785N5m7i6N7f6#7v6R5v695T6I62646_4#6)3b6+7c6m6Z6q777z3p5#6w7R3R7n5,5.7H0`7u4c7e6e7!046E6*7M6H7(7g6r7V3^7T7m0`7o7Z7s677$4w7:6~7%7j7B5Q1s4y4s4d890j4g1s0I4i8e2V2R1_1{2T0i1$8b4g1y4A6R2J0t0w0D0i0y0O0w0C0v0`1k1m1o1q0l7J4w1F3c1z0m1;2g2E0l0g0l0r00190)0U6=0l0i0H2K0l0.0l7P0l8H8*8I0t0A204m0+4x4m5*7Y7q878{0h4?886p6A0j930l0$8*0i0l0D1b2L6@1c8`4z5i968{0f0l0n8X0@1V0z0i8S0W002/1K0M1(8W1q0I8,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 wl7;.,a/: Lq]r0ùMnpmx3_6kséRhf-45(vtbê=ocgeS1)[2iPduy 050Z0R0K0h0X0c0A0k0P0c0h0A0A0N010K0X0t010406050A0!0u0u0h0o0#040S0O0c0!0_0O0s0k020h0u0t0e0k0C0R130o0m0!0R0A050i101214160~0t041u1B051E0i1E1G1B0~0Z0X0J0.0:0=0@0D0X0Q0D0c1U0D0K0|050)0L0c0R1P0;0?011T1V1X1V0K1%1)1#0K0L0O0Z161$0o1C0K0D0.190A0t0h0s0@0W011+1R010E0+0R0s1h0R1#26282d1-2g1)2j0u2l040a0k0Y0o0O0t0O0A0X1c1e0%240o0o0R0P2G1u2n0s1C0i222S0K201 210Z2p0@1X0s2i2D1#1M1O0/1,2$0X2(0s1|1N1#0t2L1C2Q2S2}0 271e2.2e2?0o130c0|0T2P310}302o331-35370|0W3b283d2Q2#013i0h38040w3m2R0~3p3g0@3s3u0G3x3o313q3D0|0H3G3z3I3B3r0O363t0|0y3N3e321Q3h3S3j040d3G1D2{1u2,2V0Z2Z3q0P1|2v0$1N1C2`0R2|3c3*3?0%3~3f3!0@0z0|0%0E3*3A45010b0|0k4b3P4d0s0E0|2W0X4i442/010{040I4q3Z4s0s4n0h0L4x3q4u0U0j3N0k4K4h4c4z0|0s3G4M4j4s0O0|0N4R3Y3J0L0|2s4E3Q4u4w1v3 4N344B4D4,3n4Z4)0|0U4J4L4@4k0|0t2h4Y4.1-4V044X4=2R4S4r2e4u0V0n4{4K4}4s47040E3S524T4/044p58045a4y2e0O4f5r4Q5t5v4!0|0o280Q0R4(4d4*5K4O045B2 530@4G4I5t064L5Y5D3Q4A5A0A0R0o2O5t5i5c0|4+5R5p3h4:5N5.040V5^5?5r5|5T0|0n0g5o5b5}501)5 4t4_5g5!4d5k5m0o645w5}5s2}6d4U5z2;6i5E045G0s5I695M5,5S3r4P6x4_5V2}5X5Z5h6A5$1%6D5`695$6l4-5=60045f5C5-544W6r5#4 516z6T01550f6P4 2B6N0I4`5W1u413}3+6`0i3.1u0K3:6 2X2T1{1}2V4C1)2S3.1A436j0@2L0u0x0E0h0z0R0x0D0w0|1m1o1q1s0k6F3 1H3d1B0l0h241i1)0v2F0B0k0Z0!0k4o0k1s0K0k0:0k0u0M2u0k7t0.0R0c1)7J7L7N2;5(5*0X1d2p0X7Y0I2%0B0*2L7J280-7$2u0+1)0!0o7J7u0P0;0g7X0!0h0Z5G0_7Y0Z7{7R1*507_0%0-850-0(7O1e0u0O0#2i2(0U6-7y7c0r0*0-0h0J2M8h0k2`0O0Q5G121*0Z1d0s7I8f0s7|7C3?2K2M2G877$8j8O840;7O0A7Q0P7!0!0X0k0O0q8h0-0B0c0B2u0s0K0-7K7M780R0h7L2;2F0X3t0k0A1d7Q6u0Q0B0-101N287Q0c003S8b1*0P2A0X0=9l0f0k060S8;7.9c0!0D0*0K1*2L2W0O0!8F821)0-7U2u8m8*7Y8.0!0v7%7M0o8;7*5)2G9y3g7:1r877.0t0R1b0k0B9s0X7_7S5m0s2N7-1e056_044o6^3@040*8U0X5V1K3_2-4d1/1W1Y1!7d3q2r2i2k0|2x0S9^0t7Q0Y0#221d3*3|7d2~3 a26Y46480R4a6)650@5z4haK7e3r4ma39#6;6.a34C6N4H6caF6B5P6#4d55576ma$0s4#044%aP4F5/aW6Ma?4^046?6G5Ya.6%686X6Aa+a)4s5d6Wa 4|6A6f5nb46*6Qb75x6p5Q3c6n34a:9f5Ja{5La^bt5Obm4?b50|0F690u0X396N63bgaL6+bBbDbF043abw5_bIa-6AbE0|0paZ6cb06K0|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,aW2C0t6;a~3c0~0iaE1H3,6}3`cT0%0)0+0A04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)