Discussion :

[Mckinl3y]

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 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
//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 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
 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 :

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

[Flodelarab]

Bonjour

La fonction Echanger() prend en paramètres des indices alors que Echanger_2() prend en paramètres des valeurs (utilisées comme indices). Est-ce normal ?

[Mckinl3y]

En effet c'est normal, voici les codes de ces méthodes pour faire plus court :

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
//échanger deux valeurs du tableau
		void Echanger(int z, int n) {
			int tmp = tab[z];
			tab[z] = tab[n];
			tab[n] = tmp;	
		}
 
		// échanger valeurs
		void Echanger_2 (int z, int n) {
			int tmp = z;
			z = n;
			n = tmp; 
		}

merci

[Flodelarab]

Dans Echanger_2(), les variables z et n sont locales. Changer z et changer n ne servent à rien.

De plus, si tu crois que les valeurs sont échangées dans ton tableau, tu te berces d'illusion.

[Mckinl3y]

Merci pour votre réponse.

Donc en remplaçant l'appel de la fonction par le code, cela devrait fonctionner.
En effet je n'ai plus la boucle à l'infini.
Maintenant la quasi totalité du tableau est effacée et remplacée par UNE valeur.


Je ne comprends pas vraiment la notion de localité dans ce cas, car pour l'autre méthode les modifications dans le tableau s'effectuent bien.

Merci de votre lecture

[Mckinl3y]

Bien, j'ai fini par trouver la solution par tâtonnement dans le code. Le hic est que je ne comprends pas forcément le pourquoi du comment au niveau du blocage.

Niveau code ma Partition() ressemble à ceci :

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
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(deb, j);
 
			return j;
		}

Pour le Echanger(deb, j); --> j'ai tenté d'utilisé précédemment le pivot, mais cela me donnait le tableau avec valeurs modifiées comme précisé juste avant. Avec le [deb] cela fonctionne, pourtant pivot = [deb] , je ne saisis donc pas la différence.

[Flodelarab]

Je ne comprends pas vraiment la notion de localité dans ce cas, car pour l'autre méthode les modifications dans le tableau s'effectuent bien.

Car l'autre méthode travaille avec les indices! Et pas les valeurs.

Tout ce que retient l'ordinateur est un "pointeur" sur un emplacement mémoire. Que ce soit pour un objet ou pour un tableau.
tab[0] est la valeur à l'adresse de base de tab.
tab[1] est la valeur à l'adresse de base de tab repoussée d'une unité.
tab[n] est la valeur à l'adresse de base de tab repoussée de n unités.

Quand tu utilises des paramètres z, n ou tmp, il réserve d'autres emplacements mémoire.
Tu peux jouer avec les valeurs de z, n ou tmp, tant que tu veux, ton tableau n'a rien à voir. Il est à une autre place mémoire.

[Mckinl3y]

Bonjour,

Ah très bien ! je teremercie pour cette explication.
Je vais travailler tout ça.

Bonne journée