informatique (tronc commun des prépas scientifiques) · Chapitre 9 · Exercice de TD

L'arbre du tri fusion, en chiffres

Les tris · niveau 2

Énoncé

Décrire l'arbre des appels du tri fusion pour $n = 16$ . Combien de niveaux comporte-t-il, quel est le travail par niveau et le nombre de comparaisons dans le pire des cas ?

Corrigé

L'arbre comporte $lo g_{2} (16) = 4$ niveaux :

Niveau 0 : 1 liste de taille 16.
Niveau 1 : 2 listes de taille 8.
Niveau 2 : 4 listes de taille 4.
Niveau 3 : 8 listes de taille 2.
Niveau 4 : 16 listes de taille 1 (cas de base). Le travail de fusion à chaque niveau est proportionnel à $n = 16$ . Le nombre total de placements est de $16 \times 4 = 64$ . Le pire cas du nombre de comparaisons lors de la remontée vaut $n lo g_{2} (n) - n + 1 = 16 \times 4 - 16 + 1 = 49$ comparaisons.

Exercices semblables

Le pire cas du tri rapide, construit de ses mains corrigé
Trier des fiches — la clé de tri corrigé
Le banc d'essai des six tris corrigé
Compter les inversions en $O (n lo g n)$ corrigé
Le tri par comptage stable, et le tri par base corrigé

Le cours du chapitre · Tous les exercices du chapitre