Tri par fusion: listes non conservées [Résolu]

Signaler
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
-
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
-
Bonjour, je suis en train d'essayer de réaliser un tri par fusion. J'ai donc codé une fonction qui permet de diviser par deux une liste, puis les sous-listes en deux, et ainsi de suite, grâce à deux appels récursifs.

Cependant, lorsque je dois utiliser ma fonction merge pour fusionner les nouvelles listes ensemble, je n'ai pas le bon résultat: la fusion ne s'est pas faite. J'obtiens par exemple le résultat suivant:


[1, 4, 13, 5, 2]
liste gauche :[1, 4]
liste droite: [13, 5, 2]
liste gauche :[1]
liste droite: [4]
merge: []
liste gauche :[13]
liste droite: [5, 2]
liste gauche :[5]
liste droite: [2]
merge: []
merge: []
merge: []

Process finished with exit code 0


la classe qui contient la fonction qui me pose problème:
package com.company;

import java.util.ArrayList;
import java.util.LinkedList;

public class TriFusion {


    public static LinkedList<Integer> triFusion(LinkedList<Integer> sequence){

        LinkedList<Integer> listLeft = new LinkedList();
        LinkedList<Integer> listRight = new LinkedList();

        if (sequence.size()>1){
            // division en 2 sous listes
            int milieu = sequence.size()/2;

            // sous liste de gauche
            for (int i = 0; i < milieu; i++) {
                listLeft.add(sequence.get(i));
            }

            // sous liste de droite
            for (int i = milieu; i < sequence.size(); i++) {
                listRight.add(sequence.get(i));
            }

            System.out.println("liste gauche :" + listLeft);
            System.out.println("liste droite: " + listRight);
            listLeft = triFusion(listLeft);
            listRight = triFusion(listRight);

            listLeft = merge(listLeft, listRight);
            System.out.println("merge: " + listLeft);
        }

        else { return listLeft; }

        return listLeft;
    }





    public static LinkedList merge(LinkedList<Integer> listLeft, LinkedList<Integer> listRight){

        //index des listes
        int r = 0, l = 0;

        while (r < listRight.size()){

            if (listRight.get(r) < listLeft.get(l) || listRight.get(r) == listLeft.get(l)){
                listLeft.add(l, listRight.get(r));
                // si fin liste droite
                if ((r+1) > listRight.size()) { break; }
                // comparaison avec élément droit suivant
                r = r+1; l = 0;
            }

            else{ // comparaison avec élément gauche suivant

                // si fin liste gauche
                if ((l+1 == listLeft.size())){
                    listLeft.add(listRight.get(r));
                }
                r = r; l = l+1; }

            if ((r+1) > listRight.size()-1){ break; } // si pas d'élément suivant

        }

        return listLeft;

    }


    public static void main(String[] args) {

        // test division des listes
        LinkedList<Integer> listTest = new LinkedList();
        listTest = Sequence.linkedListGenerated(5);
        System.out.println(listTest);

        listTest = TriFusion.triFusion(listTest);
        //System.out.println(listTest);


        // test fonction merge
//        LinkedList<Integer> listLeft = new LinkedList();
//        listLeft = Sequence.linkedListGenerated(1);
//        System.out.println("LinkedList gauche a une taille de "+listLeft.size()+" : "+listLeft);
//
//        LinkedList<Integer> listRight = new LinkedList();
//        listRight = Sequence.linkedListGenerated(1);
//        System.out.println("LinkedList droite a une taille de "+listRight.size()+" : "+listRight);
//
//        System.out.println(TriFusion.merge(listLeft, listRight));


    }



}


la classe qui me permet de générer une liste d'entiers, si jamais:
package com.company;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Random;

public class Sequence {

    /**
     * permet de générer une suite
     * d'éléments aléatoires
     * et de longueur n
     */
    public static ArrayList sequenceGenerated(int n){

        ArrayList suite = new ArrayList();
        int k = 0;
        while (k<n){
            int element = new Random().nextInt(15);
            suite.add(element);
            k++;
        }
        return suite;
    }



    /**
     * permet de générer une linkedlist
     * d'éléments aléatoires
     * et de longueur n
     */
    public static LinkedList linkedListGenerated(int n){

        LinkedList list = new LinkedList();
        int k = 0;
        while (k<n){
            int element = new Random().nextInt(15);
            list.add(element);
            k++;
        }
        return list;
    }



