Sujet Précédent Sujet Suivant

Tri par fusion: listes non conservées

Résolu/Fermé
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 - 26 janv. 2021 à 19:02
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 - 2 févr. 2021 à 10:50
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);

    }



}
A voir également:

6 réponses

Réponse 1 / 6
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
26 janv. 2021 à 19:36
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);
0
Réponse 2 / 6
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
26 janv. 2021 à 21:44
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));


    }



}
0
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
27 janv. 2021 à 09:56
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.
0
Réponse 3 / 6
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
27 janv. 2021 à 12:19
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
0
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
27 janv. 2021 à 14:32
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]
}
0
Réponse 4 / 6
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
Modifié le 27 janv. 2021 à 17:05
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);


    }



}
0
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
27 janv. 2021 à 18:47
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;
}
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 6
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
28 janv. 2021 à 11:34
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?
0
KX Messages postés 16733 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 janvier 2024 3 015
28 janv. 2021 à 13:39
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.
0
Réponse 6 / 6
charline159 Messages postés 208 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
2 févr. 2021 à 10:50
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!
0

Discussions similaires

TELECHARGER DES JEUX JAVA
undertaker3 -
neogenesis -

1 réponse
telecharger des jeux java
benboudjema -
benboudjema -

2 réponses
telecharger bible louis second java pour itel
charl -
madmyke -

1 réponse
A java exception has occurred minecraft
moi83310 -
NathLeBg -

14 réponses
Où télécharger des jeux java gratuits ?
chris1501 -
narcisse -

2 réponses