Aller au contenu

Tri par tas⚓︎

Avertissement

Pour faire cet exercice, il est nécessaire d'avoir fait l'exercice de découverte de la structure de tas-min avec la fonction est_tas_min. Ou au moins, savoir ce qu'est la structure de tas.

Le tri par tas utilise la même stratégie que le tri par sélection : on extrait la valeur minimale, de manière répétitive, qui reste dans les données. Cette valeur est ajoutée à la fin de la liste triée en construction. La seule différence, c'est que le tri par tas utilise une structure efficace pour faire cela : un tas.

On utilisera, dans cet exercice, une implémentation de tas-min avec la bibliothèque standard de Python.

🐍 Script Python
from heapq import heappush, heappop

class TasMin:
    def __init__(self):
        self.donnees = []

    def est_vide(self):
        return self.donnees == []

    def ajoute(self, element):
        heappush(self.donnees, element)

    def extrait_min(self):
        mini = heappop(self.donnees)
        return mini

Exemple d'utilisation

🐍 Console Python
>>> nombres = TasMin()
>>> nombres.est_vide()
True
>>> nombres.ajoute(7)
>>> nombres.est_vide()
False
>>> nombres.ajoute(4)
>>> nombres.ajoute(9)
>>> nombres.extrait_min()
4
>>> nombres.extrait_min()
7
>>> nombres.est_vide()
False
>>> nombres.extrait_min()
9
>>> nombres.est_vide()
True

L'objectif de l'exercice est d'implémenter une fonction tri_par_tas qui prend en paramètre une liste d'éléments comparables entre eux et qui renvoie cette liste triée.

Contrainte

Il est interdit d'utiliser les méthodes natives sort et sorted. Vous devez utiliser la classe TasMin construite avec l'aide de la bibliothèque standard de Python. Dans un autre exercice, vous aurez à construire cette classe sans la bibliothèque standard.

Exemples

