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']

Évaluations restantes : 10/10

.128013s3_8èuf^vy n7aS1me(P24:jtwi][hE)6Oo;bcdgM/T0làqAp.rL,=k95Rxé050N0s0z0o0B0T0b0l0M0T0o0b0b0$010z0B0X010406050b0g0r0r0o0Z0k040p0J0T0g100J0m0l020o0r0X0K0l0*0s1a0Z0V0g0s0b050Q17191b1d150X041B1I051L0Q1L1N1I150N0B0j0^0`0|0~0E0B0O0E0T1#0E0z13050:0L0T0s1W0{0}011!1$1(1$0z1.1:1,0z0L0J0N1d1-0Z1J0z0E0^1g0b0X0o0m0~0v011=1Y010h0=0s0m1o0s1,2d2f2k1@2n1:2q0r2s040a0l0u0Z0J0X0J0b0B1j1l0.2b0Z0Z0s0M2N1B2u0m1J0Q292Z0z2726280N2w0~1(0m2p2K1,1T1V0_1?2-0B2/0m231U1,0X2S1J2X2Z34162e1l2^2l2}0Z1a0T130l0q2W3814372v3a1@3c3e3g0v3j2f3l2X2,013q0o3f040l0c3u2Y153x3o0~3A3C0l0w3G3w383y3M3g0)3Q3I3S3K3z0J3d3B3g0H3X3m391X3p3$3r3D0n3+3J3.3L3:3(3D0e3@3Z3_3#3%3N0(3 3n413U040q0S463-2_423;0q3i1C3k3Y474f490q3t4k3v4m4e3b3{3C0q3F4s3H3,3T4x130q3P4B3R4n4w434G3W4J4u4E4N4a3*4Q4D3!4p3?4W3^4o4F4a3~4#404%4T0q454+4L3/4T0v4c4;4v4?3;0v4j344R4Y4(0v4r504X48534A564$4M4}4I5b4,5d3|0v4P5g4=3`4@4V5m4{5o4}4!5r4S4}4*5w524@4:5A584T0c4_5E4-3;0c4 4l575K3|0c555O5c4|5R5a3k1K321B2?2$0N2*3y0M232C0-1U1J310s335Z4J055,0.5@5n010%0m130h2H0r3Q5P2l0A3g665V3L61040E0s0o0X0V6b5h1@693D6l5~60130B1p3$0z3Q0l673p136g6i0X0g0b0E6q5s0112040#6y6A3L6C6h0X2J0X3X51410%133o6J3y6o6z5_6c3z0M130R0{0P2{6%3!6M0x3X0l6|6z6,6!040.0h6@416)744f0h0r130d0d2{2M7c772l6M0t7h1@0L6M0b0s0T736+6m0~6M0G6`4Q6}7A6~7u017n137p7r7l0~0J130Y7J3z130N1k2/1z6P6,7L040$7V7D6M0D0C6X7A6Q5 7Q0s7s366,767t5~0m0h131z0z0d0j0B0.7O7j7O7F047H7/5Z6,7w7y507B6}7+702S0z0g0Z0m7!5~84867O7X7N7?6K6e7R0m7T1A4J7C5~7X0$7Z8A7+7$7(4Q067*6 7-873v7+7=7:7D7^130o0y0J1i0s81137k8t3y8o7q8P2Y8H136O8G6,6e7q1u2p6x8)6^137x6{8d8B8u6S6E6G6I8|4182984f8+7I9b2l8r7O8v7S0s7U9f1@6M8;34923T7`1:2B0m8{8T5~7w7)8e8N717.7O8S888U7_040s0+2%0;7|0r6?9n7v8%837o8,8$048 7z917+6e9S0m0B8m6K8D9.9t6f6T6V9!8(9z6K9d8-5}9/7M9i7Q9k9m9{3y9B9%8d8f138h8j8l8=8U139+9-8K6Y4f70729H6a9U3z9L2%0B0d2e0Z0d0:8za68}049`9J7@130j3B0s8jaCaH6K8a906|9)13aB9;3!9:agaI046:0b6=afaD998%0GaS9s3!700h3$aX48130+a^4f0J6o9T9raU04aK1:aN9!8b4l91a:a_04aWas9has6e8X8Z0z8#as9aa+4oa`9!a.a9bbbq042S170T0:9y3kbv9g138Fb189137%a/ab040A1!1:a|9g6o2}bC3vbE6Bbd0{8qa1bh7`0b7|7~80bna-b84tbab2by0gbA0obW8.7Wb%bp3b8W6U2p0N9_a2b!aO8Qb}048sb bZ9N9P7f9+9_0Gbt8c9D7D8g0/aebSbZb@b_b{1406cy7+0M0q13030lblb*c83Ham2l701?0s0ZcwbY6Rbd0ZawayaAb#b.aF0D7O9S130)5laPa78:cs0~c%040w5Tc97#c-a!6Kc:4q9!9qbD7+c:0n5Yc@9A130Ccld0ca8Ec.6LbKc$0B4Gc?b|c^6Nddc:c=c~dndh04c)dqc`3yd2d4dkd6048J50cK1@cM0|cOcQb2avax1bcXcI9 c,c!7O0bcC04000L0o0M00dvbI7DdV13000od$cZc bX7+d*dX0o0Ld#d%dad)dWdYd.cd9VdCd9d;dbbHd|dBc#asd?d,e0c+aEd:2YcR01ecd^d`d/ddec0Leed5aQc_d(5~eqd!esdAeudC3+0Q5{5?5!eH0Q5%1B0z5)eM2(2!22242$d^1:2Z5%1HdR3!2S0r0d0h0o0%0s0d0E0c131t1v1x1z0lb:8.1O3l1I0u8Z0Z0l0g1laB0l2P0:0=1:ej1b2M0E1abl0+13090t0m09e42Y8;1R05b^3l1(040T002{7pcP0B1k0l0of139bk0l2pfacU29fe9Nfh0t09fe0E0M3B0l0Ifj0Gfl660Qft15ftfvcf0Zd!2Nf50g0laj0r18fCfE2b1ifH1l7+fbfLb`fN04fifQb`fSfUfW0mfYfm2Zf$1BfreZ0Wfx0B0lf95,f`0N00f2cFcU0laycF0{f5gpf3eV6hf/f60;0Tf9f}fKfdg0fgg2fjfZ8A7{f{fJfcfMgLg3fRfT0TfVgN0T0J0OfXga3Q0#0l1xgjgQf92Bf8aMf00b2f0@5,8x0;0|2f0M1;310,3BgA0l17f01:0@8w0m0,1z8sfp1I0F1l31b`0Be?g,0=fH0+0Bb*1;gq0o1i2Sgrgj0X1h0@f+0X7 0sg,f2hn1y9w0z0l0Uf^e)2Ug@f:b^10hC0BfT100h2b0mb*2fhO310f0@1r5`5-04g.0M0%0b6w1BeG3DgQ2p7~2H2OaM0+0la?htgthD0lhFhHhg3l1/0Jh@1x0Jble|040!e@av0@2L1pha0l0tgufxdJfA0mg,gu0b0,1:2Uizg,hQ0Lb^ha0Gh71khO2z0z0@fI5,1p1bg~fB1r0=iqiPgRgHgTgKfOg429gYg!0m0i0vg*4Jid150Qifih0gij5?i`0.f70?04.