Exercices de tri

Activité 1 - Quel tri ?

On considère le tableau $[6,\,1,\,4,\,5,\,2,\,3]$. Après la première itération d'un tri, on obtient le tableau : $[1,\,6,\,4,\,5,\,2,\,3]$

Cocher la ou les affirmations correctesSolution

On a utilisé un tri par insertion
On a utilisé un tri par sélection
On a utilisé un tri par insertion ou par sélection

Lors de la première itération on échange les valeurs d'indices $0$ et $1$
Lors de la première itération on insère le minimum, a valeur $1$, à sa place correcte à gauche
C'est juste, voir les deux premières questions

Activité 2 - Quel tri ?

On considère le tableau $[6,\,1,\,4,\,5,\,2,\,3]$. Après la première itération d'un tri, on a obtenu le tableau : $[1,\,6,\,4,\,5,\,2,\,3]$. Après la deuxième itération du tri :

Cocher la ou les affirmations correctesSolution

par sélection, on obtient le tableau : $[1,\,2,\,6,\,4,\,5,\,3]$
par sélection, on obtient le tableau : $[1,\,2,\,4,\,5,\,6,\,3]$
par insertion, on obtient le tableau : $[1,\,4,\,6,\,5,\,2,\,3]$
par insertion, on obtient le tableau : $[1,\,2,\,4,\,5,\,3,\,6]$

On sélectionne la valeur minimale, le $2$ à l'indice $4$ et on l'échange avec le $6$ à l'indice $1$
Voir réponse ci-dessus
On insère la valeur d'indice $2$ au bon endroit
Voir réponse ci-dessus

Activité 3 - Quel tri ?

On considère le tableau $[5,\,4,\,3,\,2,\,1]$.

Après deux itérations :

Cocher la ou les affirmations correctesSolution

du tri par sélection on obtient le tableau : $[1,\,2,\,3,\,4,\,5]$
du tri par sélection on obtient le tableau : $[1,\,2,\,5,\,4,\,3]$
du tri par insertion on obtient le tableau : $[3,\,4,\,5,\,2,\,1]$
du tri par insertion on obtient le tableau : $[1,\,2,\,3,\,5,\,4]$

étape 1 : $[1,\,4,\,3,\,2,\,5]$, étape 2 : $[1,\,2,\,3,\,4,\,5]$
étape 1 : $[4,\,5,\,3,\,2,\,1]$, étape 2 : $[3,\,4,\,5,\,2,\,1]$

Activité 4 - Quel tri ?

On considère les fonctions suivantes dont certaines sont incorrectes.

def tri_A(tableau):
    for i in range(len(tableau) - 1):
        i_mini = i
        for j in range(i + 1, len(tableau)):
            if tableau[j] < tableau[i_mini]:
                i_mini = j
        tableau[i], tableau[i_mini] = tableau[i_mini], tableau[i]

def tri_B(tableau):
    for i in range(len(tableau) - 1):
        i_mini = i
        for j in range(i + 1, len(tableau) - 1):
            if tableau[j] < tableau[i_mini]:
                i_mini = j
        tableau[i], tableau[i_mini] = tableau[i_mini], tableau[i]

def tri_C(tableau):
    for i in range(1, len(tableau)):
        valeur_a_inserer = tableau[i]
        j = i
        while j > 0 and tableau[j - 1] > valeur_a_inserer:
            tableau[j] = tableau[j - 1]
            j = j + 1 
        tableau[j] = valeur_a_inserer

def tri_D(tableau):
    for i in range(1, len(tableau)):
        valeur_a_inserer = tableau[i]
        j = i
        while j > 0 and tableau[j - 1] > valeur_a_inserer:
            tableau[j] = tableau[j - 1]
            j = j - 1
        tableau[j] = valeur_a_inserer

Activité 5 - Coût des algorithmes

On étudie les coûts des algorithmes en fonction de la longueur des données et dans le pire des cas.

Cocher la ou les affirmations correctesSolution

Le coût du tri par sélection est linéaire
Le coût du tri par sélection est logarithmique
Le coût du tri par sélection est quadratique
Pour une entrée de grande taille, un algorithme de coût linéaire est plus avantageux qu'un algorithme de coût logarithmique
Pour une entrée de grande taille, un algorithme de coût logarithmique est plus avantageux qu'un algorithme de coût quadratique

