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

Fusion de deux fichiers triés

Fichiers et flux · niveau 3 (difficile)

Énoncé

Deux fichiers a.txt et b.txt contiennent chacun des entiers, un par ligne, en ordre croissant. Écrire dans fusion.txt tous ces entiers en ordre croissant, sans charger les fichiers en mémoire : on ne garde à tout instant que la ligne courante de chacun. Tester avec $1, 4, 9, 12$ et $2, 4, 10, 15, 20$ . Quel est le nombre de lectures et d'écritures, en fonction des tailles $n_{a}$ et $n_{b}$ des fichiers ?

Corrigé

On garde la ligne courante de chaque fichier (null quand il est épuisé), on écrit la plus petite des deux et l'on avance dans le fichier d'où elle vient. C'est l'étape de fusion du tri par fusion.


int ecrits = 0;
try (BufferedReader a = Files.newBufferedReader(Path.of("a.txt"));
     BufferedReader b = Files.newBufferedReader(Path.of("b.txt"));
     PrintWriter out = new PrintWriter(Files.newBufferedWriter(Path.of("fusion.txt")))) {
    String la = a.readLine(), lb = b.readLine();
    // Invariant : tout ce qui est écrit est trié et inférieur ou égal
    // aux valeurs courantes la et lb (null = fichier épuisé).
    while (la != null || lb != null) {
        if (lb == null || (la != null && Integer.parseInt(la) <= Integer.parseInt(lb))) {
            out.println(la);
            la = a.readLine();
        } else {
            out.println(lb);
            lb = b.readLine();
        }
        ecrits++;
    }
}


9 entiers écrits : 1 2 4 4 9 10 12 15 20

Chaque ligne de chaque fichier est lue une fois et écrite une fois : $n_{a} + n_{b}$ écritures et $n_{a} + n_{b} + 2$ appels à readLine (les deux derniers renvoient null). La mémoire utilisée est constante, quelle que soit la taille des fichiers. Attention à l'ordre des tests : la != null doit être vérifié avant Integer.parseInt(la).