Aperçu du sujet
EXERCICE 1 : Algorithmes de tri (4 points) Cet exercice traite principalement du thème « algorithmique, langages et programmation ». Le but est de comparer le tri par insertion (l'un des algorithmes étudiés en 1ère NSI pour trier un tableau) avec le tri fusion (un algorithme qui applique le principe
EXERCICE 1 : Algorithmes de tri (4 points) Cet exercice traite principalement du thème « algorithmique, langages et programmation ». Le but est de comparer le tri par insertion (l'un des algorithmes étudiés en 1ère NSI pour trier un tableau) avec le tri fusion (un algorithme qui applique le principe de « diviser pour régner »). Partie A : Manipulation d’une liste en Python 1. Donner les affichages obtenus après l’exécution du code Python suivant. notes = [8, 7, 18, 14, 12, 9, 17, 3] notes[3] = 16 print(len(notes)) print(notes) 2. Écrire un code Python permettant d'afficher les éléments d'indice 2 à 4 de la liste notes. Partie B : Tri par insertion Le tri par insertion est un algorithme efficace qui s'inspire de la façon dont on peut trier une poignée de cartes. On commence avec une seule carte dans la main gauche (les autres cartes sont en tas sur la table) puis on pioche la carte suivante et on l'insère au bon endroit dans la main gauche. 1. Voici une implémentation en Python de cet algorithme. Recopier et compléter les lignes 6 et 7 surlignées (uniquement celles-ci). 1 def tri_insertion(liste): 2 """ trie par insertion la liste en paramètre """ 3 for indice_courant in range(1,len(liste)): 4 element_a_inserer = liste[indice_courant] 5 i = indice_courant - 1 6 while i >= 0 and liste[i] > : 7 liste[ ] = liste[ ] ........... ........... 8 i = i - 1 9 liste[i + 1] = element_a_inserer On a écrit dans la console les instructions suivantes : notes = [8, 7, 18, 14, 12, 9, 17, 3] tri_insertion(notes) print(notes) On a obtenu l'affichage suivant : [3, 7, 8, 9, 12, 14, 17, 18] 21-NSIJ2PO1 2/15 On s'interroge sur ce qui s’est passé lors de l’exécution de tri_insertion(notes). 2. Donner le contenu de la liste notes après le premier passage dans la boucle for. 3. Donner le contenu de la liste notes après le troisième passage dans la boucle for. Partie C : Tri fusion L'algorithme de tri fusion suit le principe de « diviser pour régner ». (1) Si le tableau à trier n’a qu’un élément, il est déjà trié. (2) Sinon, séparer le tableau en deux parties à peu près égales. (3) Trier les deux parties avec l’algorithme de tri fusion. (4) Fusionner les deux tableaux triés en un seul tableau. source : Wikipedia 1. Cet algorithme est-il itératif ou