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
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
A voir également:
- Tri fusion java
- Waptrick java football - Télécharger - Jeux vidéo
- Jeux java itel football - Télécharger - Jeux vidéo
- Java apk - Télécharger - Langages
- Tri excel - Guide
- Java décompiler - Télécharger - Langages
6 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
26 janv. 2021 à 19:36
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 :
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);
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
26 janv. 2021 à 21:44
Alors j'ai fait les modifications, et maintenant j'obtiens ceci:
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 ?
[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)); } }
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
27 janv. 2021 à 09:56
27 janv. 2021 à 09:56
Bonjour,
Ton problème est ici (voir mes commentaires)
Il faut écrire :
Remarque importante : LinkedList - comme son nom l'indique - est une liste chaînée, en conséquence
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.
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
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?
Ç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
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
27 janv. 2021 à 14:32
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() :
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] }
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
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:
alors que pourtant, il me semble avoir tout fait correctement ? (comme le get(i) est coûteux, j'ai modifié également ma fonction merge)
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); } }
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
27 janv. 2021 à 18:47
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 :
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 :
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; }
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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
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:
pour cloner ma liste est une bonne idée?
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?
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
28 janv. 2021 à 13:39
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.
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.
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
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!
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!