Dérouler une fusion

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

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

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.