Discussion :

[Mckinl3y]

Bonjour à tous, j'ai besoin de votre aide pour solutionner un algo de tri par insertion en java sur listes chaînées

merci d'avance pour votre temps et votre lecture.

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//methode qui retourne une liste des valeurs <= e
	public Liste_chaînée Less_or_equals(int e){
 
		Cellule c = tete;
		Liste_chaînée l = new Liste_chaînée();
 
		while(c!=null){
 
			if (c.valeur <= e)
				l.Cons(c.valeur); //cons ajoute une valeur en début de liste
 
			c = c.suivant;
 
		}
 
		return l;
 
	}
 
	//retourne une liste des valeurs > e
	public Liste_chaînée More_than(int e){
 
		Cellule c = tete;
        Liste_chaînée l = new Liste_chaînée();
 
		while(c!=null){
 
			if (c.valeur > e)
				l.Cons(c.valeur);
 
			c = c.suivant;
 
		}
 
		return l;
 
	}
 
	//methode qui va concaténer toutes les listes crées et triées
	public Liste_chaînée Concatener (Liste_chaînée l1, Liste_chaînée l2){
 
		Liste_chaînée l = new Liste_chaînée();
 
		if(l1 != null)
			l = l1;
 
		if (l2 != null){
 
			Cellule tmp = l2.tete;
 
			while (tmp !=null){
 
				l.Snoc(tmp.valeur);
				tmp=tmp.suivant;
			}
		}
 
		return l;
	}
 
	//methode de tri rapide
	public Liste_chaînée Tri_rapide (){
 
		if (tete == null || tete.suivant == null)
			return this;
 
		else {
 
 
		Liste_chaînée l1 = Less_or_equals(tete.valeur);
		Liste_chaînée l2 = More_than (tete.valeur);
 
		l1 = l1.Tri_rapide();
		l2 = l2.Tri_rapide();
 
 
 
		return Concatener(l1,l2);
	    }
 
	}

l'exe :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 System.out.println("\n\n* Tri rapide *");
	    Liste_chaînée l2 = new Liste_chaînée();
	    l2.Init(10); // crée une liste de 10 occurrences
	    l2.Afficher();
	    System.out.println("\nListe triee : ");    
	    l2.Tri_rapide();
	    l2.Afficher();

les classes liste et cellule sont difinies comme suit :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Cellule {
 
	public int valeur;
	public Cellule suivant;
 
	//constructeur
	Cellule(int _valeur){
 
		valeur = _valeur;
		suivant = null;
	}
 
}

et

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
public class Liste_chaînée {
 
	public Cellule tete;
 
 
	//constructeur
	 Liste_chaînée(){
 
		tete = null;
 
	}

Bien j'espère avoir mis assez de détails, étant novice en algo !

[souviron34]

Et quel est ton problème ??

[Mckinl3y]

Bonsoir, veuillez pardonner mon temps de réponse,
-> mon premier problème était :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
Liste triee : 
Exception in thread "main" java.lang.StackOverflowError
	at TD.Liste_chaînée.Tri_rapide(Liste_chaînée.java:409)
	at TD.Liste_chaînée.Tri_rapide(Liste_chaînée.java:412)
...
...
...

Après plusieurs test le soucis vient de la méthode less_or_equals, sur l'affection de c :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

Cellule c = tete.suivant; // au lieu de Cellule c = tete;

J'ai un peu de mal sur le cheminement donc je ne comprends pas pourquoi de décalage

-> second soucis : une fois le code modifié comme ci dessus, la méthode Afficher() me renvoie bien la liste mais absolument pas triée.

Merci d'avance.
Bon code