Aller au contenu

Préparatifs pour les algorithmes de tri⚓︎

Modifications sur place

Dans tous les exercices sur les algorithmes de tri, et sauf mention contraire, les modifications apportées aux tableaux sont effectuées directement sur les tableaux. On dit que ce sont des modifications sur place.

Il ne faut donc pas rajouter de return tab à la fin des fonctions. Le tableau passé en paramètre est modifié lors de l'appel de la fonction et les tableaux étant muables en Python, les modifications persistent après l'appel de la fonction.

Néanmoins, pour faciliter la recherche de bugs, vous pouvez rajouter un return tab pour simplifier les tests.

Rappels sur le module random

Afin de produire des tableaux à trier, nous allons utiliser le module random. On pourra utiliser deux fonctions différentes : random, qui renvoie un nombre tiré aléatoirement dans l'intervalle \([0;1[\) et randint qui prend deux entiers a et b et qui renvoie un entier tiré au hasard entre a et b inclus.

Exemple d'utilisation
>>> import random
>>> random.random()  # génération d'un nombre entre 0 et 1
0.4671064597997632
>>> random.randint(0, 100)  # un entier entre 0 et 100 inclus
24
Génération de tableaux pour tester les fonctions

À l'aide du module random, on peut générer des tableaux aléatoires à l'aide d'une fonction comme la suivante :

Vous pourrez utiliser cette fonction dans les exercices suivants
def genere_tableau(n):
    return [random.random() for _ in range(n)]
