Discussion :

[flyzi]

Bonjour,

cela fait 2h que je cherche à traduire en java cet algorithme sans succès :

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
 
tri(deb,fin) {
g=deb;
d=fin;
pivot=tab[deb];
 
iterer
       iterer
               sortir quand (tab[d]<=pivot)
               d=d-1;
       fin-iterer
 
       sortir quand (g=d)
       tab[g]=tab[d];
       tab[d]=pivot;
       g=g+1;
 
       iterer
               sortir quand (tab[g]>=pivot)
               g=g+1;
       fin-iterer
 
       sortir quand (g=d)
       tab[d]=tab[g];
       tab[g]=pivot;
       d=d-1;
fin-iterer
 
si (g-1>deb) alors tri(deb,g-1) finsi
si (fin>g+1) alors tri(g+1,fin) finsi
}

Voici ce que j'ai fait (comme parametre j'ai passé au départ biDirectionSort(0,n-1) avec n nombre de chiffre dans mon tableau) :

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
 
public void biDirectionSort(int start, int end)  {
			int g=start;
			int d=end;
			int pivot=tab[start];
 
 
			while((g!=d)&&(tab[d]>pivot)) {d--;}
 
			if(g!=d) {				
				tab[g]=tab[d];
				tab[d]=pivot;
				g++;
			}
 
 
			while((g!=d)&&(tab[g]<pivot)) {g++;}
 
			if(g!=d) {
				tab[d]=tab[g];
				tab[g]=pivot;
				d--;	
			}
 
			//g=d à ce stade
 
			if((g-1)>start)  {
				biDirectionSort(start,(g-1));
			}
 
			if(end>(g+1))  {
				biDirectionSort((g+1),end);
			}
		}

[tchize_]

si tu commencais par traduire l'algo en itératif au lieu de vouloir le faire directement en récursif, et si tu évitais de confondre "d=d+1" dans l'algo avec "d--;" dans la traduction?

[flyzi]

...

désolé, j'ai mal recopié l'algorithme en le mettant sur le forum. (je vais corriger ça sur l'algo de départ)
Il faut utiliser la récursivité obligatoirement.

Qu'est ce qui ne va pas sinon dans mon code java?

note : je n'ai pas le droit d'utiliser de "break"


merci d'avance.

[tchize_]

désolé, pas vu la récursivité en fin de l'algo. Donc, dans ce cas, je constate que ton alog de départ a 2 niveaux de boucles imbriquées, alors que ton code java n'en a qu'un seul, ca doit déjà être un problème à la base J'avais pas relevé parce que je pensais que ta recursivité était pour supprimer la boucle extérieure

ensuite, pas de break? C'est curieux

[flyzi]

en mettant le tout dans une même boucle, je ne peux pas vérifier deux fois si g=d et ainsi éviter les permutations....

je ne vois pas...


merci d'avance.

[unknow0]

Bonjour,

tu peux tester deux fois si g=d en mettant toute la fin du code dans un if
Mais ca risque de ne pas être tres jolis :s