Aller au contenu

Exercices

Exercice 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]\)

  • 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
Exercice 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 :

  • 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
Exercice 3 : Quel tri ?

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

Après deux itérations :

  • 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]\)
  • ❌
Exercice 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
  • La fonction tri_A met en œuvre un tri par sélection
  • La fonction tri_A met en œuvre un tri par insertion
  • La fonction tri_B met en œuvre un tri par sélection
  • La fonction tri_B met en œuvre un tri par insertion
  • La fonction tri_C met en œuvre un tri par sélection
  • La fonction tri_C met en œuvre un tri par insertion
  • La fonction tri_D met en œuvre un tri par sélection
  • La fonction tri_D met en œuvre un tri par insertion
  • ✅
  • ❌
  • ❌ Il faudrait for j in range(i + 1, len(tableau)): pour lire la dernière valeur du tableau
  • ❌
  • ❌
  • ❌ Il faudrait j = j - 1 car on prend la valeur se trouvant à gauche pour la décaler vers la droite
  • ❌
  • ✅
Exercice 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.

  • 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
  • ❌
  • ❌
  • ✅
Exercice 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 ?

🐍 Script Python
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]
  • \(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.

Exercice 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.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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

.128013S4u_7m/oc5];g26kyh3fjw:vaxr(n[=+,)-isP1p dblte050Q0U0T0z0K0S0L0P0j0S0z0L0L0F010T0K0O010406050L0d0g0g0z0B0r040b0i0S0d0/0i0D050h0_0{0}0 0@0O04051f181i0h1f0@0Q0K0y0%0)0+0-0)0D0n0d0z0n0U0J0O0r0T0s160P0s0K0n0s0S1K0s0T0=050Y0R0S0U1r0*0,011J1L1N1L0T1T1V1R0T0B1g1F0%120L0O0z0D0-0o011X1t010u0!0U0D0z0g0U1R1?1^1}1Z201V23250=0a0P0M0B0i0O0i0L0K150D0P0W1;0B0B0U0j2q18280D1g0h1F2D1-1/1.1S0Q2a1u0K0D222n1R1o1q0(1Y2N2P0D0i2T1R0O2w1g2B2D2*0^1@2r2V1~2Z0B0|0S1R0z1I2w0u0-030e0e0j2!0U1N2Y0i0J0o0J0N0=0N180z2+2.0?2-292:1Z2=2@2_2{0U2}012 3133352Q38380=0o3e3g1^3i2B2M013n0z2^1g2`0s2|2~30320W3x2Z3z0t0=0t3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390c0=0c3#193%3j2/1s3m0i2?3L3p3P3r3R3v3U3@3W390k0=0k3}2*3(2.3I3,473:3u3T344d37390p0=0p4j3 3)423+443o3N3q3s4r3?363z0f0=0f4A3F1j2(182T2G0Q1/2L3*014s2S1p1g2%0U2)3h3$4S4s4-290K0Q0-302B3z3b4H4@4_4b4t4M393b0P2e0U504s3V4v3a1R0h3f403I0q0=0W0u4/2C5h4#0w0=0P5n4=412W3J0u0=1-0K0e0L342x2q0e0W0j0B5u5p4D010;040C5M4C5x0D5A0z1U0U0z0d5T4m4#5Q0I0x5u0@3~4S3H4 014`2.3z1{4~4^5?515b5_1|57594L3^3A2D3f0P695t5U1~5j040u445u6b5(5O5W040K6i5N5x0i5r6n175/2C6j3k6l0R0=0B1^1A5%6z5x5Q5S6w5v4n6B042d6G5w1~6J6R4n5X5Z5#6V5)0=0I6p6c1Z0i0=0J6(6k5x0g0K3c6!5O5*5,6L5.2,5;5|5@1^3X3p5=3=4c530J3Y5624585}5a4u7267046a7j6y6S3m0=5C0|0A6o6L7l3I6+040F6.6H2;7o5-6V745D5^3_736 5~7f7I7a256376653`7h7k6a6q6d0=6g5L7t7X7n040v7z7m0-6s7o6v2*7u4#0D6O6D1w0U6@6I0=6K6}6/7B6n7+7v0=0G844#6;6?6L7%0-5Q0H886A0=6Q8c6)8e7~7|821*5!5$8l811Z5*5+7D8u4?7K4{4f7J7Q52654g7O7c758H4e0J4g7U7V7k8d016e0K5m7$8m3J6X1V6Z8A7,5P0=0E8p7(7*8)3I5Q0l8h6r0=020n0T0m8^8q5Y8%8t807A8w8,8.3+7o0e7q7s948*8?6`4k7E8C7H0J4x5{8G5 4w617b9p7M9m5e688S9z8U6m7p0z7r8 6*0=7y8Z8v997)8z9e0P7F8D0J4O9o7d648O4O8K9u779U3D9A8!6m8r8(9P6#048-8;7?7C9=6^0=0l8g9K959M9,934.8!5Q9;9.6l9a9c988+048@9}8*7w9J7;9B8$8saaa4aa9C9b9E9da29Lab9{9G9 91al9^7}9:ao9@a6aCad9i8c0h4;4T4,4V4)180T4YaR2J2Eaz2D4W5.0W0Y0!0L04.
Exercice 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.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
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

.128013S4u_87m/oc5];g26kyh3fjw:var(n[=,)-isP1p dblte0050P0T0S0A0J0R0K0O0k0R0A0K0K0F010S0J0N010406050K0d0h0h0A0B0s040b0j0R0d0/0j0D050i0_0{0}0 0@0N04051f181i0i1f0@0P0J0z0%0)0+0-0)0D0o0d0A0o0T0I0N0s0S0t160O0t0J0o0t0R1K0t0S0=050Y0Q0R0T1r0*0,011J1L1N1L0S1T1V1R0S0B1g1F0%120K0N0A0D0-0p011X1t010v0!0T0D0A0h0T1R1?1^1}1Z201V23250=0a0O0L0B0j0N0j0K0J150D0O0W1;0B0B0T0k2q18280D1g0i1F2D1-1/1.1S0P2a1u0J0D222n1R1o1q0(1Y2N2P0D0j2T1R0N2w1g2B2D2*0^1@2r2V1~2Z0B0|0R1R0A1I2w0v0-030e0e0k2!0T1N2Y0j0I0u0I0M0=0M180A2+2.0?2-292:1Z2=2@2_2{0T2}012 3133352Q380I1{040p3e3g1^3i2B2M013n0A2^1g2`0t2|2~30320W3x2Z3z0u0=0u3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390c0=0c3$193(3j2/1s3m0j2?3M3p3Q3r3S3v3V3^3X390l0=0l3~2*3)2.3J3-483;3u3U344e37390q0=0q4k403*433,453o3O3q3s4s3@363z0g0=0g4B3G4m3k4E3K4G474I494K3?4d4N390f0=0f4S2C1j2(182T2G0P1/2L3+014t2S1p1g2%0T2)3h3%3G054t53290J0P0-302B3z3b4I5b5d4c4u4)3a1|2e0T5k4t3W4w5o2D3f413J0r0=0W0v554/4D2W010x0=0O5F59425I0D0v0=1-0J0e2O0K0T0B2q0e0W0k0B5N5z4{0;040C5*5H2;5T0A1U0T0A0d5:4n5,0=0H0y5N0@3 563I5j015e2.3z3B3/0O674%5m3_3A5p245r685l5u6b1R0i3f0O6u5M5;1Z5B040v455N6w5}4W0D0=0J6D5+4W0j5K042O6K6x3,0Q0=0B1^1A5|4V5I5-5/645G6F5I0h0J3c6Z5P1~5-0G6R6*2;6U042d6/3J6$6}4{6H041*5_5{6(5O6~5 60626}6f0e5f393Z5i5c6n5t4v3Y6k255s4M6i7i3E6v7w6E6!5=040z3M0T0d0B0e0A5W0D5Y2w5)777y6:1Z0j0=0F6@7z3m5?5^5`704W5-0E7#5Q6I7)6;0=0m7c775z7e7g0I3{7j7r4(6i3{0O5q7{6h4f7^6r6t7x6u6L7*040w7V7Q0-7S047U7O897A6J77632,667k691^3z4h7`7l7s834h7 6l816p4g850487886S016z0x1J1V8d4o0=8c8j8K8g020o0S0n8Q4{6,0=0U8#6M6O1^0P8*8a747!7;8K7%7,7X8b8/1~8g0I8|1Z8%043d8?6^1Z5-7/8U968f0=020R8Z903,0=7C1V7F7H7J7L5Z8_0-5-618n7d8r7f6a4x3p7e7m5n4y8B7q8x7|834y5x8H8I7w8k8`8;768p9b018^957W9i8{9Y8e9W7.9h018g8i2*7P8R735@1V8=9U9Z9(047(9$9:8T9.9Q9c048 9a9_92949^9%987:a96e9x7@4P8w6g8E0I4P9G6maj7n39ah7v9O6va13K8S9*9,9*729 3h9/4{8~9*a7ac548q5k7@4+ai6oaq0I4+an8DaSaPat87aw729S9r9`9|ad71ay9}5~0499a08V7TaB9j7D9m7I5X5Z9q9v7;0i584:524=4 180S4^b82J2E9=b50i4?630W0Y0!0K04.
Exercice 9

Insertion dans une liste triée

Exercice 10

Tri de trois valeurs

Crédits⚓︎

Auteurs : Nicolas Revéret, Mireille COILHAC