Devoir de synthèse n°2 : tri Shell, tri par comptage, fusion de deux tableaux triés, tri des colonnes d'une matrice

Exercice 1 : le tri Shell (6 pts)

Le tri Shell est un tri par insertion appliqué d'abord aux éléments éloignés de h cases, puis avec des pas de plus en plus petits, jusqu'au pas 1 qui est un tri par insertion normal. On utilise la suite de pas 1, 4, 13, 40, … (chaque pas vaut 3h + 1) : on commence par le plus grand pas de cette suite qui est inférieur à n, puis on divise h par 3 (division entière) après chaque passe.

• 1) Donner les pas utilisés pour n = 5 et pour n = 20 (1 pt).
• 2) Écrire la procédure TriShell(T, n) qui trie T dans l'ordre croissant (3 pts).
• 3) Écrire le programme qui lit n (2 ≤ n ≤ 100, saisie contrôlée) et les n entiers, affiche les pas utilisés sur une ligne, puis le tableau trié (2 pts).

Pour n = 5 et les valeurs 9, 4, 7, 1, 3, le programme affiche :

Pas : 4 1
1 3 4 7 9

Exercice 2 : le tri par comptage (5 pts)

Les notes d'un devoir sont des entiers de 0 à 20. Pour les trier, on compte combien de fois chaque note apparaît dans un tableau C de 21 cases (C[v] = nombre d'élèves qui ont la note v), puis on réécrit les notes dans l'ordre.

• 1) Écrire la procédure Compter(T, n, C) (1 pt).
• 2) Écrire la procédure TriComptage(T, n) qui trie T dans l'ordre croissant à l'aide de C (2 pts).
• 3) Écrire la fonction Frequente(C) qui renvoie la note la plus fréquente (la plus petite en cas d'égalité) (1 pt).
• 4) Écrire le programme qui lit n (1 ≤ n ≤ 40) puis les n notes (saisies contrôlées), affiche les notes triées et la note la plus fréquente (1 pt).

Pour n = 7 et les notes 12, 8, 15, 12, 8, 20, 12, le programme affiche :

8 8 12 12 12 15 20
Note la plus fréquente : 12

Exercice 3 : fusionner deux tableaux triés (5 pts)

Deux classes ont chacune un tableau de scores (entiers de 0 à 100) trié dans l'ordre croissant : A (n éléments) et B (m éléments). On veut obtenir un seul tableau C trié de n + m éléments, sans utiliser de tri.

• 1) Écrire la procédure RemplirTrie(T, n) qui lit n entiers entre 0 et 100, chacun supérieur ou égal au précédent (saisie contrôlée) (1 pt).
• 2) Écrire la procédure Fusion(A, n, B, m, C) (3 pts).
• 3) Écrire le programme principal qui lit n et m (1 ≤ n, m ≤ 30), les deux tableaux, et affiche C (1 pt).

Pour A = 40, 55, 70 et B = 45, 50, 76, 85, le programme affiche :

40 45 50 55 70 76 85

Exercice 4 : trier les colonnes d'une matrice (4 pts)

Soit M une matrice de l lignes et c colonnes d'entiers (2 ≤ l ≤ 8, 2 ≤ c ≤ 8). On veut trier chaque colonne de M dans l'ordre croissant, de haut en bas.

• 1) Écrire la procédure TriColonne(M, l, j) qui trie la colonne j de M dans l'ordre croissant par le tri par insertion (2 pts).
• 2) Écrire la procédure AfficherMat(M, l, c) qui affiche M ligne par ligne, les éléments d'une ligne séparés par un espace (1 pt).
• 3) Écrire le programme qui lit l et c (saisies contrôlées) et les éléments de M ligne par ligne, trie toutes les colonnes et affiche M (1 pt).

Pour l = 3, c = 3 et les lignes 7 2 9, 1 8 4 et 5 3 6, le programme affiche :

1 2 4
5 3 6
7 8 9