Fusion de deux tableaux triés — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 5)

Fusion de deux tableaux triés

Tableaux · niveau 2

Énoncé

Écrire static int[] fusion(int[] a, int[] b) qui reçoit deux tableaux triés par ordre croissant et retourne un nouveau tableau, trié, contenant toutes leurs valeurs. On n'utilisera pas Arrays.sort : on parcourra les deux tableaux une seule fois, en prenant à chaque étape la plus petite des deux valeurs en tête.

Corrigé


static int[] fusion(int[] a, int[] b) {
    int[] r = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;                 // prochaines cases de a, b et r
    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) r[k++] = a[i++];
        else r[k++] = b[j++];
    }
    while (i < a.length) r[k++] = a[i++];    // reste de a
    while (j < b.length) r[k++] = b[j++];    // reste de b
    return r;
}

L'expression r[k++] = a[i++] range a[i] dans r[k], puis augmente k et i de $1$ (l'opérateur ++ placé après la variable donne l'ancienne valeur, puis l'incrémente). Quand l'un des tableaux est épuisé, il suffit de recopier le reste de l'autre, déjà trié. Pour {1, 4, 9} et {2, 3, 10, 12} : [1, 2, 3, 4, 9, 10, 12]. Chaque valeur est recopiée une seule fois : le travail est proportionnel à la somme des longueurs. C'est l'étape centrale du tri par fusion.