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 nLximwgyk02P;o, 5à6uRal84t/sbrvce.3)Afh:1S=9é7_dqp( 050W0H0A0w0e0x0C0q0G0x0w0C0C0R010A0e0Y010406050C0u0f0f0w0E0i040Q0o0x0u0@0o0b0q020w0f0Y0n0q0v0H110E0X0u0H0C050B0~1012140|0Y041s1z051C0B1C1E1z0|0W0e0F0,0.0:0=0N0e0h0N0x1S0N0A0`050%0D0x0H1N0/0;011R1T1V1T0A1#1%1Z0A0D0o0W141!0E1A0A0N0,170C0Y0w0b0=0l011)1P010M0)0H0b1f0H1Z24262b1+2e1%2h0f2j040a0q0m0E0o0Y0o0C0e1a1c0#220E0E0H0G2E1s2l0b1A0B202Q0A1~1}1 0W2n0=1V0b2g2B1Z1K1M0-1*2!0e2$0b1`1L1Z0Y2J1A2O2Q2{0}251c2,2c2;0E110x0`0q0P2N2 0{2~2m311+3335370l3a263c2O2Z013h0w36040q0J3l2P0|3o3f0=3r3t0q0z3x3n2 3p3D370r3H3z3J3B3q0o343s370t3O3d301O3g3T3i3u0U3Y3A3#3C3%3V3u0y3+3Q3-3S3U3E0S3?3e3^3L040P0k3}3!2-3_3(0P391t3b1B2_1s2*2T0W2X3p0G1`2t0!1L1A2^0H2`4c4b3m054l0#4t3~460j0`0#0M3H3Z3p0g374H3,460b0M0`2/0C0H0E2M4v2P4I3R0_040Z4M3@4O0`0d4(4B2c4#0p3H0q4Z3 0`0Y2f4-454/0`0K0O3O0q534?4N2c4D040e4G4X3u4@4O0D0`2q4|3p4#4%5c5e324_4{5n561+4#0K4=5o1+0o0`0R0R5x5t0=0f0e0`435s4)4~04515c06545S555M3g5q1%5j3R5A040I5Z4^040w0Y0Y2g0W5(465l5:5p044,5L4.5u4 52545y0=580H0*0H5?5|5O5~5T5U5{3C0`0i5E5V0=5#5D5c6b4}5W044`5Y5`6n6i0`5%6s3K4_2z660=5l5w5Q6a536001585a6g6c3q4+6M6t015#020h0A0n6Q6y046f6x4!0`5P2{5R6G5S6I0b4R0b4T4V0e1b6B015=6$5)5_2}5F6`0`4;6l6.5X656|5;5}6F6,5 706/6p5r6 6h6S6v6_7f5+5-0b5/785N5m7i6N7f6#7v6R5v695T6I62646_4#6)3b6+7c6m6Z6q777z3p5#6w7R3R7n5,5.7H0`7u4c7e6e7!046E6*7M6H7(7g6r7V3^7T7m0`7o7Z7s677$4w7:6~7%7j7B5Q1s4y4s4d890B4g1s0A4i8e2V2R1_1{2T0w1$8b4g1y4A6R2J0f0V0M0w0j0H0V0N0J0`1k1m1o1q0q7J4w1F3c1z0L1;2g2E0q0s0q0b00190)0e6=0q0w0F2K0q0.0q7P0q8H8*8I0f0T204m0+4x4m5*7Y7q878{0p4?886p6A0B930q0$8*0w0q0M1b2L6@1c8`4z5i968{0I0q0c8X0@1V0C0w8S0W002/1K0G1(8W1q0A8,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 nLxiùmwgyk02P;o, 56]uRMal4t/sbr[vce.3)fh-:1S=êé7_dqp( 050Y0J0B0y0e0z0D0r0I0z0y0D0D0T010B0e0!010406050D0v0g0g0y0F0j040S0p0z0v0_0p0b0r020y0g0!0o0r0w0J130F0Z0v0J0D050C101214160~0!041u1B051E0C1E1G1B0~0Y0e0H0.0:0=0@0O0e0i0O0z1U0O0B0|050)0E0z0J1P0;0?011T1V1X1V0B1%1)1#0B0E0p0Y161$0F1C0B0O0.190D0!0y0b0@0m011+1R010N0+0J0b1h0J1#26282d1-2g1)2j0g2l040a0r0n0F0p0!0p0D0e1c1e0%240F0F0J0I2G1u2n0b1C0C222S0B201 210Y2p0@1X0b2i2D1#1M1O0/1,2$0e2(0b1|1N1#0!2L1C2Q2S2}0 271e2.2e2?0F130z0|0R2P310}302o331-35370|0m3b283d2Q2#013i0y38040L3m2R0~3p3g0@3s3u0A3x3o313q3D0|0s3G3z3I3B3r0p363t0|0t3N3e321Q3h3S3j040W3G1D2{1u2,2V0Y2Z3q0I1|2v0$1N1C2`0J2|3c3*3?0%3~3f3!0@0k0|0%0N3*3A45010h0|0r4b3P4d0b0N0|2W0e4i442/010{040#4q3Z4s0b4n0y0E4x3q4u0M0Q3N0r4K4h4c4z0|0b3G4M4j4s0p0|0T4R3Y3J0E0|2s4E3Q4u4w1v3 4N344B4D4,3n4Z4)0|0M4J4L4@4k0|0!2h4Y4.1-4V044X4=2R4S4r2e4u0G0u4{4K4}4s47040N3S524T4/044p58045a4y2e0p4f5r4Q5t5v4!0|0F280i0J4(4d4*5K4O045B2 530@4G4I5t064L5Y5D3Q4A5A0D0J0F2O5t5i5c0|4+5R5p3h4:5N5.040G5^5?5r5|5T0|0u0q5o5b5}501)5 4t4_5g5!4d5k5m0F645w5}5s2}6d4U5z2;6i5E045G0b5I695M5,5S3r4P6x4_5V2}5X5Z5h6A5$1%6D5`695$6l4-5=60045f5C5-544W6r5#4 516z6T01550K6P4 2B6N0#4`5W1u413}3+6`0C3.1u0B3:6 2X2T1{1}2V4C1)2S3.1A436j0@2L0g0X0N0y0k0J0X0O0L0|1m1o1q1s0r6F3 1H3d1B0c0y241i1)0d2F0V0r0Y0v0r4o0r1s0B0r0:0r0g0U2u0r7t0.0J0z1)7J7L7N2;5(5*0e1d2p0e7Y0#2%0V0*2L7J280-7$2u0+1)0v0F7J7u0I0;0q7X0v0y0Y5G0_7Y0Y7{7R1*507_0%0-850-0(7O1e0g0p0j2i2(0M6-7y7c0x0*0-0y0H2M8h0r2`0p0i5G121*0Y1d0b7I8f0b7|7C3?2K2M2G877$8j8O840;7O0D7Q0I7!0v0e0r0p0f8h0-0V0z0V2u0b0B0-7K7M780J0y7L2;2F0e3t0r0D1d7Q6u0i0V0-101N287Q0z003S8b1*0I2A0e0=9l0K0r060S8;7.9c0v0O0*0B1*2L2W0p0v8F821)0-7U2u8m8*7Y8.0v0d7%7M0F8;7*5)2G9y3g7:1r877.0!0J1b0r0V9s0e7_7S5m0b2N7-1e056_044o6^3@040*8U0e5V1K3_2-4d1/1W1Y1!7d3q2r2i2k0|2x0S9^0!7Q0n0j221d3*3|7d2~3 a26Y46480J4a6)650@5z4haK7e3r4ma39#6;6.a34C6N4H6caF6B5P6#4d55576ma$0b4#044%aP4F5/aW6Ma?4^046?6G5Ya.6%686X6Aa+a)4s5d6Wa 4|6A6f5nb46*6Qb75x6p5Q3c6n34a:9f5Ja{5La^bt5Obm4?b50|0P690g0e396N63bgaL6+bBbDbF043abw5_bIa-6AbE0|0laZ6cb06K0|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,aW2C0!6;a~3c0~0CaE1H3,6}3`cT0%0)0+0D04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)