Activité 6 - Combien d'échanges ?

On considère la fonction suivante triant un tableau. Le pire des cas de l'algorithme mis en œuvre est celui d'un tableau initialement trié dans l'ordre décroissant.

Combien d'échanges sont effectués pour trier un tableau de taille $10$ dans le pire des cas ?

def tri(tab) :
    for i in range (1, len(tab)) :
        for j in range (len(tab) - i) :
            if tab[j] > tab[j + 1] :
                tab[j], tab[j + 1] = tab[j + 1], tab[j]

Cocher la réponse correcteSolution

$10$
$45$
$55$
$100$

Lors de la première itération de la boucle principale il y aura $9$ échanges, $8$ dans la suivante puis $7$, $6$, ... $1$.

Au total il y aura donc $9+8+7+6+\dots+1=45$ échanges.

Activité 7 - Tri par sélection dans l'ordre décroissant

Compléter la fonction tri_selection_decr prenant en argument un tableau et le triant en place à l'aide du tri par sélection dans l'ordre décroissant.

Évaluations restantes : 5/5

.128013rt=7flb)1 2e/vygj:,-]swnuph5aS(o3k_i4+6P;[cdxm050S0m0c0D0K0g0w0k0R0g0D0w0w0d010c0K0A010406050w0z0U0U0D0b0p040E0G0g0z0/0G0y050n0_0{0}0 0@0A04051f181i0n1f0@0S0K0o0%0)0+0-0B0K0q0B0g1w0B0c0=050Y0h0g0m1r0*0,011v1x1z1x0c1F1H1D0c0b1g0c0B0%120w0A0D0y0-0l011J1t010f0!0m0y0D0U0m1D1$1(1-1L1:1H1?1^0=0a0k0O0b0G0A0G0w0K150y0k0W1!0b0b0m0R2d181{0y1g0n1Y2q1V1X1W1E0S1}0-1z0y1=2a1D1o1q0(1K2A0K2C0y0G2G1D0A2j1g2o2q2U0^1%2e2I1.2N0b0|0g0=0j2n2Y0?2X1|2!1L2$2(0=0l2,1(2.2o2z012?0D2)040H2`2p0@2}2;0-30320L352|2Y2~3b0=0C3e373g392 0G2%310=0N3l2/2Z1s2=3q2@040e3e1j2S182G2t0S1X2y3o0R2O1_1g3I1h3G2W192-053O0W2T3n3y0-0I0=0W0f3e0k3w3h0f0=1V0K0J0w0m1H2l0K160J0W0R0b3E383%010;040F433$2J2 3=0D1G0m0D0z4a2:45470i0s3l0k4r3.444c3)040f3q3-3/3o0y0=0K4A4u1.0G0x4E173W2{4t4b2#0h0=0b1(0q0m4k3x4c47494N2p4B450y4S04204Y2~4#4/4C4e4g4i4=4m0=0i4G4Q1L0G0=0u4~4l4c0U0K2*4`4!4|4p4%0?4s5g4P552#4E0J0|0T4F5e5i4Z4I0=0d545s2=4E4q5h4r4)4v0=4y425q5D5k040r5w2~4J4L5N4C4,4U0y4W5a1.4;5e5J5y045p2U5r5O0=0M5R4557595!4H1L470t5.4c4+0=4.5=4 0-5Z2W5?3a4@1H4_5 5j5@4|4o5A5B5g5#3(4E3,5I644d041S4h4j695x610=0Q5X5$5M6s4:0=0v5`5t04020q0c0P6E5$6p686360466v6x655%5m0D5o6T6R040v5d2U066f6*5*4?6V5n5(2-6,4551045v6l6Q4D5L6e5h6h6n6N6r6P6a6u046w6A6-6:2{70470v5_6`75714f67733X6m4778746t6n3@6/6Z7e6L0-6@6_5)706|727w6S794*5l7v7I5b6#7g7C6m7E7k6q7G776Z6|7b4(7o6C3v0n3Z0m2q2R7*3H1p3J2t2w2r7T2q3I0@0n0W0Y0!0w04.

Activité 8 - Tri par insertion dans l'ordre décroissant

Compléter la fonction tri_insertion_decr prenant en argument un tableau et le triant en place à l'aide du tri par insertion dans l'ordre décroissant.

Évaluations restantes : 5/5

.128013rt=7flb)1 2e/vygj:,-]8swnuph5aS(o3k_i46P;[cdm0050S0m0c0E0L0g0x0k0R0g0E0x0x0d010c0L0B010406050x0A0T0T0E0b0p040F0H0g0A0/0H0z050n0_0{0}0 0@0B04051f181i0n1f0@0S0L0o0%0)0+0-0C0L0q0C0g1w0C0c0=050Y0h0g0m1r0*0,011v1x1z1x0c1F1H1D0c0b1g0c0C0%120x0B0E0z0-0l011J1t010f0!0m0z0E0T0m1D1$1(1-1L1:1H1?1^0=0a0k0O0b0H0B0H0x0L150z0k0W1!0b0b0m0R2d181{0z1g0n1Y2q1V1X1W1E0S1}0-1z0z1=2a1D1o1q0(1K2A0L2C0z0H2G1D0B2j1g2o2q2U0^1%2e2I1.2N0b0|0g0=0j2n2Y0?2X1|2!1L2$2(0=0l2,1(2.2o2z012?0E2)040I2`2p0@2}2;0-30320M352|2Y2~3b0=0D3e373g392 0H2%310=0N3l2/2Z1s2=3q2@040e3v383y3a3A3s040w3e1j2S182G2t0S1X2y3o0R2O1_1g3Q1h3O2W192-053W0W2T3n3G010J0=0W0f3e0k3w3h0f0=1V0L0K2L0x0m0b2d0K0W0R0b3M3F2J010;040G4a3.4c0z3}0E1G0m0E0A4h2:3/4e0i0s3l0k4y3_4b1.3;040f3q3^3`3o4k040L4H4B1L0H0y0=2L4N4i2#0h0=0b1(0q0m4r3x4c4e4g3(2{4I3/0T0L2*4%2~4e0t4U4s4j4X04204?3o4*503/4K1S4o4q4,2p4.4)0=0i4v4x4z5h5b2#0=0o310m0A0b0K0E400z422j4959044A4V4P0=0d4`4(5k04564p535c040Q5L5H4M5y5j1L4e0v5g5h4y5T3a0=0r5F2~0H5D5(4J4S5X5Y5!3:0=0y1v1H5,545$5`4c5*04020q0c0P5}1.4:0=0U654P4R041(0S6a5#5I4m1H5K5S4O0-4e5O6m5B6h5%5y5A4{1.5 0u6g0167042+6r6x5U0=5W6v5;5 020g636B4K5m1H5p5r5t5v435P6I044w5y065Y6*6w5G2=4l4n6l2W6n4d0=6q6=6s2 5|6G6-6o6J6B5 5E6L6?556j576!705N7a6|046u2U6,5)0=6A756{6D6F6`6H7b6K2U6)6+5i766}7h6M5+7m7r7e7g2-7i3o6z6B7o5/7x6{776:587q6 6@7c6~3h7z3)6?5V727C7A7y046T5o5q5s41436Z6(183+0m2q2R7_3P1p3R2t2w2r782q3Q0@0n0W0Y0!0x04.

Activité 9 - Tri de couples de valeurs

Le secrétariat d'un collège souhaite établir la liste de ses élèves triée par niveau puis par ordre alphabétique.

Il veut ainsi obtenir une liste dans laquelle :

on rencontre tout d'abord les élèves de 6ème puis ceux de 5ème, de 4ème et enfin ceux de 3ème,
au sein de chaque niveau, les élèves sont triés dans l'ordre alphabétique de leur nom.

Chaque élève est décrit par un tuple Python dans lequel la première valeur est le niveau dans lequel il est scolarisé (entier allant de 3 à 6) et la seconde son nom (une chaîne de caractères).

On se propose d'utiliser le tri par sélection.

Par exemple :

>>> eleves = [
...     (4, "Targeur Samia"),
...     (5, "Blennie Aymeric"),
...     (5, "Alose Tom"),
...     (6, "Targeur Samir"),
... ]
>>> tri_eleves(eleves)
>>> eleves
[(6, 'Targeur Samir'), (5, 'Alose Tom'), (5, 'Blennie Aymeric'), (4, 'Targeur Samia')]

On rappelle que Python trie nativement les chaînes de caractères dans l'ordre lexicographique :

>>> "Alose Tom" < "Blennie Aymeric"
True
>>> "Targeur Samia" > "Targeur Samir"
False

Compléter les fonctions indice_minimum_depuis et tri_eleves ci-dessous afin d'effectuer le tri souhaité à l'aide du tri par sélection.

Évaluations restantes : 5/5

.128013rt=7flb)1 2e/vygj:,-]8sw9nuph5aS(o3k_i4+6P;[cdm0050U0m0c0F0M0g0x0k0T0g0F0x0x0d010c0M0C010406050x0B0V0V0F0b0p040G0I0g0B0;0I0A050n0{0}0 110_0C04051h1a1k0n1h0_0U0M0o0)0+0-0/0D0M0q0D0g1y0D0c0@050!0h0g0m1t0,0.011x1z1B1z0c1H1J1F0c0b1i0c0D0)140x0C0F0A0/0l011L1v010f0$0m0A0F0V0m1F1(1*1/1N1=1J1^1`0@0a0k0Q0b0I0C0I0x0M170A0k0Y1$0b0b0m0T2f1a1}0A1i0n1!2s1X1Z1Y1G0U1 0/1B0A1@2c1F1q1s0*1M2C0M2E0A0I2I1F0C2l1i2q2s2W0`1)2g2K1:2P0b0~0g0@0k0j2p2!0^2Z1~2$1N2(2*2,0l2/1*2;2q2B012_0F2+040k0J2}2r0_302@0/33350k0N392 2!313f2,0E3j3b3l3d320I2)342,0P3q2=2#1u2^3v2`360e3A3c3D3e3F3x360w3J3s3L3u3w3g0z3R2?3T3n040j0W3Y3C2L3U3G0j2.1b2:3r3Z3+3#0j2|3:2~3=3*2%3N350j383{3a3B3m400@0j3i443k3?3 3V493p4c1l2U1a2I2v0U1Z2A3t0T2Q1{1i4n1j4l2Y4j4t0Y2V3S3+0K0@0Y0f3j0k463t0A0f0@2N1q0T0m0L0V2N0M0V0|0L0Y0C0B0M0x3j4N3T0?040H4,3K3@0@1U0m0F0B4=4F1:4/0t4L4-4@040M4}4e1N4/0i0s3q0k5e4M4?2%4R4W4Y525h1N0I0@0d5m4~2^4R5d5f531:4H040f3v5s583e0@0r5E3~5o0y4R194c5g5t3e0h0@0b1*0q0m575K0/4/4;4j5n5G555J315p040O5,3t4X495Z31505;3!5T04225^3t5$603!4^0F1I4`4|5(5R015a5b5w5f5x5)015A0M4K5P5y5u044_4{633+4/0S6t5i045I6a5F6c0@0v6w6B5!015?043(6H5_6E5{3+5.020q0c0R6Q6y6r692Y6i6v6x6p0M5k0A566N616E6G6#6b6K6M6=6C4/0v5c4c066g706h6b0A5j4X6,6X5o5q785*6A2W6 715Q6C5A0m1B6m2W7h6I746q661J6s6.4.0@6;2:6o7c6(5#6:7C6J0M0@6^7z6$6P6n6i5.0d5r7N7365677u6_6I6%7v546*766-7X6O046F7F6@7F6{6}7e7g707A6j4R7m2:7o3m7U7t6!7K6b7Z7)4O5H7/7E7!1:6K3/857w7+7b016S0g6V8h7q6Z88047y2~7^7q7$5l8a59898e3+8c8p6|6f7?7@6i8u6+7(7|7^7P8m876~6g7^5A2l0c0B0b5O7n8t758w7e063}315A4J8m4Q6q0b6*7k0m0o0m4+8x7D4:7F8n7s688p6e8R727i0@5C0b8P5+7S6C0I5M558Z8M8I5}5V0A5X8p5%8A2%5}5 8{6D8}9u8 7V818s7L040i8h5.0u8h8C9u5a7;3;7?8#558K9F7a9c7p5N4T4V7%4!0V4$0m4(4*9o8~7 919K0@519U7~9b9q8y9D8F8S8I9,7W826`7x9+9?9 7Y6E9:8!9|7r9z8p8r2r9P8v779.8g9;3t8Oak64aa80aca2ag8L9B83a69a8oaiad4E6C8u8D3A0n4C0m2s2TaJ4m1r4o2v2y2t902s4n0_0n0Y0!0$0x04.