-------------------------------------------------------- CORRECTION TYPE EXAM - TECH. ALGO. & PROG. - AVRIL 2017 C. GAVOILLE -------------------------------------------------------- Q1. Problème: "Le Tri" o Entrée: un tableau de n éléments o Sortie: le tableau où les éléments ont été ordonné Q2. Tri fusion: on coupe en deux moitiés le tableau, on tri chaque moitié récursivement, puis on les fusionne en temps linéaire. Q3. La complexité est en O(nlogn). Q4. A1 = {5,3,1,2,4} et A2 = {5,1,3,2,4} Oui, il existe toujours un minimum local. Le plus petit élément est nécessairement un minimum local, ses éléments adjacents étant nécessairement supérieurs (et strictement car tous différents). Q5. Il y a plusieurs algorithmes possibles. En voici un: int algo_naif(int *A,int n){ if( n==1 || A[0]A[i] && A[i]0 et A[m-1]