Fusionner deux linkedList

Résolu/Fermé
charline159 Messages postés 212 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 - 26 janv. 2021 à 16:50
charline159 Messages postés 212 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 - 26 janv. 2021 à 18:46
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

KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
26 janv. 2021 à 17:28
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]
1
charline159 Messages postés 212 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
Modifié le 26 janv. 2021 à 17:56
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);

    }



}
0
KX Messages postés 16668 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 17 mars 2023 3 004
26 janv. 2021 à 18:10
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.
0
charline159 Messages postés 212 Date d'inscription lundi 14 août 2017 Statut Membre Dernière intervention 22 juin 2022 1
26 janv. 2021 à 18:46
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!
0