Discussion :

[LenyEdwarx]

Bonjour à tous,

Je me remets depuis peu au langage JAVA et suis confronté à une erreur Stack OverFlow lorsque je lance mon code de Tri Rapide. J'ai un peu du mal à comprendre ce qui cloche dans mon code. A priori, je dirais qu'il part en boucle infinie et finit par planter mais je ne comprends pas pourquoi il part dans une boucle infinie. Pourriez-vous m'éclairer svp ? Merci d'avance.

Voici mon code:

Code :

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
public class ClassMain {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] tab = {15,15,17,3,8,11,28,6,55,7};
		TriRapide(tab,0,tab.length-1);
 
	}
 
	public static void TriRapide(int[] tab, int deb, int fin)
	{
		if (fin>deb)
		{
		int ind_pivot = Partition(tab, deb, fin);
		TriRapide(tab,deb,ind_pivot);
		TriRapide(tab,ind_pivot+1,fin);
		}
	}
 
	public static int Partition(int[] tab, int a, int b)
	{
		int pivot = tab[a];
		int i=a;
 
		for (int j=a+1;j<=b;j++)
		{
			if (tab[j]<pivot)
			{
				i++;
				int temp = tab[i];
				tab[i] = tab[j];
				tab[j] = temp;
 
			}
		}
		i++;
		tab[a] = tab[i];
		tab[i] = pivot;
 
 
		return i;
	}
}

Voici le message d'erreur :

Exception in thread "main" java.lang.StackOverflowError
	at sun.nio.cs.SingleByteEncoder.encodeArrayLoop(Unknown Source)
	at sun.nio.cs.SingleByteEncoder.encodeLoop(Unknown Source)
	at java.nio.charset.CharsetEncoder.encode(Unknown Source)
	at sun.nio.cs.StreamEncoder.implWrite(Unknown Source)
	at sun.nio.cs.StreamEncoder.write(Unknown Source)
	at java.io.OutputStreamWriter.write(Unknown Source)
	at java.io.BufferedWriter.flushBuffer(Unknown Source)
	at java.io.PrintStream.write(Unknown Source)
	at java.io.PrintStream.print(Unknown Source)
	at java.io.PrintStream.println(Unknown Source)
	at ClassMain.TriRapide(ClassMain.java:13)
	at ClassMain.TriRapide(ClassMain.java:17)
	at ClassMain.TriRapide(ClassMain.java:17)

Merci d'avance pour votre aide.

[joel.drigo]

Salut,

Il y a un i++ de trop (celui en dehors de la boucle, ligne 36 dans le code de ton message), qui fait qu'on atteint jamais la condition de fin de récursivité (fin<=deb). La StackOverFlowError indique justement qu'on a consommé toute la pile disponible, ce qui arrive en cas de récursivité "infinie".

[LenyEdwarx]

Merci Joël pour ta réponse. En effet, maintenant que tu le dis, il semble que ce i++ ligne 36 ne devrait pas être là.
Je teste ça ce soir .


Je viens de refaire le cheminement sur papier et j'arrive à me convaincre que ce i++ ne doit pas être là. Néanmoins, j'ai du mal à comprendre pourquoi cela empêche d'atteindre ma condition (deb<fin).

Merci pour ton aide !