Fusionner deux linkedList [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 souhaiterais fusionner deux linkedList, de manière à ce que les éléments (des entiers) soient triés par ordre croissants.
Par exemple, si j'ai [1] et [3], j'aimerais que ma fonction merge me renvoie [1,3].

Sauf qu'actuellement, je n'ai qu'un des éléments, et j'obtiens [1], je ne vois pas pourquoi. J'ai débuggué mais je ne vois rien de spécial, pourriez-vous m'indiquer où est le problème s'il vous plaît?

Merci pour votre aide...

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

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

        while (r < listRight.size()){
            while (l < listLeft.size()){

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

                    // comparaison avec élément droit suivant
                    if ((r+1) > listRight.size()-1) { return listLeft; }
                    r = r+1; l = 0;
                }
                else{ // comparaison avec élément gauche suivant
                    r = r; l = l+1; }
            }

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

        }

        return listLeft;

    }


le test:
public static void main(String[] args) {
        // 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));


    }



fonction pour générer une linked list (au cas où) et qui se trouve dans la classe Sequence:
/**
     * 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;
    }




Configuration: Windows / Firefox 84.0

3 réponses

Messages postés
16336
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 mai 2021
2 829
Bonjour,

Tu fais référence à trop de code manquant pour que l'on puisse tester , à commencer par ta classe LinkedList...

Mais déjà, dès les premières lignes, la double boucle while est suspecte.
Si les deux listes en entrées sont triées, alors tu as juste à les parcourir toutes les deux dans l'ordre, tantôt l'une, tantôt l'autre, en alternance selon laquelle à l'élément courant le plus petit.

Exemple avec des tableaux :
public static int[] merge(int[] tab1, int[] tab2) {
    int[] tab = new int[tab1.length + tab2.length];
    for (int i = 0, i1 = 0, i2 = 0; i < tab.length; i++)
        tab[i] = (i1 < tab1.length && tab1[i1] < tab2[i2]) ? tab1[i1++] : tab2[i2++];
    return tab;
}

public static void main(String[] args) {
    int[] tab1 = { 1, 3, 5, 7 }, tab2 = { 2, 4, 6, 8 };
    System.out.println(Arrays.toString(merge(tab1, tab2)));
}
Ce qui donne bien [1, 2, 3, 4, 5, 6, 7, 8]
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
Bonjour, et merci pour ta réponse.

Les listes ne sont pas triées justement, et mes deux boucles while sont faites justement pour que je puisse comparer chaque élément de l'une avec chaque élément de l'autre.

Voilà donc tout mon code (j'avais pas tout donné car il y a des choses "inutiles" je pense, vis-à-vis de mon problème actuel).

La classe qui contient ma fonction merge qui ne marche pas (et qui inclut également la fonction main où je l'ai testé):

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 liste gauche: " + 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()){
            while (l < listLeft.size()){

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

                    // comparaison avec élément droit suivant
                    if ((r+1) > listRight.size()-1) { return listLeft; }
                    r = r+1; l = 0;
                }
                else{ // comparaison avec élément gauche suivant
                    r = r; l = l+1; }
            }

            if ((r+1) > listRight.size()-1){ return listLeft; } // 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 pour générer une suite de nombres (sous forme d'arraylist ou de linkedlist):
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);

    }



}
Messages postés
16336
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
14 mai 2021
2 829
Le principe du tri par fusion c'est de découper une liste en deux, trier la partie de gauche, trier la partie de droite, et fusionner les deux parties triées.
Donc normalement ce sont bien deux listes déjà triées que tu devrais fusionner.

Remarque : le tri par fusion est censé avoir une complexité en O(N.log(N)) mais avec une double boucle while tu vas obtenir une complexité en O(N²), ce qui n'est donc pas un tri par fusion.
Messages postés
184
Date d'inscription
lundi 14 août 2017
Statut
Membre
Dernière intervention
5 mai 2021
1
D'accord merci pour tes explications, j'ai pu corriger et finalement ça marche!

Je passe le topic en résolu.

(J'ai encore besoin de corriger d'autres choses sur ce code, donc je vais ouvrir un nouveau topic, étant donné que ce n'est pas le même problème).

Merci!