Tri rapide : récursion à l'infini
Bonjour à tous,
Je débute en algorithmie, dans un cursus de développeur j'étudie la complexité des tri sur les différentes structures de données.
Mon problème concerne le tri d'un tableau par le tri rapide; j'ai deux implémentations et je ne réussis à n'en faire fonctionner qu'une, je ne trouve pas la solution pour la seconde, même après des recherches sur différents fourms
Voilà mon code :
Code:
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
| //tri rapide
public int Partition (int deb, int fin){
int j = deb;
int pivot = tab [deb];
for (int i = deb+1; i <= fin; i++){
if (tab[i] < pivot){
j++;
Echanger(j,i);
}
}
Echanger_2 (tab[j], pivot);
return j;
}
public int Partition_2(int deb, int fin){
int val = tab[deb];
int i = deb - 1;
int j = fin + 1;
while( i < j )
{
do
{
j--;
}
while(tab[j] > val);
do
{
i++;
}
while(tab[i] < val);
if( i < j ) Echanger(i, j);
}
return j;
}
public void Tri_rapide (int deb, int fin){
if (deb < fin) {
int pivot = Partition (deb,fin); //on récupère j
Tri_rapide (deb, pivot);
Tri_rapide (pivot+1, fin);
}
} |
Mon problème vient de la méthode Partition ();
De plus la méthode Echanger() échange deux valeurs du tableau, et Echanger_2() échange 2 variables quelconques
L'appel de la fonction se fait comme suit :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| switch (choix){
case 1 : tab.Tri_minimum();
break;
case 2 : tab.Tri_maximum();
break;
case 3 : tab.Tri_insertion();
break;
case 4 : tab.Tri_bulle();
break;
case 5 : tab.Tri_rapide(1, taille-1);
break;
default : System.out.println("MAUVAISE VALEUR ENTREE !! \n");
break;
} |
et l'erreur est :
Citation:
Exception in thread "main" java.lang.StackOverflowError
at TD.Tableau.Tri_rapide(Tableau.java:268)
at TD.Tableau.Tri_rapide(Tableau.java:269)
... ...
... ...
at TD.Tableau.Tri_rapide(Tableau.java:269)
Je comprends qu'il y a un soucis au niveau du bouclage ou de l'appel, quelque chose tourne dans le vide, mais je ne le situe pas.
La méthode Partition_2() fonctionne très bien.
je demande donc votre aide,
merci d'avance
