informatique (tronc commun des prépas scientifiques) · Chapitre 9 · Application directe du cours

Dérouler une fusion

Les tris · niveau 1 (application)

Énoncé

Dérouler la fonction de fusion sur a = [1, 4, 7] et b = [2, 3, 9]. Combien de comparaisons sont effectuées ? Quelle est la borne maximale de comparaisons lors de la fusion de listes de tailles $a$ et $b$ ?

Corrigé

$(i, j) = (0, 0)$ : $1 \leq 2 ⟹ r = [1]$ , $i = 1$ .
$(i, j) = (1, 0)$ : $4 > 2 ⟹ r = [1, 2]$ , $j = 1$ .
$(i, j) = (1, 1)$ : $4 > 3 ⟹ r = [1, 2, 3]$ , $j = 2$ .
$(i, j) = (1, 2)$ : $4 \leq 9 ⟹ r = [1, 2, 3, 4]$ , $i = 2$ .
$(i, j) = (2, 2)$ : $7 \leq 9 ⟹ r = [1, 2, 3, 4, 7]$ , $i = 3$ (liste a épuisée).
Coller le reste de b : [9]. Résultat : [1, 2, 3, 4, 7, 9]. Le nombre de comparaisons est de $5$ . Pour deux listes de tailles $a$ et $b$ , le pire cas du nombre de comparaisons est $a + b - 1$ .

Exercices semblables

Compter les inversions en $O (n lo g n)$ corrigé
Le tri par comptage stable, et le tri par base corrigé
Que vaut $lo g_{2} (n!)$ ? La borne, au plus près corrigé
Deux déroulés corrigé
La stabilité, sur pièces corrigé

Le cours du chapitre · Tous les exercices du chapitre