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.

🐍 Script Python
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
  • 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
  • ❌
  • ❌
  • ✅
  • ❌
  • ✅
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"
(Shift+Esc ; 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

.128013cPw-7 sSfbgn3xk+]vei;(h4l,mjdop65_:2)=tay1/[ur050D0t0N0O0u0z0h0g0b0z0O0h0h0M010N0u0F010406050h0T0B0B0O0U0P040i0E0z0T0/0E0m050R0_0{0}0 0@0F04051f181i0R1f0@0D0u0s0%0)0+0-0)0m0l0T0O0l0t0e0F0P0N0x160g0x0u0l0x0z1K0x0N0=050Y0k0z0t1r0*0,011J1L1N1L0N1T1V1R0N0U1g1F0%120h0F0O0m0-0K011X1t010j0!0t0m0O0B0t1R1?1^1}1Z201V23250=0a0g0c0U0E0F0E0h0u150m0g0W1;0U0U0t0b2q18280m1g0R1F2D1-1/1.1S0D2a1u0u0m222n1R1o1q0(1Y2N2P0m0E2T1R0F2w1g2B2D2*0^1@2r2V1~2Z0U0|0z1R0O1I2w0j0-030I0I0b2!0t1N2Y0E0e0K0e0Q0=0Q180O2+2.0?2-292:1Z2=2@2_2{0t2}012 3133352Q38380=0K3e3g1^3i2B2M013n0O2^1g2`0x2|2~30320W3x2Z3z0n0=0n3D2A3h0@3H3l0-3K3M053O3Q3t3S3w2O3y390y0=0y3#193%3j2/1s3m0E2?3L3p3P3r3R3v3U3@3W390H0=0H3}2*3(2.3I3,473:3u3T344d37390G0=0G4j3 3)423+443o3N3q3s4r3?363z0f0=0f4A3F1j2(182T2G0D1/2L3*014s2S1p1g2%0t2)3h3$4S4s4-290u0D0-302B3z3b4H4@4_4b4t4M393b0g2e0t504s3V4v3a1R0R3f403I0p0=0W0j4/2C0g5h4#0m0j0=1-0u0I0h342x2q0I0W0b0U5n4=412W010;040w5G5q4D3J5u0O1U0t0O0T5O4C5J5L0L0J5G0@3~4S3H4 014`2.3z1{4~4^5.515b5;1|57594L3^3A2D3f0g645p5Z1~5j040j445G664m5r0=0u6d5P5J0E0d6h175*5o6k2;0k0=0U1^1A5Y6f5Q5L5N6q5H4n6u042d6z3k6B0=6D2,673m5S5U5W6K5I1~5#6j6Q0-0E0=0e6Z6A5J0B0u3c6V3I5#5%6E5)6P4m5-5/1^3X3p6`5_4u6}5624585^5a71393Y6204657d6e6L5J0m6h0I0|0o6i6E7f6W1Z6$040M6)7g2;6h5(6/6 4{3_6~5@3=4c530e3`73255~7H603`7b7e656s1Z696b5F7o7U3+0=0C7v7q6#6n042O7(6G6v6x0t6/4#6C7?5Q7i7,7.4#7s0q7}5Q6,6.6E7!5K0=0A817h6H6J856!875M7_7h6S1V6U8e6*6X0=0L5$7z8n4?7F5x5:4f7E7N52604g7L757G8C4e0e4g7R7S7e86690u5m7Z8f7{1*5V5X8u7)8g0S8i7x047%8Z6:0=0r8a1~7s020l0N0v8/6R048W8m6^7w1Z5L8$8+6g7,7k0O7m8%908-6=4k7A8w7C0e4x5?8B5`4w5|749k789h5e638N9u867{5w7l7n2*7p3I7s7u8T8o8`8*9d8+7B8y0e4O9j765 8J4O8F9p7I9P3D9v8U8k8X990-919(5R7|936M040r899G8 7#8{5T8l8Y8~8!9*9.8j959z9+5L8.9?8!9E8_9^8|9|4.8f9 9}4n7ja3a08p9:9=9B9w9$8}ae9H9)0=92ah949Aat9@8ga69K2,0R4;4T4,4V4)180N4YaN2J2E9`aK0R4W5)0W0Y0!0h04.
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"
(Shift+Esc ; 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

.128013cPw-7 sSfbgn38k]vei;(h4l,mjdo0p65_:2)=tay1/[ur050C0s0N0O0t0y0h0g0b0y0O0h0h0M010N0t0F010406050h0T0A0A0O0U0P040i0D0y0T0/0D0m050R0_0{0}0 0@0F04051f181i0R1f0@0C0t0r0%0)0+0-0)0m0l0T0O0l0s0e0F0P0N0w160g0w0t0l0w0y1K0w0N0=050Y0k0y0s1r0*0,011J1L1N1L0N1T1V1R0N0U1g1F0%120h0F0O0m0-0K011X1t010j0!0s0m0O0A0s1R1?1^1}1Z201V23250=0a0g0c0U0D0F0D0h0t150m0g0W1;0U0U0s0b2q18280m1g0R1F2D1-1/1.1S0C2a1u0t0m222n1R1o1q0(1Y2N2P0m0D2T1R0F2w1g2B2D2*0^1@2r2V1~2Z0U0|0y1R0O1I2w0j0-030I0I0b2!0s1N2Y0D0e0n0e0Q0=0Q180O2+2.0?2-292:1Z2=2@2_2{0s2}012 3133352Q380e1{040K3e3g1^3i2B2M013n0O2^1g2`0w2|2~30320W3x2Z3z0n0=0n3E2A3h0@3I3l0-3L3N053P3R3t3T3w2O3y390x0=0x3$193(3j2/1s3m0D2?3M3p3Q3r3S3v3V3^3X390H0=0H3~2*3)2.3J3-483;3u3U344e37390G0=0G4k403*433,453o3O3q3s4s3@363z0f0=0f4B3G4m3k4E3K4G474I494K3?4d4N390o0=0o4S2C1j2(182T2G0C1/2L3+014t2S1p1g2%0s2)3h3%3G054t53290t0C0-302B3z3b4I5b5d4c4u4)3a1|2e0s5k4t3W4w5o2D3f413J0p0=0W0j552C0g5z4{0m0j0=1-0t0I2O0h0s0U2q0I0W0b0U5F59422W010;040v5Z5I4W0m5M0O1U0s0O0T5+4D5$5(0L0J5Z0@3 563I5j015e2.3z3B3/0g634%5m3_3A5p245r645l5u671R0R3f0g6q5H5_1~5B040j455Z6s4n5J0=0t6z5,5$0D0d6D17605G6G2;0k0=0U1^1A5^6B4W5(5*6M5!3J0A0t3c6V4V5`0=0z6F6t3m6Q042d6*5#1~6Y6^4o5/5;5?6|4{5{5|5~6|6b0I5f393Z5i5c6j5t4v3Y6g255s4M6e7b3E6r7p6A6+2;0=0r3M0s0T0U0I0O5P0m5R2w5Y6!7r6_1Z0D0=0M6/6W5$5.041*5=5@6!6O1Z5(0S715-6D7#6,040q757W627d651^3z3{7c7k4(6e3{0g5q7^6d4f0e7?7o7q6q7X3,0=0B7O7s7K7M8a7J87046E6!5 2,7.5k790e4h7@7e7l804h7|6h7~6l4g6n6p847I5A0=0d1J1V8e6}04897H86017L04020l0N0u8K4{6%0=0E8X4W6I0=1^0C8$7Q6~1V707-7P6`0=7!8;8b8g8N2*8E4{8R0e8,1~8Z043d8_8f5%0=7+8O6:0-8R020y8V923m7u7w7y7A7C7E5S7(8?045}8j767/78664x3p777f5n4y8w7j8s7_804y5x048D7q8P7R7T8:8l8=7Y8@9s9k8M9Z0-5(9b8}8P8R7N9c9W8g9T7V9V8`99048^9?987R8|3h8~8%0=919.9@94969{3J9(7,a8778o4P8r6c8z0e4P9H6iah7g39af839P859d3K889j9e8da49|awaA3J90ax01a6ab548m6j8o4+ag6kao0e4+al8yaRaOar9Qau9S5:8/9=aK9/9^9`a)9@9}9$9^9)9 9+az9*a!9l1V9n7B5Q5S9r9w7W0R584:524=4 180N4^ba2J2Ea$b70R4?5 0W0Y0!0h04.

Crédits⚓︎

Auteurs : Nicolas Revéret, Mireille COILHAC