L'arbre du tri fusion, en chiffres

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 9 — Les tris

É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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.