>>> tri_par_tas([55, 42, 12, 73])
[12, 42, 55, 73]
>>> tri_par_tas(['bac', 'a', 'abc', 'b'])
['a', 'abc', 'b', 'bac']
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(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
Évaluations restantes : 10/10
.128013:LpM(40^ed3; 1jEo5_An)h]6,qc[yuvà8i2xms7=wlSatf9ORrg.TéPkbè/050k0j0U0T0J0R0N0n0C0R0T0N0N0P010U0J0d010406050N0F0M0M0T0Z0E040S0r0R0F100r0v0n020T0M0d0m0n0Y0j1a0Z0B0F0j0N050,17191b1d150d041B1I051L0,1L1N1I150k0J0G0^0`0|0~0x0J0!0x0R1#0x0U13050:0*0R0j1W0{0}011!1$1(1$0U1.1:1,0U0*0r0k1d1-0Z1J0U0x0^1g0N0d0T0v0~0K011=1Y010V0=0j0v1o0j1,2d2f2k1@2n1:2q0M2s040a0n0(0Z0r0d0r0N0J1j1l0.2b0Z0Z0j0C2N1B2u0v1J0,292Z0U2726280k2w0~1(0v2p2K1,1T1V0_1?2-0J2/0v231U1,0d2S1J2X2Z34162e1l2^2l2}0Z1a0R130n0o2W3814372v3a1@3c3e3g0K3j2f3l2X2,013q0T3f040n0l3u2Y153x3o0~3A3C0n0g3G3w383y3M3g0s3Q3I3S3K3z0r3d3B3g0z3X3m391X3p3$3r3D0O3+3J3.3L3:3(3D0I3@3Z3_3#3%3N0W3 3n413U040o0h463-2_423;0o3i1C3k3Y474f490o3t4k3v4m4e3b3{3C0o3F4s3H3,3T4x130o3P4B3R4n4w434G3W4J4u4E4N4a3*4Q4D3!4p3?4W3^4o4F4a3~4#404%4T0o454+4L3/4T0K4c4;4v4?3;0K4j344R4Y4(0K4r504X48534A564$4M4}4I5b4,5d3|0K4P5g4=3`4@4V5m4{5o4}4!5r4S4}4*5w524@4:5A584T0l4_5E4-3;0l4 4l575K3|0l555O5c4|5R5a3k1K321B2?2$0k2*3y0C232C0-1U1J310j335Z4J055,0.5@5n010)0v130V2H0M3Q5P2l0Q3g665V3L61040x0j0T0d0B6b5h1@693D6l5~60130J1p3$0U3Q0n673p136g6i0d0F0N0x6q5s0112040A6y6A3L6C6h0d2J0d3X51410)133o6J3y6o6z5_6c3z0C130$0{0e2{6%3!6M0b3X0n6|6z6,6!040.0V6@416)744f0V0M130t0t2{2M7c772l6M0f7h1@0*6M0N0j0R736+6m0~6M0w6`4Q6}7A6~7u017n137p7r7l0~0r130#7J3z130k1k2/1z6P6,7L040P7V7D6M0D0y6X7A6Q5 7Q0j7s366,767t5~0v0V131z0U0t0G0J0.7O7j7O7F047H7/5Z6,7w7y507B6}7+702S0U0F0Z0v7!5~84867O7X7N7?6K6e7R0v7T1A4J7C5~7X0P7Z8A7+7$7(4Q067*6 7-873v7+7=7:7D7^130T0p0r1i0j81137k8t3y8o7q8P2Y8H136O8G6,6e7q1u2p6x8)6^137x6{8d8B8u6S6E6G6I8|4182984f8+7I9b2l8r7O8v7S0j7U9f1@6M8;34923T7`1:2B0v8{8T5~7w7)8e8N717.7O8S888U7_040j0L2%0;7|0M6?9n7v8%837o8,8$048 7z917+6e9S0v0J8m6K8D9.9t6f6T6V9!8(9z6K9d8-5}9/7M9i7Q9k9m9{3y9B9%8d8f138h8j8l8=8U139+9-8K6Y4f70729H6a9U3z9L2%0J0t2e0Z0t0:8za68}049`9J7@130G3B0j8jaCaH6K8a906|9)13aB9;3!9:agaI046:0N6=afaD998%0waS9s3!700V3$aX48130La^4f0r6o9T9raU04aK1:aN9!8b4l91a:a_04aWas9has6e8X8Z0U8#as9aa+4oa`9!a.a9bbbq042S170R0:9y3kbv9g138Fb189137%a/ab040Q1!1:a|9g6o2}bC3vbE6Bbd0{8qa1bh7`0N7|7~80bna-b84tbab2by0FbA0TbW8.7Wb%bp3b8W6U2p0k9_a2b!aO8Qb}048sb bZ9N9P7f9+9_0wbt8c9D7D8g0/aebSbZb@b_b{1406cy7+0C0o13030nblb*c83Ham2l701?0j0ZcwbY6Rbd0ZawayaAb#b.aF0D7O9S130s5laPa78:cs0~c%040g5Tc97#c-a!6Kc:4q9!9qbD7+c:0O5Yc@9A130ycld0ca8Ec.6LbKc$0J4Gc?b|c^6Nddc:c=c~dndh04c)dqc`3yd2d4dkd6048J50cK1@cM0|cOcQb2avax1bcXcI9 c,c!7O0NcC04000*0T0C00dvbI7DdV13000Td$cZc bX7+d*dX0T0*d#d%dad)dWdYd.cd9VdCd9d;dbbHd|dBc#asd?d,e0c+aEd:2YcR01ecd^d`d/ddec0*eed5aQc_d(5~eqd!esdAeudC3+0,5{5?5!eH0,5%1B0U5)eM2(2!22242$d^1:2Z5%1HdR3!2S0M0t0V0T0)0j0t0x0l131t1v1x1z0nb:8.1O3l1I0(8Z0Z0n0F1laB0n2P0:0=1:ej1b2M0x1abl0L13090f0v09e42Y8;1R05b^3l1(040R002{7pcP0J1k0n0Tf139bk0n2pfacU29fe9Nfh0f09fe0x0C3B0n0Xfj0wfl660,ft15ftfvcf0Zd!2Nf50F0naj0M18fCfE2b1ifH1l7+fbfLb`fN04fifQb`fSfUfW0vfYfm2Zf$1BfreZ0ufx0J0nf95,f`0k00f2cFcU0naycF0{f5gpf3eV6hf/f60;0Rf9f}fKfdg0fgg2fjfZ8A7{f{fJfcfMgLg3fRfT0RfVgN0R0r0!fXga3Q0A0n1xgjgQf92Bf8aMf00N2f0@5,8x0;0|2f0C1;310%3BgA0n17f01:0@8w0v0%1z8sfp1I0q1l31b`0Je?g,0=fH0L0Jb*1;gq0T1i2Sgrgj0d1h0@f+0d7 0jg,f2hn1y9w0U0n0Hf^e)2Ug@f:b^10hC0JfT100V2b0vb*2fhO310+0@1r5`5-04g.0C0)0N6w1BeG3DgQ2p7~2H2OaM0L0na?htgthD0nhFhHhg3l1/0rh@1x0rble|040ce@av0@2L1pha0n0fgufxdJfA0vg,gu0N0%1:2Uizg,hQ0*b^ha0wh71khO2z0U0@fI5,1p1bg~fB1r0=iqiPgRgHgTgKfOg429gYg!0v0i0Kg*4Jid150,ifih0Fij5?i`0.f70?04.