Extraits de quelques appels
>>> genere_tableau(4)
[0.34253573685847016, 0.5447961372120071, 0.16355941327056156, ...
>>> genere_tableau(100)
[0.8066534034910527, 0.8467728275829794, 0.10028352226518222, ...

Vous pouvez aussi utiliser la fonction range en mettant un, deux ou trois paramètres pour obtenir des listes triées de façon croissante ou décroissante. Cette fonction ne renvoie pas vraiment une liste Python. Pour obtenir une liste, ou un tableau, il faut utiliser en plus la fonction list :

Génération de listes triées
>>> list(range(4, 8))
[4, 5, 6, 7]
>>> list(range(4, 8))
[4, 5, 6, 7]
>>> list(range(4, 45, 3))
[4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43]
>>> list(range(10, -1, -1))
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Exercice 1

Compléter le code de la fonction echange qui prend en paramètres un tableau tab et deux entiers i et j, et qui échange les valeurs de tab se trouvant aux indices i et j. On suppose que i et j sont des indices valides de tab.

Exemples d'utilisation
>>> tab = [4, 9, 1, 10]
>>> echange(tab, 0, 2)
>>> tab
[1, 9, 4, 10]
>>> animaux = ["chat", "chien", "poule", "vache"]
>>> echange(animaux, 2, 1)
>>> animaux
["chat", "poule", "chien", "vache"]

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5

.128013;)3=ljqnRgv,S"/:rfuOemkdas p h1itP(_y2[4]cbo030s0p0B0t0A090u0v0K090t0u0u080i0B0A0w0i020x030u0n0q0q0t0l0F020h0M090n0%0M0c0v000t0q0w050v0d0p0:0l0b0n0p0u030j0-0/0;0?0+0w02031l1e1o0j1l0+0s0A0f0V0X0Z0#0y0A0e0y091C0y0B0)030Q0L090p1x0Y0!0i1B1D1F1D0B1L1N1J0B0l1m0B0y0V0_0u0w0t0c0#0G0i1P1z0i0m0S0p0c110p1J1+1-1=1R1^1N1{0q1}02040v0C0l0M0w0M0u0A0|0~0O1)0l0l0p0K2i1e1 0c1m0j1'2u1#1%1$1K0s210#1F0c1`2f1J1u1w0W1Q2E0A2G0c0M2K1J0w2n1m2s2u2Y0,1,0~2M1?2R0l0:090)0z2r2$0*2#202'1R2)2+0)0G2/1-2;2s2D0i2_0t2,02072}2t0+302@0#33350I382u2V0p2u2K2x0s1%2C3c0i0K2S270N1v1m3j2X2:3h033t0O3A2?1y1R0r0)0O0m3h0v2=2%3I3d0m0)2o0y1-0e0p3C3b3S0i0(020D3#2$310c0)1L3+3H2N3'0)0g3O3Q3-0)0A3;3R3?3(3_1f2:3P3$3?3.020a3 313(060k3h0x0v4j463,3r490B123`471?0M0)084r4m3%4o0t0L4c3r3(0H4D4z3}4H410)0J4h4k4l3=2(3/4B4K1?4F4V2^4J442~3{4E4M4x4R1R4u024w4#2t4Q404S023:4/3G4=1R4X4_4%4I4a4Y0#3(4N4_4i4k4 484T4C4~4s4|0)4G5d4y5a515i4*534(4_4;314,4.2Y5r4n3/4q561e3E3k1p2W1e3m1e0B3o5I2A2v4B1N3l3x1k4`312n0q0E0m0t0r0p0E0y070)16181a1c0v4g4~1r2;1l0o0~0w0p0{0v0t0n0Z0A0v0{0S0A0u0p0l0v1N0U0t0m0m2o0Q2i0U0q0n090%0w680v2k0C0F1'0}5-1p2;2K311T1E1G1I3y5F2!4~5C5T3r3K023M4)4{3T3V0K3X0c3Z523@3)6U4A5c2!5e5o02435v594?3~5m6N6V6'456)4Z5l6!5j4W0)4f4O586#325b6U4}6@5n6 026+736-546/2~5w504^784d5g6X0)4b6,7h02556(6~5t5u6:6~6Y717i7m5x6?3B6~7a6M3|4@4U7z3%727C6^6=777M74544h5B3u3i5F0j3m0+7Y0P0R0T02.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5

.128013;)3=ljqnRgv,S"/:rfuOemkdas p h1itP(_y2[4]cbo030s0p0B0t0A090u0v0K090t0u0u080i0B0A0w0i020x030u0n0q0q0t0l0F020h0M090n0%0M0c0v000t0q0w050v0d0p0:0l0b0n0p0u030j0-0/0;0?0+0w02031l1e1o0j1l0+0s0A0f0V0X0Z0#0y0A0e0y091C0y0B0)030Q0L090p1x0Y0!0i1B1D1F1D0B1L1N1J0B0l1m0B0y0V0_0u0w0t0c0#0G0i1P1z0i0m0S0p0c110p1J1+1-1=1R1^1N1{0q1}02040v0C0l0M0w0M0u0A0|0~0O1)0l0l0p0K2i1e1 0c1m0j1'2u1#1%1$1K0s210#1F0c1`2f1J1u1w0W1Q2E0A2G0c0M2K1J0w2n1m2s2u2Y0,1,0~2M1?2R0l0:090)0z2r2$0*2#202'1R2)2+0)0G2/1-2;2s2D0i2_0t2,02072}2t0+302@0#33350I382u2V0p2u2K2x0s1%2C3c0i0K2S270N1v1m3j2X2:3h033t0O3A2?1y1R0r0)0O0m3h0v2=2%3I3d0m0)2o0y1-0e0p3C3b3S0i0(020D3#2$310c0)1L3+3H2N3'0)0g3O3Q3-0)0A3;3R3?3(3_1f2:3P3$3?3.020a3 313(060k3h0x0v4j463,3r490B123`471?0M0)084r4m3%4o0t0L4c3r3(0H4D4z3}4H410)0J4h4k4l3=2(3/4B4K1?4F4V2^4J442~3{4E4M4x4R1R4u024w4#2t4Q404S023:4/3G4=1R4X4_4%4I4a4Y0#3(4N4_4i4k4 484T4C4~4s4|0)4G5d4y5a515i4*534(4_4;314,4.2Y5r4n3/4q561e3E3k1p2W1e3m1e0B3o5I2A2v4B1N3l3x1k4`312n0q0E0m0t0r0p0E0y070)16181a1c0v4g4~1r2;1l0o0~0w0p0{0v0t0n0Z0A0v0{0S0A0u0p0l0v1N0U0t0m0m2o0Q2i0U0q0n090%0w680v2k0C0F1'0}5-1p2;2K311T1E1G1I3y5F2!4~5C5T3r3K023M4)4{3T3V0K3X0c3Z523@3)6U4A5c2!5e5o02435v594?3~5m6N6V6'456)4Z5l6!5j4W0)4f4O586#325b6U4}6@5n6 026+736-546/2~5w504^784d5g6X0)4b6,7h02556(6~5t5u6:6~6Y717i7m5x6?3B6~7a6M3|4@4U7z3%727C6^6=777M74544h5B3u3i5F0j3m0+7Y0P0R0T02.
Exercice 2

