Tri par dénombrement

On souhaite dans cet exercice trier des tableaux non vides de nombres entiers positifs ou nuls.

Pour ce faire on utilise l'algorithme du tri par dénombrement.

Les étapes sont les suivantes :

déterminer la valeur maximale dans le tableau,
regrouper dans un autre tableau le nombre d'apparitions de chaque valeur entre 0 et le maximum déterminé à l'étape précédente. Dans ce tableau d'effectifs, la valeur à l'indice i donnera le nombre d'apparitions de i dans le tableau initial,
parcourir le tableau des effectifs et ajouter autant de fois que nécessaire chaque indice dans le tableau de nombres triés.

Exemple

On souhaite trier le tableau nombres = [3, 3, 2, 0, 3, 0, 2, 0, 2, 3] :

La valeur maximale est 3
Le tableau des effectifs vaut :

🐍 Script Python

# indice     0  1  2  3
effectifs = [3, 0, 3, 4]

Le 3 à l'indice 2 signifie que le nombre 2 apparaît trois fois dans nombres.

On parcourt effectifs :
- à l'indice 0 on trouve la valeur 3 : on insère trois fois 0 dans le tableau nombres_tries,
- à l'indice 1 on trouve la valeur 0 : on n'effectue pas d'insertion,
- à l'indice 2 on trouve la valeur 3 : on insère trois fois 2 dans nombres_tries,
- à l'indice 3 on trouve la valeur 4 : on insère quatre fois 3 dans nombres_tries.
On obtient le tableau [0, 0, 0, 2, 2, 2, 3, 3, 3, 3].

Vous devez écrire quatre fonctions. Chaque question est indépendante.

Contrainte pour toutes les questions

On interdit d'utiliser dans toutes les questions la méthode de tri sort et la fonction de tri native sorted.

1. La fonction maximum

Écrire la fonction maximum qui prend en paramètre un tableau de nombres nombres et renvoie la valeur maximale dans celui-ci.

Contrainte

On interdit d'utiliser les fonctions natives max et min.

Évaluations restantes : 10/10

.128013beqn,4vèià3mo5_tLxR;Phklpwf(: cg.a=ry0DS6u/2)As1d050X0c0q0I0j0y0V0E0F0y0I0V0V0J010q0j0z010406050V0Q0m0m0I0K0L040O0n0y0Q0=0n0e0E020I0m0z0u0E0t0c0 0K0d0Q0c0V050R0|0~10120`0z04051x1q1A0R1x0`0X0j0h0*0,0.0:0w0j0G0w0y1O0w0q0^050#0b0y0c1J0-0/011N1P1R1P0q1X1Z1V0q0K1y0q0w0*150V0z0I0e0:0S011#1L010B0%0c0e1d0c1V1{1}221%251Z280m2a040a0E0v0K0n0z0n0V0j181a0Z1_0K0K0c0F2v1q2c0e1y0R1@2H1;1?1=1W0X2e0:1R0e272s1V1G1I0+1$2R0j2T0e0n2X1V0z2A1y2F2H2/0{1|1a2Z232(0K0 0y0^0W2E2?0_2=2d2^1%2`2|0^0S301}322F2Q01370I2}040l3b2G0`3e350:3h3j0g3m3d2?3f3s0^0o3v3o3x3q3g0n2{3i0^0P3v1B2-1q2X2K0X1?2P3F0F2)2k0Y1H1y2,0c2.313M3W0Z3(341K1%0x0^0Z0B3M3p3/0:0A0^0E3^3E3`3g0B0^0 0s0j0m0}3 3.2!010@040C4a2@410e0^2(0m0b2A1p1r3)3_4c4e0T0D3C0E4z3~4t2_440I463v4B404c0n0^0J4H334i4c0m0j0^0M4y4A4P3f3;040B3H4O4C364l0b4(4J230n3|042$4-4b4D044m4o1o4h3f4e4x4r3c064A554I4^3:0^0j3@522G574Q4_0e4,5d045f3f4L04020G0q0u4@5g4*04450j4~3F504W56564Y3F4k5x4F5z5k5m3F5o4N5M5G4j4+5D5N414!2A0q0Q0K0e5u3y4E4G5k0`0R3+3%3N5:0R3Q1q0q3S5^2N2I0I1Y5=3Q1w3-5v0:2A0m0p0B0I0x0c0p0w0l0^1i1k1m1o0E512;1D321x0r0I0E4$0e2C0j193~5/5J46480m1q6A0E1o0q2e0j6j6l0E6y2$2u0j3i0j0V1!1Z0E5y6D0E0k6z3X044V5.6(0E0z0Q6U6O1a1R6J0y00276V4n6X0Z0)0h3i0c5#0V0H1B6p040U1-272v0E0q0n170c4$6:0D6;6-726J6Q0=6T6V0K6#6%3,6*6G0F100E1Z0)4{4p0E0V196J7e0Q0)6~6H0e0=0c0K0)2r2t0=0B0)7f0E0e0Q0(756o620N1}0)7K0)7C0E0I177F7z0V0f7l7p6S1R7s6s6X6Z0}7;0h2B7B6s3$4S0i2A0E701Z5#0E0X0Q7d5~1Z7=7(1E3P0!0$0(04.