    /** test des fonctions
     * sequenceGenerated()
     * et linkedListGenerated()
     */
    public static void main(String[] args) {

        ArrayList test = new ArrayList();
        test = sequenceGenerated(8);
        System.out.println("la liste générée est: " + test);

        LinkedList test2 = new LinkedList();
        test2 = linkedListGenerated(4);
        System.out.println("la LinkedList générée est: " + test2);

    }



}

6 réponses

Messages postés
16339
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mai 2021
2 830
Bonjour,

Il vaut mieux ne pas modifier les listes que tu passes en paramètres, parce qu'après au sein des appels récursifs tu vas encore continuer à les modifier et au final la liste que tu traites n'est plus celle que tu pensais.
À chaque méthode, créé toi une nouvelle liste pour le résultat de manière à bien isoler les données.

De plus pour mieux suivre l'enchaînement des opérations je te conseille de modifier tes affichages :

System.out.println("liste gauche : " + listLeft);
LinkedList<Integer> listLeftSorted = triFusion(listLeft);
System.out.println("liste gauche : " + listLeft + " => " + listLeftSorted);

System.out.println("liste droite : " + listRight);
LinkedList<Integer> listRightSorted = triFusion(listRight);
System.out.println("liste droite : " + listRight + " => " + listRightSorted);

LinkedList<Integer> listMerged = merge(listLeftSorted, listRightSorted);
System.out.println("merge: " + sequence + " => " +  listMerged);
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
Alors j'ai fait les modifications, et maintenant j'obtiens ceci:


[12, 2, 10, 13, 2]
liste gauche : [12, 2]
liste gauche : [12]
liste gauche : [12] => []
liste droite : [2]
liste droite : [2] => []
merge: [12, 2] => [2, 12]
liste gauche : [12, 2] => [2, 12]
liste droite : [10, 13, 2]
liste gauche : [10]
liste gauche : [10] => []
liste droite : [13, 2]
liste gauche : [13]
liste gauche : [13] => []
liste droite : [2]
liste droite : [2] => []
merge: [13, 2] => [2, 13]
liste droite : [13, 2] => [2, 13]
merge: [10, 13, 2] => [10, 2, 13]
liste droite : [10, 13, 2] => [10, 2, 13]
merge: [12, 2, 10, 13, 2] => [10, 12, 2, 2, 13]


parfois ça marche, parfois ça ne marche pas, comme ce cas là, et je ne vois pas vraiment pourquoi ma liste à la fin n'est pas triée ?



package com.company;

import java.util.ArrayList;
import java.util.LinkedList;

public class TriFusion {


    public static LinkedList<Integer> triFusion(LinkedList<Integer> sequence){

        LinkedList<Integer> listLeft = new LinkedList();
        LinkedList<Integer> listRight = new LinkedList();

        LinkedList<Integer> listLeftSorted = new LinkedList();
        LinkedList<Integer> listRightSorted = new LinkedList();
        LinkedList<Integer> listMerged = new LinkedList();

        if (sequence.size()>1){
            // division en 2 sous listes
            int milieu = sequence.size()/2;

            // sous liste gauche
            for (int i = 0; i < milieu; i++) {
                listLeft.add(sequence.get(i));
            }

            // sous liste droite
            for (int i = milieu; i < sequence.size(); i++) {
                listRight.add(sequence.get(i));
            }

            System.out.println("liste gauche : " + listLeft);
            listLeftSorted = triFusion(listLeft);
            System.out.println("liste gauche : " + listLeft + " => " + listLeftSorted); //

            System.out.println("liste droite : " + listRight);
            listRightSorted = triFusion(listRight);
            System.out.println("liste droite : " + listRight + " => " + listRightSorted); //

            listMerged = merge(listLeft, listRight);
            System.out.println("merge: " + sequence + " => " +  listMerged);

            //listMerged = merge(listLeftSorted, listRightSorted);

        }

        else { return listLeft; }

        return listLeft;
    }





    public static LinkedList merge(LinkedList<Integer> listLeft, LinkedList<Integer> listRight){

        //index des listes
        int r = 0, l = 0;

        while (r < listRight.size()){

            if (listRight.get(r) < listLeft.get(l) || listRight.get(r) == listLeft.get(l)){
                listLeft.add(l, listRight.get(r));

                // si fin liste droite => exit
                if ((r+1) > listRight.size()) { break; }

                // comparaison avec élément droit suivant
                r = r+1; l = 0;
            }

            else{ // comparaison avec élément gauche suivant

                // si fin liste gauche => ajout en fin de liste
                if ((l+1 == listLeft.size())){
                    listLeft.add(listRight.get(r));
                    r=r+1;
                }

                r = r; l = l+1; }

        }

        return listLeft;

    }