Compléter le code de la fonction est_trie(tab) qui renvoie True si et seulement si le tableau tab est trié dans l'ordre croissant. On considère qu'un tableau vide est trié.

Indication

Lorsqu'on a un tableau de 3 valeurs, il faut faire 2 comparaisons. S'il y a 10 valeurs, il faut faire 9 comparaisons.

Il faut donc faire attention aux nombres d'itérations réalisées. À chaque itération on fait une comparaison. Il faut donc en faire une de moins que le nombre d'éléments dans le tableau.

Exemples d'utilisation
>>> est_trie([4, 1, 2])
False
>>> est_trie([1, 2, 4])
True
>>> est_trie(["Alice", "Bob", "Charlie", "Eve"])
True
>>> est_trie(["petit", "grand", "absurde"])
False

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5

.128013;)3=x+lwTqn'Rgv,S.à"A5/:rfFuOemkêèédas p h1itP(_y2[4]cb-o030E0y0N0F0M0b0G0H0W0b0F0G0G080o0N0M0I0o020J030G0w0z0z0F0t0R020l0Z0b0w0?0Z0f0H000F0z0I050H0h0y100t0e0w0y0G030r0}0 11130{0I02031y1r1B0r1y0{0E0M0j0+0-0/0;0K0M0i0K0b1P0K0N0_030%0X0b0y1K0.0:0o1O1Q1S1Q0N1Y1!1W0N0t1z0N0K0+160G0I0F0f0;0S0o1$1M0o0u0(0y0f1e0y1W1{1}221'251!280z2a02040H0O0t0Z0I0Z0G0M191b0#1_0t0t0y0W2v1r2c0f1z0r1@2H1;1?1=1X0E2e0;1S0f272s1W1H1J0,1%2R0M2T0f0Z2X1W0I2A1z2F2H2.0|1|1b2Z232'0t100b0_0L2E2=0`2;2d2@1'2_2{0_0S2 1}312F2Q0o360F2|02073a2G0{3d340;3g3i0U3l3c2=3e3r0_0q3u1C2,1r2X2K0E1?2P3p0o0W2(2k0!1I1z2+0y2-303B3M0#3U331L1'0A0_0#0u3u0H322?3#3q0u0_1p0N0Q1;0M0y3B3o3.0o0^020P3{3w3K0f0_1Y423!2!3~0_060s3u0J0H4h3+3|4a3%020u0Z0t3*3,3x0_0M4r4k230Z0c4u0f4w433}0f0X0_0t1}0i3`1s3V4x1'3 414N3b4s444H022h483-4a4R4!4t02474T2G4V3}3 064'3K0Z0_0Y4;3}0z0M2}4_4$4c4e4+0`4i544j4E4l4u3)5256492^460F0X4~233 0T5i354u5m0;3 0V4D5d1'4?02000i0N055t4#5e4)5g5p4b025l524-4a45024v5L4P0;5w0a5H4{4}5R575j0_0V512.4g555*5M234m2A0N0w0t4C5b5,3$0W0_0v3h0G4M5(545^0;5.0$5;5?2.5c5D5_0_0d0t1o4f1r3X3T3C6j0r3F1r0N3H6o2N2I5g1!2H3F1x3Z6a0;2A0z0Q0u0F0A0y0Q0K070_1j1l1n1p0H5'3V1E311y0x1b0I0y180H0F0w0/0M0H0D0W0t0M2A0H0-0H4o0f2C0M1a6$2$2t6R1C312X3e1)1R1T1V3R3D2:5L6i6z3e4m3(5C3x3:023=3@6-5 4O5!4Q0_4S2:5S3f5f5h5Z5u5q504f617u4m4o4q5@7u5O5Q68620o4z4B7g4W4I4K7n4U7u4%7y6A0o5X022~7Z3e3 0k7R4F4X4Z7(3K7Y7t7p3q7w5H4/4d7C5*697d597,5N7_7:4.0_5K7?7z7v5P5H5w4^854a7$7'897!5r824y0_5y5A8n5n5F7x8k7)875H7K7`5$6S3b5)7~4i7N645:5=8s635`025|0)7V3m7D7@0o8J668M8W8O6d6f520{0r7b6k6w3Q6y0p0w6:3_8:2x3M1f110y0t0+0K0F6P6*0b0D2j0f0N6$0j2B6:1#0}1I1}960$0H2x0G0g110t0B0N8{0H0n6:9k0j9e0Y0#5=3_0t0k0H6`8^940W1#6%9h6!090M0C2j0H9g9D0Z8_6/0b0g0D9294960F980W9a0H2+6+0D0#950m6 8(0#0%0(0G02.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5

