Aperçu du sujet
EXERCICE 1 (6 points) Cet exercice porte sur les algorithmes de tri et la programmation en Python. On se propose dans cet exercice de se pencher sur un algorithme pour trier un tableau appelé le tri de Stooge. Pour trier les éléments situés entre les indices i et j, où
EXERCICE 1 (6 points) Cet exercice porte sur les algorithmes de tri et la programmation en Python. On se propose dans cet exercice de se pencher sur un algorithme pour trier un tableau appelé le tri de Stooge. Pour trier les éléments situés entre les indices i et j, où i < j, dans un tableau t par ce tri, on procède ainsi : • si les éléments d’indice i et j sont mal placés, on les échange ; • si il y a au moins trois éléments entre les indices i et j on trie les deux premiers tiers du tableau avec cette méthode ; o on trie les deux derniers tiers du tableau avec cette méthode ; o on trie à nouveau les deux premiers tiers du tableau avec cette o méthode. Pour réaliser ce découpage en tiers, on considère l’entier k défini par l’expression (j – i + 1) // 3, et on considère les indices intermédiaires i+k et j-k. deux premiers tiers i i+k j-k j t deux derniers tiers Voici le code partiel de l’algorithme du tri de Stooge en Python qui trie donc les éléments d’un tableau par ordre croissant. 1 def triStooge(tab, i, j): 2 if tab[i] > tab[j]: 3 echange(tab, i, j) 4 if (j - i) > 1: 5 k = (j - i + 1)//3 6 triStooge(...) 7 triStooge(...) 8 triStooge(...) 1. Écrire la fonction qui prend en arguments une liste echange(tab, i, j) Python et deux indices , et réalise sur place l’échange des valeurs tab i, j dans à ces indices. La fonction ne renvoie rien. tab 24-NSIJ2AN1 Page : 2 / 12 2. Finaliser le programme précédent en complétant les lignes 6, 7 et 8 sur votre copie. 3. Indiquer en le justifiant si cet algorithme est itératif ou récursif. Soit l’appel avec . triStooge(A, 0, 5) A = [5, 6, 4, 2, 3, 1] 4. Déterminer la valeur numérique prise par lors de ce premier appel. Une k justification est attendue. La figure ci-dessous présente l’arbre (incomplet) des appels récursifs effectués depuis l’appel . triStooge(A, 0, 5) Figure 1. Arbre des appels récursifs pour triStooge(A, 0, 5) 5. Dénombrer le nombre d’appels récursifs effectués lors du tri sans compter l’appel initial. 6. Déterminer les appels effectués dans les cases 1, 2 et 3 de cet arbre des appels récursifs. 7. Dans cette question, . Recopier le