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

.128013fe)à6i1p3m_:Svk(q5rtgx.=swcd;,èPo/hDaR2nA bl04Luy050C0c0u0L0g0S0z0Q0B0S0L0z0z0y010u0g0i010406050z0W0k0k0L0t0X040n0H0S0W0=0H0O0Q020L0k0i0D0Q0M0c0 0t0r0W0c0z050I0|0~10120`0i04051x1q1A0I1x0`0C0g0o0*0,0.0:0J0g0v0J0S1O0J0u0^050#0R0S0c1J0-0/011N1P1R1P0u1X1Z1V0u0t1y0u0J0*150z0i0L0O0:0N011#1L010b0%0c0O1d0c1V1{1}221%251Z280k2a040a0Q0G0t0H0i0H0z0g181a0Z1_0t0t0c0B2v1q2c0O1y0I1@2H1;1?1=1W0C2e0:1R0O272s1V1G1I0+1$2R0g2T0O0H2X1V0i2A1y2F2H2/0{1|1a2Z232(0t0 0S0^0h2E2?0_2=2d2^1%2`2|0^0N301}322F2Q01370L2}040j3b2G0`3e350:3h3j0U3m3d2?3f3s0^0s3v3o3x3q3g0H2{3i0^0f3v1B2-1q2X2K0C1?2P3F0B2)2k0Y1H1y2,0c2.313M3W0Z3(341K1%0p0^0Z0b3M3p3/0:0A0^0Q3^3E3`3g0b0^0 0w0g0k0}3 3.2!010@040q4a2@410O0^2(0k0R2A1p1r3)3_4c4e0d0m3C0Q4z3~4t2_440L463v4B404c0H0^0y4H334i4c0k0g0^0T4y4A4P3f3;040b3H4O4C364l0R4(4J230H3|042$4-4b4D044m4o1o4h3f4e4x4r3c064A554I4^3:0^0g3@522G574Q4_0O4,5d045f3f4L04020v0u0D4@5g4*04450g4~3F504W56564Y3F4k5x4F5z5k5m3F5o4N5M5G4j4+5D5N414!2A0u0W0t0O5u3y4E4G5k0`0I3+3%3N5:0I3Q1q0u3S5^2N2I0L1Y5=3Q1w3-5v0:2A0k0l0b0L0p0c0l0J0j0^1i1k1m1o0Q512;1D321x0V0L0Q4$0O2C0g193~5/5J46480k1q6A0Q1o0u2e0g6j6l0Q6y2$2u0g3i0g0z1!1Z0Q5y6D0Q0e6z3X044V5.6(0Q0i0W6U6O1a1R6J0S00276V4n6X0Z0)0o3i0c5#0z0x1B6p040P1-272v0Q0u0H170c4$6:0m6;6-726J6Q0=6T6V0t6#6%3,6*6G0B100Q1Z0)4{4p0Q0z196J7e0W0)6~6H0O0=0c0t0)2r2t0=0b0)7f0Q0O0W0(756o620K1}0)7K0)7C0Q0L177F7z0z0E7l7p6S1R7s6s6X6Z0}7;0o2B7B6s3$4S0F2A0Q701Z5#0Q0C0W7d5~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

.128013fe)1ip3m:Svk(5rtgx*=swcd,Po/]ha2n bl0+[4uy050y0c0q0F0f0K0v0I0x0K0F0v0v0u010q0f0g010406050v0P0i0i0F0p0Q040k0B0K0P0+0B0H050C0=0@0_0{0:0g04051b141e0C1b0:0y0f0l0Z0#0%0)0E0f0r0E0K1s0E0q0.050U0J0K0c1n0$0(011r1t1v1t0q1B1D1z0q0p1c0q0E0Z0~0v0g0F0H0)0G011F1p010b0W0c0H0F0i0c1z1Y1!1)1H1,1D1/1;0.0a0I0A0p0B0g0B0v0f110H0I0S1W0p0p0c0x29141@0H1c0C1U2m1R1T1S1A0y1_0)1v0H1.261z1k1m0!1G2w0f2y0H0B2C1z0g2f1c2k2m2Q0;1Z2a2E1*2J0p0^0K0.0e2j2U0/2T1^2W1H2Y2!0.0G2(1!2*2k2v012/0F2#040h2?2l0:2_2-0)2|2~0O312^2U2`370.0o3a1f2O142C2p0y1T2u35010x2K1=1c3l1d3j2S152)053s0S2P3c3q0m0.0S0b3h341o1H0w0.0I3M3G3O360b3J2z0i0J2f1;0H0q3T2,3V010-040n3*2V3,0H0.2J3!2f0v3;2`3.0z3a3S3N2F2{0.0^0s0f3}3q3.0d0j3a060I4h423U443@040c0b0b2g0+0b3|3A2@4j3+440B0.0u412+3=443.0N4a3,0i0f0.0L4J4G0.0D4D431*4A040t4T4k1*3.3:4v2l4E3d460F484Z4y4V0.0M4/4F1*4L2$4P4#0.0d4f4i4x4^1H3I040b0B0p4@4+040H0J5a3q0B3Q042H5f3?3^0B3`0c4u2S4U1H3.4e4(0/51514*3q4m4o4q2h0f4t4|5u0.4I5x5B5m5c5e5N5t0)3.4S5x522`4W0M4C5X5O444`042%5x4g4i5(1*552f0q0P0p135%5T454n4p4r5H5r2)0:0C3D0c2m2N673k1l3m2p2s2n0F1C6a0C3l640S0U0W0v04.

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

.128013fe)61i_p3m:Svk(5rtgx*=swcd,Po/]ha2n bl+[4uy7050A0c0s0H0g0M0x0K0z0M0H0x0x0w010s0g0i010406050x0Q0k0k0H0r0R040m0D0M0Q0-0D0J050E0@0_0{0}0=0i04051d161g0E1d0=0A0g0n0#0%0)0+0G0g0t0G0M1u0G0s0:050W0L0M0c1p0(0*011t1v1x1v0s1D1F1B0s0r1e0s0G0#100x0i0H0J0+0I011H1r010b0Y0c0J0H0k0c1B1!1$1+1J1.1F1;1?0:0a0K0C0r0D0i0D0x0g130J0K0U1Y0r0r0c0z2b161_0J1e0E1W2o1T1V1U1C0A1{0+1x0J1:281B1m1o0$1I2y0g2A0J0D2E1B0i2h1e2m2o2S0?1#2c2G1,2L0r0`0M0:0f2l2W0;2V1`2Y1J2!2$0:0I2*1$2,2m2x012;0H2%040j2^2n0=2{2/0+2~300P332`2W2|390:0q3c353e372}0D2#2 0:0e3j2-2X1q2:3o2=040S3c1h2Q162E2r0A1V2w3m0z2M1@1e3G1f3E2U172+053M0U2R3l3w0+0o0:0U0b3C363#010y0:0K3+3!2H2}0b0:1T0g0h0U2L0k0L2h1?0J0s3=2.3-0/040p463v3@0J0:3 410c0x4c2|490d0l3j0K4r3;3,4e0:0`0u0g3c4t3?1,0D0:0w4A3u3f4w0H4y0k0^4l3m494b3U2_4I3m4f044h2h4k4T2n4V480:0d4q4s4(4v040c0b0b2i0-0b4#2S4B473@4E044G4$044|4d2Z3(2B40421:45524.1,4R4P3-4X4Z4j5h3@490B4H4u56044x4z5d5r1J4n4,4r5e2:4g0D594j0h3{5l52542|4 514{5C0+490O0F5A5M3m3%040b3o5q4C5D4Y5%4}4D3/042J5+552:0L0:0r1$0t0c5m5f0:4S2U5x384K4y5;5N0:0N663m0k0g2(5}5y4*4p52064s6l5X5i5E5G0x5I0r0g5K5Q62015O6a6o4Y5F4i6r5J4`2+6n4~686A4/4;4?2j0g4_6f5S0:0O6T2}4g6X495V5L5R6y0:0v6M5~046W5w5(635*6:5,6g046$2S6k4-6x5Z2h0s0Q0r156%6x5j6D4!6s6u6H2_0=0E3X0c2o2P7i3F1n3H2r2u2p0H1E7l0E3G7f0U0W0Y0x04.

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

.128013.8217fe)6i1p3m_:Svk(q5rtgx.=swcd;,èPo^/]haR2nA bl0+é[48uy7I050C0d0u0M0g0T0z0R0B0T0M0z0z0y010u0g0i010406050z0!0k0k0M0t0#040n0H0T0!0{0H0P0R020M0k0i0D0R0N0d150t0r0!0d0z050J12141618100i04051D1w1G0J1D100C0g0o0:0=0@0_0L0g0v0L0T1U0L0u0~050+0S0T0d1P0?0^011T1V1X1V0u1%1)1#0u0t1E0u0L0:1b0z0i0M0P0_0O011+1R010c0-0d0P1j0d1#2123281-2b1)2e0k2g040a0R0G0t0H0i0H0z0g1e1g0)1 0t0t0d0B2B1w2i0P1E0J1}2N1`1|1{1$0C2k0_1X0P2d2y1#1M1O0;1,2X0g2Z0P0H2%1#0i2G1E2L2N2^11221g2)292.0t150T0~0h2K2|0 2{2j2~1-30320~0O3623382L2W013d0M33040j3h2M103k3b0_3n3p0Y3s3j2|3l3y0~0s3B3u3D3w3m0H313o0~0f3I392}1Q3c3N3e040$3S3v3V3x3X3P040Z3B1H2?1w2%2Q0C1|2V3L0B2/2q0(1N1E2=0d2@373-3`0)423a3%010p0~0)0c3-3$2*010A0~0R4f3K490P0c0~1`0g0l0)2.0k0S2G2p0P0u0l2d0l0i0=0B0d4m484h0}040q4K3U4h0P0~4w4y1u4Q3l4N0e0m3I0R4(4l4g2 0~150w0g3B4*4n4h0H0~0y4;3T3E4-0M4/0k134Y3L4N4P1x434+3c4U0H4x2G1v573i4|540~0e4%4)5i4o0~0d0c0c2H0{0c5f2^4=4L294^044`5g2M5z4R4,044v5c4W4A0u5349555Q4S5b5d4X5F475I1-4N0E4{593x4~4/5T294!5m4(5o5U042,1M4I4D0B0t2A0!2G5(4?5B4_615A1-0k0g0~0U5:5H3l4b040c3N655!5*040P6j3l0H4j5@6n5Y6d3L0P0S0~0t230v4J5Y5=5.0~562`5)3m5+4:6u6F1-5C0V6o3L68345-5#5k4$5Y064)6%6v496f6h0t6T5p040l6.4@6r2,6=2 6y046A0P6C6X0_5S6E6K4T045r5t2I0g5w70014N0X7c756t6J626Y040K4#6c6(5n745V4W5x587k710~7f737x6L6s5_0d5{5}0u5 6D7j667y7m6_6Q646O7s6m7p7q6)5?5^0g5`2H7I7K7Q0_6R5E5y6P0_6V04356#1w45413.7`0J3;1w0u3?7 2T2O0M1(7|3;1C5Z3l4z0l0c0M0p7G0L0j0~1o1q1s1u0R6!2`1J381D0%0T0R0z000M0v2A0R0C000!1g4s0R3N1U2,3o0:168D1*3`1k1)4/0u0W0R2Y0W0,2G8x0g8Y0M0R0o3o0d5 0R4.0g321*1u0u8Q8Y0b3N0C8$0C0!0R4V8 0b0W0T0W5O0/0q0M0o2H0R8G0R1@0d0M912D7/01162A0L150u0d0w0~090q0P095l6u96982d0u0/0*9f2Z8+8-8/8;8?8`9n9p1}9s9u9w9y0I0O9A4;0=1 8T9u2A8X0z0d6A8C1s0M8~0M0{8n0e0x4l8s890Q8,4B8A8.0w8x8/4I0R2x2,0u0E0R0-8Y008^8:0H2,0/120t8Y8o0)0!a3a84Bak0!1N239G8p1H380!0T381X044I8_3o0v8K9T1*9K8y0M0i4G0g8n0R1s8zaq9L1)5 9H4B0g0F5ea72y2A1N8o0H910PaC1)0z5%0JaF10aFad0P0W4I0@2A1*2D5|0W9-9J9h851)9k0R232Z0w8R1f9t2e4Ban9H5s5u7a0/a61s8(0i8.8_3`0P0z5c2pam2D9$0k98ai2G0x1wa{1waC387}0*0,0.04.

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