.128013;)3=x+lwTqn'Rgv,S.à"A5/:rfFuOemkêèédas p h1itP(_y2[4]cb-o030E0y0N0F0M0b0G0H0W0b0F0G0G080o0N0M0I0o020J030G0w0z0z0F0t0R020l0Z0b0w0?0Z0f0H000F0z0I050H0h0y100t0e0w0y0G030r0}0 11130{0I02031y1r1B0r1y0{0E0M0j0+0-0/0;0K0M0i0K0b1P0K0N0_030%0X0b0y1K0.0:0o1O1Q1S1Q0N1Y1!1W0N0t1z0N0K0+160G0I0F0f0;0S0o1$1M0o0u0(0y0f1e0y1W1{1}221'251!280z2a02040H0O0t0Z0I0Z0G0M191b0#1_0t0t0y0W2v1r2c0f1z0r1@2H1;1?1=1X0E2e0;1S0f272s1W1H1J0,1%2R0M2T0f0Z2X1W0I2A1z2F2H2.0|1|1b2Z232'0t100b0_0L2E2=0`2;2d2@1'2_2{0_0S2 1}312F2Q0o360F2|02073a2G0{3d340;3g3i0U3l3c2=3e3r0_0q3u1C2,1r2X2K0E1?2P3p0o0W2(2k0!1I1z2+0y2-303B3M0#3U331L1'0A0_0#0u3u0H322?3#3q0u0_1p0N0Q1;0M0y3B3o3.0o0^020P3{3w3K0f0_1Y423!2!3~0_060s3u0J0H4h3+3|4a3%020u0Z0t3*3,3x0_0M4r4k230Z0c4u0f4w433}0f0X0_0t1}0i3`1s3V4x1'3 414N3b4s444H022h483-4a4R4!4t02474T2G4V3}3 064'3K0Z0_0Y4;3}0z0M2}4_4$4c4e4+0`4i544j4E4l4u3)5256492^460F0X4~233 0T5i354u5m0;3 0V4D5d1'4?02000i0N055t4#5e4)5g5p4b025l524-4a45024v5L4P0;5w0a5H4{4}5R575j0_0V512.4g555*5M234m2A0N0w0t4C5b5,3$0W0_0v3h0G4M5(545^0;5.0$5;5?2.5c5D5_0_0d0t1o4f1r3X3T3C6j0r3F1r0N3H6o2N2I5g1!2H3F1x3Z6a0;2A0z0Q0u0F0A0y0Q0K070_1j1l1n1p0H5'3V1E311y0x1b0I0y180H0F0w0/0M0H0D0W0t0M2A0H0-0H4o0f2C0M1a6$2$2t6R1C312X3e1)1R1T1V3R3D2:5L6i6z3e4m3(5C3x3:023=3@6-5 4O5!4Q0_4S2:5S3f5f5h5Z5u5q504f617u4m4o4q5@7u5O5Q68620o4z4B7g4W4I4K7n4U7u4%7y6A0o5X022~7Z3e3 0k7R4F4X4Z7(3K7Y7t7p3q7w5H4/4d7C5*697d597,5N7_7:4.0_5K7?7z7v5P5H5w4^854a7$7'897!5r824y0_5y5A8n5n5F7x8k7)875H7K7`5$6S3b5)7~4i7N645:5=8s635`025|0)7V3m7D7@0o8J668M8W8O6d6f520{0r7b6k6w3Q6y0p0w6:3_8:2x3M1f110y0t0+0K0F6P6*0b0D2j0f0N6$0j2B6:1#0}1I1}960$0H2x0G0g110t0B0N8{0H0n6:9k0j9e0Y0#5=3_0t0k0H6`8^940W1#6%9h6!090M0C2j0H9g9D0Z8_6/0b0g0D9294960F980W9a0H2+6+0D0#950m6 8(0#0%0(0G02.
Exercice 3