    public static void main(String[] args) {

//        // test division des listes
        LinkedList<Integer> listTest = new LinkedList();
        listTest = Sequence.linkedListGenerated(5);
        System.out.println(listTest);

        listTest = TriFusion.triFusion(listTest);
        //System.out.println(listTest);




        // test fonction merge
//        LinkedList<Integer> listLeft = new LinkedList();
//        listLeft = Sequence.linkedListGenerated(2);
//        System.out.println("LinkedList gauche a une taille de "+listLeft.size()+" : "+listLeft);
//
//        LinkedList<Integer> listRight = new LinkedList();
//        listRight = Sequence.linkedListGenerated(1);
//        System.out.println("LinkedList droite a une taille de "+listRight.size()+" : "+listRight);
//
//        System.out.println(TriFusion.merge(listLeft, listRight));


    }



}

Messages postés
16339
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mai 2021
2 830
Bonjour,

Ton problème est ici (voir mes commentaires)
            listMerged = merge(listLeft, listRight); // tu fusionnes deux listes non triées
            System.out.println("merge: " + sequence + " => " +  listMerged);

            //listMerged = merge(listLeftSorted, listRightSorted); // c'est bien ça qu'il faut mettre

        }

        else { return listLeft; } // listLeft est une liste vide ici

        return listLeft; // listLeft ne représente que la première moitié de la séquence
    }

Il faut écrire :
            listMerged = merge(listLeftSorted, listRightSorted); // fusion de deux listes triées
            System.out.println("merge: " + listLeft + " + " + listRight + " => " +  listMerged);
        }
        else { return sequence; } // liste de taille 0 ou 1 retournée à l'identique

        return listMerged; // résultat de la fusion
    }

Remarque importante : LinkedList - comme son nom l'indique - est une liste chaînée, en conséquence
list.get(i)
est une opération coûteuse : en O(N), contrairement à une ArrayList - qui se base sur des tableaux - pour lesquelles on aurait un
list.get(i)
en O(1). Donc en terme de complexité, l'utilisation intensive de
list.get(i)
sur une LinkedList est horrible, il vaudrait mieux utiliser soit une ArrayList, soit manipuler les LinkedList au travers de son Iterator.
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
Ah oui, effectivement, j'avais oublié de faire ces changements, autant pour moi!

Ça marche parfaitement, merci beaucoup pour ton aide, et pour tes explications, encore une fois !

Sinon, pour créer mes linked list en début d'algo du tri par fusion, j'imagine que cette façon de faire serait plus économe?

for (int i = 0; i < sequence.size()/2; i++) { // sous liste gauche
                listLeft.add(sequence.getFirst());
                sequence.removeFirst();
            }
            listRight = sequence; // sous liste droite, le reste
Messages postés
16339
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mai 2021
2 830
Ne modifies pas un paramètre de méthode : sequence devrait être identique au début et à la fin de méthode, sinon ça va entraîner des effets de bords bizarres.

Voici par exemple ce qui arriverait avec ton sequence.removeFirst() :
public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>(Arrays.asList(5, 4, 3, 2, 1));
    System.out.println(list); // [5, 4, 3, 2, 1]
    LinkedList<Integer> sortedList = triFusion(list);
    System.out.println(list); // [1]  ==> c'est moche !
    System.out.println(sortedList); // [1, 2, 3, 4, 5]
}
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
D'accord, du coup j'ai créé une autre Linklist, à laquelle j'ai assigné la valeur de sequence, pour pouvoir travailler avec elle sans la modifier.

Pareil avec la fonction merge.

Tout semble marcher, à l'exception qu'il me manque juste un nombre à la fin de ma fusion:

LinkedList générée :[13, 10, 13, 3, 11]
liste gauche : [13, 10]
liste gauche : [13]
liste gauche : [13] => [13]
liste droite : [10]
liste droite : [10] => [10]
merge: [] => [10, 13]
liste gauche : [] => [10, 13]
liste droite : [13, 3, 11]
liste gauche : [13]
liste gauche : [13] => [13]
liste droite : [3, 11]
liste gauche : [3]
liste gauche : [3] => [3]
liste droite : [11]
liste droite : [11] => [11]
merge: [] => [3, 11]
liste droite : [] => [3, 11]
merge: [] => [3, 13]
liste droite : [] => [3, 13]
merge: [] => [3, 10, 13, 13]
test tri par fusion: [3, 10, 13, 13]


alors que pourtant, il me semble avoir tout fait correctement ? (comme le get(i) est coûteux, j'ai modifié également ma fonction merge)

package com.company;

import java.util.ArrayList;
import java.util.LinkedList;

public class TriFusion {


    public static LinkedList<Integer> triFusion(LinkedList<Integer> sequence){

        LinkedList<Integer> listLeft = new LinkedList();
        LinkedList<Integer> listRight = new LinkedList();

        LinkedList<Integer> sequenceWork = new LinkedList();
        sequenceWork = sequence;

        LinkedList<Integer> listLeftSorted = new LinkedList();
        LinkedList<Integer> listRightSorted = new LinkedList();
        LinkedList<Integer> listMerged = new LinkedList();

        if (sequence.size()>1){
            int milieu = sequence.size()/2; // division en 2 sous listes




//            for (int i = 0; i < milieu; i++) { // sous liste gauche
//                listLeft.add(sequence.get(i));
//            }
//
//            for (int i = milieu; i < sequence.size(); i++) { // sous liste droite
//                listRight.add(sequence.get(i));
//            }



            for (int i = 0; i < sequenceWork.size()/2; i++) { // sous liste gauche

                listLeft.add(sequenceWork.getFirst());
                sequenceWork.removeFirst();

            }
            listRight = sequence; // sous liste droite, le reste


            System.out.println("liste gauche : " + listLeft);
            listLeftSorted = triFusion(listLeft);
            System.out.println("liste gauche : " + listLeft + " => " + listLeftSorted);

            System.out.println("liste droite : " + listRight);
            listRightSorted = triFusion(listRight);
            System.out.println("liste droite : " + listRight + " => " + listRightSorted);

            listMerged = merge(listLeftSorted, listRightSorted);
            System.out.println("merge: " + sequence + " => " +  listMerged);
        }

        else { return sequence; }

        return listMerged;
    }





    public static LinkedList merge(LinkedList<Integer> listLeft, LinkedList<Integer> listRight){

        //index des listes
//        int r = 0, l = 0;
//
//        while (r < listRight.size()){
//
//            if (listRight.get(r) < listLeft.get(l) || listRight.get(r) == listLeft.get(l)){
//                listLeft.add(l, listRight.get(r));
//
//                // si fin liste droite => exit
//                if ((r+1) > listRight.size()) { break; }
//
//                // comparaison avec élément droit suivant
//                r = r+1; l = 0;
//            }
//
//            else{ // comparaison avec élément gauche suivant
//
//                // si fin liste gauche => ajout en fin de liste
//                if ((l+1 == listLeft.size())){
//                    listLeft.add(listRight.get(r));
//                    r=r+1;
//                }
//
//                r = r; l = l+1; }
//
//        }
//
//        return listLeft;


        LinkedList<Integer> listLeftWork = new LinkedList();
        listLeftWork = listLeft;
        LinkedList<Integer> listRightWork = new LinkedList();
        listRightWork = listRight;
        LinkedList<Integer> listMerge = new LinkedList();

        while (listRightWork.size() != 0 & listLeftWork.size() != 0){

            // si 1 élément dans liste de droite uniquement
            if (listRightWork.size() == 1 && listLeftWork.size() == 0){
                listMerge.add(listRightWork.getFirst());
                break;
            }

            // si 1 élément dans liste de gauche uniquement
            if (listRightWork.size() == 0 && listLeftWork.size() == 1){
                listMerge.add(listLeftWork.getFirst());
                break;
            }


            if (listRightWork.getFirst() <= listLeftWork.getFirst()) {
                listMerge.add(listRightWork.getFirst());
                listMerge.add(listLeftWork.getFirst());

                listRightWork.remove(listRightWork.getFirst());
                listLeftWork.remove(listLeftWork.getFirst());
            }
            else{
                listMerge.add(listLeftWork.getFirst());
                listMerge.add(listRightWork.getFirst());

                listLeftWork.remove(listLeftWork.getFirst());
                listRightWork.remove(listRightWork.getFirst());
            }

        }

        return listMerge;

    }

    /**
     * test de la fonction merge
     * et du tri par fusion
     */
    public static void main(String[] args) {

        // test fonction merge
        LinkedList<Integer> listLeft = new LinkedList();
        listLeft = Sequence.linkedListGenerated(1);
        LinkedList<Integer> listRight = new LinkedList();
        listRight = Sequence.linkedListGenerated(1);
        System.out.println("LinkedList gauche "+listLeft+ " et droite "+listRight);

        System.out.println("test fusion des deux listes: " + TriFusion.merge(listLeft, listRight));



        // test tri par fusion
        LinkedList<Integer> listTest = new LinkedList();
        listTest = Sequence.linkedListGenerated(5);
        System.out.println("\nLinkedList générée :" + listTest);

        listTest = TriFusion.triFusion(listTest);
        System.out.println("test tri par fusion: " + listTest);


    }



}
Messages postés
16339
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mai 2021
2 830
C'est toujours le même problème, tu modifies les listes que tu passes en paramètres.

Si tu fais ça :
    public static LinkedList merge(LinkedList<Integer> listLeft, LinkedList<Integer> listRight) {
        LinkedList<Integer> listLeftWork = new LinkedList();
        listLeftWork = listLeft;

La nouvelle LinkedList créée ligne 2 ne sert à rien car l'affectation que tu fais ligne 3 la remplace. Et en réalité ce que tu fais c'est juste un changement de nom.
Si tu supprimes des données de listLeftWork ça va supprimer les données dans listLeft car les deux variables référencent le même objet, il n'y a qu'une seule liste et tu la modifies à tort.

Dans les alternatives que je te proposais ce matin, c'était soit utiliser des ArrayList, soit utiliser des Iterator, voici à quoi ça ressemblerait :

public static ArrayList<Integer> merge(ArrayList<Integer> list1, ArrayList<Integer> list2) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0, i1 = 0, i2 = 0, sz1 = list1.size(), sz2 = list2.size(), sz = sz1 + sz2; i < sz; i++) {
        if (i1 < sz1 && (i2 == sz2 || list1.get(i1) < list2.get(i2))) {
            list.add(list1.get(i1));
            i1++;
        } else {
            list.add(list2.get(i2));
            i2++;
        }
    }
    return list;
}