2. La fonction denombrement

Compléter la fonction denombrement qui prend en paramètres un tableau de nombres nombres et son maximum et renvoie un tableau d'entiers représentant les effectifs de chaque valeur.

Exemples

>>> nombres = [3, 3, 2, 0, 3, 0, 2, 0, 2, 3]
>>> denombrement(nombres, 3)
[3, 0, 3, 4]

Évaluations restantes : 10/10

.128013ben,4vi[3mo5txPhklpwf(: cga=ry0S]*u/2)s1+d050Q0c0n0B0h0s0N0y0z0s0B0N0N0C010n0h0t010406050N0J0k0k0B0D0E040G0l0s0J0+0l0d050K0=0@0_0{0:0t04051b141e0K1b0:0Q0h0g0Z0#0%0)0q0h0A0q0s1s0q0n0.050U0b0s0c1n0$0(011r1t1v1t0n1B1D1z0n0D1c0n0q0Z0~0N0t0B0d0)0L011F1p010v0W0c0d0B0k0c1z1Y1!1)1H1,1D1/1;0.0a0y0p0D0l0t0l0N0h110d0y0S1W0D0D0c0z29141@0d1c0K1U2m1R1T1S1A0Q1_0)1v0d1.261z1k1m0!1G2w0h2y0d0l2C1z0t2f1c2k2m2Q0;1Z2a2E1*2J0D0^0s0.0O2j2U0/2T1^2W1H2Y2!0.0L2(1!2*2k2v012/0B2#040j2?2l0:2_2-0)2|2~0f312^2U2`370.0m3a1f2O142C2p0Q1T2u35010z2K1=1c3l1d3j2S152)053s0S2P3c3q0r0.0S0v3h341o1H0u0.0y3M3G3O360v3J2z0k0b2f1;0d0n3T2,3V010-040w3*2V3,0d0.2J3!2f0N3;2`3.0e3a3S3N2F2{0.0^0o0h3}3q3.0M0x3a060y4h423U443@040c0v0v2g0+0v3|3A2@4j3+440l0.0C412+3=443.0i4a3,0k0h0.0F4J4G0.0H4D431*4A040I4T4k1*3.3:4v2l4E3d460B484Z4y4V0.0P4/4F1*4L2$4P4#0.0M4f4i4x4^1H3I040v0l0D4@4+040d0b5a3q0l3Q042H5f3?3^0l3`0c4u2S4U1H3.4e4(0/51514*3q4m4o4q2h0h4t4|5u0.4I5x5B5m5c5e5N5t0)3.4S5x522`4W0P4C5X5O444`042%5x4g4i5(1*552f0n0J0D135%5T454n4p4r5H5r2)0:0K3D0c2m2N673k1l3m2p2s2n0B1C6a0K3l640S0U0W0N04.

3. La fonction tri_denombrement

Compléter la fonction tri_denombrement qui prend en paramètre un tableau de nombres nombres et renvoie un tableau contenant les mêmes valeurs triées dans l'ordre croissant.

Les fonctions maximum et denombrement sont déjà chargées en mémoire.

Exemples

>>> nombres = [4, 5, 4, 2]
>>> tri_denombrement(nombres)
[2, 4, 4, 5]
>>> nombres = [5, 4, 3, 2, 1]
>>> tri_denombrement(nombres)
[1, 2, 3, 4, 5]
>>> nombres = []
>>> tri_denombrement(nombres)
[]

Évaluations restantes : 10/10

.128013ben,4vi[3mo5_txPhklpwf(: cga=ryS6]*u/72)s1+d050S0c0o0C0h0t0P0z0A0t0C0P0P0D010o0h0u010406050P0K0k0k0C0E0F040G0l0t0K0-0l0d050L0@0_0{0}0=0u04051d161g0L1d0=0S0h0g0#0%0)0+0r0h0B0r0t1u0r0o0:050W0b0t0c1p0(0*011t1v1x1v0o1D1F1B0o0E1e0o0r0#100P0u0C0d0+0N011H1r010w0Y0c0d0C0k0c1B1!1$1+1J1.1F1;1?0:0a0z0q0E0l0u0l0P0h130d0z0U1Y0E0E0c0A2b161_0d1e0L1W2o1T1V1U1C0S1{0+1x0d1:281B1m1o0$1I2y0h2A0d0l2E1B0u2h1e2m2o2S0?1#2c2G1,2L0E0`0t0:0Q2l2W0;2V1`2Y1J2!2$0:0N2*1$2,2m2x012;0C2%040j2^2n0=2{2/0+2~300f332`2W2|390:0m3c353e372}0l2#2 0:0H3j2-2X1q2:3o2=040M3c1h2Q162E2r0S1V2w3m0A2M1@1e3G1f3E2U172+053M0U2R3l3w0+0s0:0U0w3C363#010v0:0z3+3!2H2}0w0:1T0h0n0U2L0k0b2h1?0d0o3=2.3-0/040x463v3@0d0:3 410c0P4c2|490O0y3j0z4r3;3,4e0:0`0p0h3c4t3?1,0l0:0D4A3u3f4w0C4y0k0^4l3m494b3U2_4I3m4f044h2h4k4T2n4V480:0O4q4s4(4v040c0w0w2i0-0w4#2S4B473@4E044G4$044|4d2Z3(2B40421:45524.1,4R4P3-4X4Z4j5h3@490e4H4u56044x4z5d5r1J4n4,4r5e2:4g0l594j0n3{5l52542|4 514{5C0+490i0I5A5M3m3%040w3o5q4C5D4Y5%4}4D3/042J5+552:0b0:0E1$0B0c5m5f0:4S2U5x384K4y5;5N0:0R663m0k0h2(5}5y4*4p52064s6l5X5i5E5G0P5I0E0h5K5Q62015O6a6o4Y5F4i6r5J4`2+6n4~686A4/4;4?2j0h4_6f5S0:0i6T2}4g6X495V5L5R6y0:0J6M5~046W5w5(635*6:5,6g046$2S6k4-6x5Z2h0o0K0E156%6x5j6D4!6s6u6H2_0=0L3X0c2o2P7i3F1n3H2r2u2p0C1E7l0L3G7f0U0W0Y0P04.

4. La fonction tri_denombrement_en_place

Il n'est pas nécessaire de créer un autre tableau pour répondre à ce problème. On peut directement modifier le tableau passé en paramètre. Une version en place du tri va réécrire les valeurs triées directement dans le tableau de départ. Pour ce faire, il faut garder trace de l'indice où l'on doit écrire la prochaine valeur.

Compléter la fonction tri_denombrement_en_place qui prend en paramètre un tableau de nombres nombres et modifie en place le tableau contenant les mêmes valeurs triées dans l'ordre croissant. Cette fonction¹ ne renvoie rien.

Les fonctions maximum et denombrement sont déjà chargées en mémoire.

Exemples

>>> nombres = [4, 5, 4, 2]
>>> tri_denombrement_en_place(nombres)
>>> nombres
[2, 4, 4, 5]
>>> nombres = [5, 4, 3, 2, 1]
>>> tri_denombrement(nombres)
>>> nombres
[1, 2, 3, 4, 5]
>>> nombres = []
>>> tri_denombrement(nombres)
>>> nombres
[]

Évaluations restantes : 10/10

.8217.128013beqn,4évèi+[3mo5_txR;Phklpwf(: cg.a=ry0S6]Iu/72)As1^8d050%0d0t0K0l0A0Z0G0H0A0K0Z0Z0L010t0l0B010406050Z0T0p0p0K0M0N040P0q0A0T0{0q0f0G020K0p0B0w0G0v0d150M0e0T0d0Z050U12141618100B04051D1w1G0U1D100%0l0j0:0=0@0_0y0l0I0y0A1U0y0t0~050+0c0A0d1P0?0^011T1V1X1V0t1%1)1#0t0M1E0t0y0:1b0Z0B0K0f0_0W011+1R010D0-0d0f1j0d1#2123281-2b1)2e0p2g040b0G0x0M0q0B0q0Z0l1e1g0)1 0M0M0d0H2B1w2i0f1E0U1}2N1`1|1{1$0%2k0_1X0f2d2y1#1M1O0;1,2X0l2Z0f0q2%1#0B2G1E2L2N2^11221g2)292.0M150A0~0!2K2|0 2{2j2~1-30320~0W3623382L2W013d0K33040o3h2M103k3b0_3n3p0h3s3j2|3l3y0~0r3B3u3D3w3m0q313o0~0Q3I392}1Q3c3N3e040V3S3v3V3x3X3P040$3B1H2?1w2%2Q0%1|2V3L0H2/2q0(1N1E2=0d2@373-3`0)423a3%010z0~0)0D3-3$2*010C0~0G4f3K490f0D0~1`0l0s0)2.0p0c2G2p0f0t0s2d0s0B0=0H0d4m484h0}040E4K3U4h0f0~4w4y1u4Q3l4N0X0F3I0G4(4l4g2 0~150u0l3B4*4n4h0q0~0L4;3T3E4-0K4/0p134Y3L4N4P1x434+3c4U0q4x2G1v573i4|540~0X4%4)5i4o0~0d0D0D2H0{0D5f2^4=4L294^044`5g2M5z4R4,044v5c4W4A0t5349555Q4S5b5d4X5F475I1-4N0g4{593x4~4/5T294!5m4(5o5U042,1M4I4D0H0M2A0T2G5(4?5B4_615A1-0p0l0~0O5:5H3l4b040D3N655!5*040f6j3l0q4j5@6n5Y6d3L0f0c0~0M230I4J5Y5=5.0~562`5)3m5+4:6u6F1-5C0m6o3L68345-5#5k4$5Y064)6%6v496f6h0M6T5p040s6.4@6r2,6=2 6y046A0f6C6X0_5S6E6K4T045r5t2I0l5w70014N0n7c756t6J626Y040R4#6c6(5n745V4W5x587k710~7f737x6L6s5_0d5{5}0t5 6D7j667y7m6_6Q646O7s6m7p7q6)5?5^0l5`2H7I7K7Q0_6R5E5y6P0_6V04356#1w45413.7`0U3;1w0t3?7 2T2O0K1(7|3;1C5Z3l4z0s0D0K0z7G0y0o0~1o1q1s1u0G6!2`1J381D0S0A0G0Z000K0I2A0G0%000T1g4s0G3N1U2,3o0:168D1*3`1k1)4/0t0i0G2Y0i0,2G8x0l8Y0K0G0j3o0d5 0G4.0l321*1u0t8Q8Y0a3N0%8$0%0T0G4V8 0a0i0A0i5O0/0E0K0j2H0G8G0G1@0d0K912D7/01162A0y150t0d0u0~090E0f095l6u96982d0t0/0*9f2Z8+8-8/8;8?8`9n9p1}9s9u9w9y0#0W9A4;0=1 8T9u2A8X0Z0d6A8C1s0K8~0K0{8n0X0J4l8s890Y8,4B8A8.0u8x8/4I0G2x2,0t0g0G0-8Y008^8:0q2,0/120M8Y8o0)0Ta3a84Bak0T1N239G8p1H380T0A381X044I8_3o0I8K9T1*9K8y0K0B4G0l8n0G1s8zaq9L1)5 9H4B0l0k5ea72y2A1N8o0q910faC1)0Z5%0UaF10aFad0f0i4I0@2A1*2D5|0i9-9J9h851)9k0G232Z0u8R1f9t2e4Ban9H5s5u7a0/a61s8(0B8.8_3`0f0Z5c2pam2D9$0p98ai2G0J1wa{1waC387}0*0,0.04.

Une telle fonction qui ne renvoie rien est appelée procédure. ↩