Donner plusieurs tests, à l'aide de assert pour vérifier la correction de la fonction est_trie (qui est déjà en mémoire). Pour valider cet exercice, il faut tester un certain nombre de cas particuliers.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 50/50

.128013;)3=9lwqnç8gv,Sà"5/rf7uOIemkèédas p h1EitP(_y2[46cb]Uùo030z0u0J0A0I0a0B0C0S0a0A0B0B080l0J0I0D0l020E030B0r0v0v0A0o0N020j0X0a0r0;0X0d030n0{0}0 110_0D02031h1a1k0n1h0_0z0I0h0)0+0-0/0F0I0g0F0a1y0F0J0@030#0T0a0u1t0,0.0l1x1z1B1z0J1H1J1F0J0o1i0J0F0)140B0D0A0d0/0O0l1L1v0l0p0%0u0d0A0v0u1F1'1)1.1N1;1J1@1_0@040C0K0o0X0D0X0B0I170d0C0Z1$0o0o0u0S2e1a1|0d1i0n1!2r1X1Z1Y1G0z1~0/1B0d1?2b1F1q1s0*1M2B0I2D0d0X2H1F0D2k1i2p2r2V0`1(2f2J1/2O0o0~0a0@0G2o2Z0^2Y1}2#1N2%2(0@0O2,1)2.2p2A0l2?0A2)02072`2q0_2}2;0/30320Q352|2Z2~3b0@0m3e373g392 0X2'310@0R3l2/2!1u2=3q2@020q3v383y3a3A3s020f3e1l2T1a2H2u0z1Z2z3o0S2P1`1i3Q1j3O2X1b2-033W0Z2U3n3G0l0w0@1M0u0o0J3e0C3w2~0X0b0@2O3^3'2{3`3F2K2 0@0u0B0J0M1X0I0u3M451/0?020L0P4g3-460v0I0@3d422q3{3o4j0i3_4w3.4q2*4n2:3.4y4A4h1N4D022_4u3,4G464j0U063_444o1/0S0G0@010C0V2!0,2g1K0T0,4f4P3m4R1/3:023=3@4J4Y2=484a4c0o4e4F3x4S0@4l532~4M2+4P4B55024z4P4X4=4L4r4N584x0@5g2V5i541/4M4t2X4K0/4T4V5h5s2~4!4$4'2f0A162k0)4*2h4-0B4/2V4;5t1N4@4_415r5d2$4~4b4d5R3(5y0l4j4l4U4W5!1N5F024%0t0a0C0p5J0J0C0D1?5Q0o0C0k0C0+650I4a1K0h0I0Z3E4|0/5W0-3?5Y2-5D3o0d5$50525c5*5,4m6s6f0l5a5n4H0@5.5C5:0/5=4%0H5}1J5M0(0z00010709050r2D67690C0A0h2l0C6U0C5Q0r5_0y0a0y1_0d0J0i6Y0r6M0C0X0W3l5T2~6h616k436F0l3}3 0X702q6m3.6o02495%515(2{726u6A4p5l5b5x6x4I5h724M346w5j5z5p4{7w6y5l4O7o7A5A5/5*6H0C0s2f0h0y511;1K0c0r1K1J0(0O5~2k4q3?0(6+6-1?0J0(4d0y0(6V0{0p1;5Q6/5~0,6e7A6~6j7z5U0/7402407}3h6p5'7k4i566v7E7~7B4s871N7q5Z5*4M7D5)7p7y7r8j7m8f7x026D5r79467J7L0C7N7P4e6=0-0I6$2f1U0u5J2g1)0(0a6P6R053q0z5L0z0y0S28680B1)773f7`3;6i4`8p6x7b7d6q7g4v6t898s8d027n8m7F8o8i6x8k8_8h6l7s7C938 958q2^988u5B8w8x4Z4#5?7K2f0B8R6S1M0r5L7S1K9n6Q6S0%0C0N6Y4+0(0h310u9r0(7S8H5Q0C0o0y0D0x0J7(6;0e0A0C0~0o0S0F1K5J8G3v0n3*0u2r2S9*3P1r3R2u2x2s0A1I9-0n3Q0_9`0!0$0'02.