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

.128013.128203rv56èbeà:olg1ma(cd` tu4S2Dhws;pkT=.30q/_P,iLxyn)fRA050t0i0w0q0S0m0E0v0s0m0q0E0E0J010w0S0G010406050E0x0p0p0q0c0V040z0l0m0x0^0l0W0v020q0p0G0F0v0Z0i120c0N0x0i0E050O0 1113150}0G041t1A051D0O1D1F1A0}0t0S0d0-0/0;0?0C0S0n0C0m1T0C0w0{050(0h0m0i1O0:0=011S1U1W1U0w1$1(1!0w0h0l0t151#0c1B0w0C0-180E0G0q0W0?0A011*1Q010Y0*0i0W1g0i1!25272c1,2f1(2i0p2k040a0v0Q0c0l0G0l0E0S1b1d0$230c0c0i0s2F1t2m0W1B0O212R0w1 1~200t2o0?1W0W2h2C1!1L1N0.1+2#0S2%0W1{1M1!0G2K1B2P2R2|0~261d2-2d2=0c120m0{0o2O300|2 2n321,34360{0A3a273c2P2!013h0q37040L3l2Q0}3o3f0?3r3t0y3w3n303p3C0{0e3F3y3H3A3q0l353s0{0f3F1C2`1t2+2U0t2Y3p0s1{2u0#1M1B2_0i2{3b3W3)0$3;3e1P1,0H0{0$0Y3W3z3{0?0D0{0v413O433q0Y0{120U0S0p10483`2.010`040r4j314a0W0{2=0p0h2K1s1u3=424l4n0X0k3M0v4I474C334d0q4f3F4K494l0l0{0J4Q3d4r4l0p0S0{0M4H4J4Y3p3}040Y3R4X4L3g4u0h4;4S2d0l45042:4_4k4M044v4x1r4q3p4n4G4A3m064J5e4R513|0{0S405b2Q5g4Z520W4^5m045o3p4U04020n0w0F505p4?044e0S573P594)5f5f4+3P4t5G4O5I5t5v3P5x4W5V5P4s4@5M5W4a4-2K0w0x0c0W5D3I4N4P5t0}0O3@3:3X5|0O3!1t0w3$612W2S1`1|2U0q1%5~3!1z3_5E0?2K0p0P0Y0q0H0i0P0C0L0{1l1n1p1r0v5a2~1G3c1A0T0q0v4/0W2M0S1c475{5S4f4h0p1t6M0v1r0w2o0S6v6x0v6K2:2E0S3s0S0E1)1(0v5H6P0v0j6L3*044(5`6@0v0G0x6*6!1d1W6V0m002h6+4w6-0$0,0d3s0i5.0E0K1C3c2+3p1.1V1X1Z6f3p2q2h2j0{0b0v0I0i0U0w0i3W3/6f2}3=6M0!1=2h2F0v0w0l1a0i4/6 0k706|7e6V6$0^6)6+0c6;0v0u0M0u0-130v1(0,544y0v0E1c6V7O0x0,7a6T0W0^0i0c0,2B2D0^0Y0,7P0v0W0x0+0K06060B270,7{0,7:0v0q1a7?0s0:0R7V7Z6(1W7$6E6-6/108o0d2L7/6E3/4#0g2K0v7c1(5.0v0t0x7N6a1(8p8f6R6@5}2R6d3Z0%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

.128013rv5be:olg1ma*(cd tu4S2hwspk]=30/[P,ixyn)+f050q0f0s0m0K0i0z0r0p0i0m0z0z0D010s0K0A010406050z0t0l0l0m0b0M040v0h0i0t0+0h0N050G0=0@0_0{0:0A04141b051e0G1e1g1b0:0q0K0c0Z0#0%0)0x0K0j0x0i1u0x0s0.050U0e0i0f1p0$0(011t1v1x1v0s1D1F1B0s0e0h0q0{1C0b1c0s0x0Z0~0z0A0m0N0)0w011H1r010Q0W0f0N0m0l0f1B1)1+1:1J1?1F1_1{0.0a0r0I0b0h0A0h0z0K110N0r0S1%0b0b0f0p2g141~0N1c0G1#2t0s1Z1Y1!0q200)1x0N1^2d1B1m1o0!1I2D0K2F0N1V1n1B0A2m1c2r2t2X0;1*2h2L1;2Q0b0^0i0.0k2q2#0/2!1 2%1J2)2+0.0w2/1+2;2r2C012_0m2,040E2}2s0:302@0)33350u382 2#313e0.0d3h1d2V142J2w0q2A310p1V1|1c3s1f3q2Z152:053x0S2W3j3c010B0.0S0Q3o3b1q1J0y0.0r3S3L3U3d0Q3P2G0l0e2m1{0N0s3Z2?3#010-040o3:2$3=0N0.2Q3*2m0z3`313@0J3h3Y3T2M320.0^0L0K433M3@0O0g3h060r4n483!4a3}040f0Q0Q2n0+0Q423F2~4p3;4a0h0.0D472=3{4a3@0H4g3=0l0K0.0F4P4M0.0C4J491;4G040n4Z4q1;3@3_4B2s4K3k4c0m4e4)4E4#0.0P4^4L1;4R2-4V4+0.0O4l4o4D4~1J3O040Q0h0b4}4;040N0e5g3M0h3W042O5l3|3~0h400f4A2Z4!1J3@4k4.0/57574:3M4s4u4w2o0K4z525A0.4O5D5H5s5i5k5T5z0)3@4Y5D58314$0P4I5%5U4a50042.5D4m4o5.1;5b2m0s0t0b135-5Z4b4t4v4x5N5x2:0:0G3I0f2t2U6d3r1n3t2w2y2u1U1W2w0m1E6g0G3s6a0S0U0W0z04.

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

.128013rv56be:olg1ma*(cd7 tu4S2hwspk]=3/_P[,ixyn)+f050r0g0u0n0M0j0B0t0q0j0n0B0B0F010u0M0C010406050B0v0m0m0n0b0O040x0i0j0v0-0i0P050H0@0_0{0}0=0C04161d051g0H1g1i1d0=0r0M0c0#0%0)0+0z0M0k0z0j1w0z0u0:050W0f0j0g1r0(0*011v1x1z1x0u1F1H1D0u0f0i0r0}1E0b1e0u0z0#100B0C0n0P0+0y011J1t010S0Y0g0P0n0m0g1D1+1-1=1L1^1H1{1}0:0a0t0J0b0i0C0i0B0M130P0t0U1)0b0b0g0q2i16200P1e0H1%2v0u1#1!1$0r220+1z0P1`2f1D1o1q0$1K2F0M2H0P1X1p1D0C2o1e2t2v2Z0?1,2j2N1?2S0b0`0j0:0l2s2%0;2$212)1L2+2-0:0y2;1-2?2t2E012{0n2.040G2 2u0=322_0+35370w3a312%333g0:0d3j3c3l3e340i2,360:0e3q2@2(1s2`3v2|040s3j1f2X162L2y0r2C330q1X1~1e3N1h3L2#172=053S0U2Y3s3D0+0D0:0U0S3J3d3+010A0:0t3;3*2O340S0:2z0M0I0U2S0m0f2o1}0P0u3{2^3?0/040p4c3C3}0P0:45470g0B4i334f0Q0h3q0t4x3`3=4k0:0`0N0M3j4z3|1?0i0:0F4G3B3m4C0n4E0m0^4r3t4f4h3!304O3t4l044n2o4q4Z2u4#4e0:0Q4w4y4.4B040g0S0S2p0-0S4+2Z4H4d3}4K044M4,04524j2*3.2I46481`4b584@1?4X4V3?4%4)4p5n3}4f0L4N4A5c044D4F5j5x1L4t4=4x5k2`4m0i5f4p0I415r585a335557515I0+4f0K0E5G5S3t3-040S3v5w4I5J4(5-534J3^042Q5;5b2`0f0:0b1-0k0g5s5l0:4Y2#5D3f4Q4E5`5T0:0R6c3t0m0M2/635E4:4v58064y6r5%5o5K5M0B5O0b0M5Q5W68015U6g6u4(5L4o6x5P502=6t546e6G4^4`4|2q0M4 6l5Y0:0K6Z344m6%4f5#5R5X6E0:0o6S64046$5C5.695:6_5=6m046,2Z6q4?6D5)2o0u0v0b156-6D5p6J4*6y6A6N300=0H3%0g2v2W7o3M1p3O2y2A2w1W1Y2y0n1G7r0H3N7l0U0W0Y0B04.

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.128013.128203v56èbolgmadt4Shs;ké.3q/_P[)^r8e:1*(c7 uI2wp]T=0,ixyn+fRA050n0H0o0m0Z0j0s0O0M0j0m0s0s0W010o0Z0T010406050s0P0l0l0m0F0#040q0i0j0P0~0i0$0O020m0l0T0t0O0)0H180F0y0P0H0s050z1517191b130T041z1G051J0z1J1L1G130n0Z0d0?0^0`0|0r0Z0k0r0j1Z0r0o11050.0h0j0H1U0_0{011Y1!1$1!0o1,1.1*0o0h0i0n1b1+0F1H0o0r0?1e0s0T0m0$0|0R011:1W010(0:0H0$1m0H1*2b2d2i1=2l1.2o0l2q040b0O0B0F0i0T0i0s0Z1h1j0,290F0F0H0M2L1z2s0$1H0z272X0o2524260n2u0|1$0$2n2I1*1R1T0@1;2+0Z2-0$211S1*0T2Q1H2V2X32142c1j2?2j2{0F180j110J2U3612352t381=3a3c110R3g2d3i2V2*013n0m3d040x3r2W133u3l0|3x3z0p3C3t363v3I110e3L3E3N3G3w0i3b3y110f3S3j371V3m3X3o040N3$3F3)3H3+3Z040G3L1I301z2;2!0n2(3v0M212A0+1S1H2 0H313h3`430,4b3k3;010u110,0(3`3:2@010S110O4o3U4i0$0(112#0Z0A0,2{0l0h2Q2z0$0o0A2n0A0T0^0M0H4v4h4q10040L4T3(4q0$114F4H1x4Z3v4W0D0I3S0O4;4u4p3911180!0Z3L4?4w4q0i110W4}3%3O4_0m4{0l164+3V4W4Y1A4c4@3m4%0i4G2Q1y5g3s555d110D4:4=5r4x110H0(0(2R0~0(5o324~4U2j5104535p2W5I4!4^044E5l4)4J0o5c4i5e5Z4#5k5m4*5O4g5R1=4W0Y545i3H574{5$2j4-5v4;5x5%042_1R4R4M0M0F2K0P2Q5;4 5K526a5J1=0l0Z110X5|5Q3v4k040(3X6e5-5?040$6s3v0i4s606w5+6m3V0$0h110F2d0k4S5+5~5`115f345=3w5@4|6D6O1=5L0%6x3V6h3e5_5.5t4/5+064=6:6E4i6o6q0F6$5y040A6`506A2_6~396H046J0$6L6*0|5#6N6T4$045A5C2S0Z5F79014W0C7l7e6C6S6b6+040U4.6l6;5w7d5(4)5G5h7t7a117o7c7G6U6B620H64660o686M7s6f7H7v726Z6d6X7B6v7y7z6=5 610Z632R7R7T7Z0|6!5N5H6Y0|6(043f6.1z4e4a3{830z3~1z0o40882$2Y20222!0m1-853~1F5,3v4I0A0(0m0u7P0r0x111r1t1v1x0O6-341M3i1G0Q0j0O0s000m0k2K0O0n000P1j4B0O3X1Z2_3y0?198P1/431n1.4{0o0v0O2,0v0/2Q8J0Z8.0m0O0d3y0H680O4`0Z3c1/1x0o8$8.0a3X0n8=0n0P0O4(9b0a0v0j0v5X0=0L0m0d2R0O8S0O1|0H0m9d2N7{01192K0r180o0H0!11090L0$095u6D9i9k2n0o0=0-9r2-8`8|8~9092969z9B279E9G9I9K0E0R9M4}0^298)9G2K8-0s0H6J8O1v0m9a0m0~8z0D0w4u8E1Q1S3v1@1#1%1)8m3V2w2n2p110c0O0V9G9F3`495,334c82040*8{4K8M8}0!8J8~4R0O2H2_0o0Y0O0:8.00948 0i2_0=150F8.8A0,0PaDaI4KaU0P1S2d9S8B06060K0?9U3y0k8W9)1/9W8K0m0T4P0Z8z0O1v8La!9X1.689T4K0Z0g5naH2I2K1S8A0i9d0$0P0j1.0s0Ya/aM8I0$0v4R0`2K1/2N650v9|9V9t8h1.9w0O2d2-0!8%1i9F2o4KaX9T5B5D7j0=aG1v8@0T8}95430$0s5l2zaW2N9=0l9kaS2Q0w130zaw842X8k3}0-0/0;04.

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