public static LinkedList<Integer> merge(LinkedList<Integer> list1, LinkedList<Integer> list2) {
    LinkedList<Integer> list = new LinkedList<>();
    ListIterator<Integer> it1 = list1.listIterator(), it2 = list2.listIterator();
    int n1 = it1.hasNext() ? it1.next() : 0, n2 = it2.hasNext() ? it2.next() : 0;
    for (int i = 0, i1 = 0, i2 = 0, sz1 = list1.size(), sz2 = list2.size(), sz = sz1 + sz2; i < sz; i++) {
        if (i1 < sz1 && (i2 == sz2 || n1 < n2)) {
            list.add(n1);
            i1++;
            n1 = it1.hasNext() ? it1.next() : 0;
        } else {
            list.add(n2);
            i2++;
            n2 = it2.hasNext() ? it2.next() : 0;
        }
    }
    return list;
}
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
J'aimerais vraiment utiliser les LinkedList.

Merci pour ta proposition, je vais essayer de l'implémenter.

Sinon, est-ce que le fait de faire un:
LinkedList<Integer> sequenceWork = new LinkedList(sequence);

pour cloner ma liste est une bonne idée?
Messages postés
16339
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mai 2021
2 830
Dupliquer les données est rarement une bonne idée, ça prend de la place en mémoire et du temps pour copier tous les éléments d'une liste à l'autre.
Et quitte à dupliquer les données, c'est dans une ArrayList qu'il faudrait les mettre, pour profiter des get(i), mais les dupliquer dans une autre LinkedList je ne vois vraiment pas l'intérêt.

Remarque : LinkedList peut être utilisée pour être manipulée comme une pile ou une file, mais en pratique elle n'est jamais utilisée comme une liste, elle a trop d'inconvénients.
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
Désolée pour cette réponse un peu tardive.
Finalement, j'ai pu implémenter le code avec les listIterator(), hasNext() etc, et ça a l'air de marcher très bien, merci une fois de plus pour ton aide et tes indications!
Je passe le topic en résolu!