Discussion :

[thierryler]

Salut à tous,

Je suis en train de me faire tous les algo de tri classiques, pour le plaisir, mais je bloque sur le Quick sort.

J'ai écris le code suivant :

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
44
45
46
 
public class RapideTri implements Tri {
 
	@Override
	public void trier(final int[] tab) {
 
		trier(tab, 0, tab.length - 1);
 
	}
 
	private void trier(final int[] tab, final int gauche, final int droite) {
 
		if (droite <= gauche) {
			return;
		}
 
		// Je choisi le premier element
		final int pivot = tab[gauche];
 
		int g = gauche;
		int d = droite;
 
		while (g < d) {
 
			while (g < d && tab[g] < pivot) {
				g++;
			}
 
			while (g < d && pivot <= tab[d]) {
				d--;
			}
 
			if (g < d) {
				Elements.permuter(g, d, tab);
				d--;
				g++;
			}
		}
 
		trier(tab, gauche, g);
 
		trier(tab, g+1 , droite);
 
	}
 
}

J'ai plein de jeux de tests qui passent :

Code :

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

1
2
3
4
5
6
7
8
 
final int[] tab = { 1, 7, 3, 2, 1, 3, 5, 6, 9 };
final int[] tab = { 8, 2, 3, 4, 5, 1, 7, 4, 9 };
final int[] tab = { 6, 5, 3, 2, 1, 4, 7, 8, 9 };
final int[] tab = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
final int[] tab = { 1, 2 };
final int[] tab = { 2, 1 };
final int[] tab = { 2, 1, 2 };

Mais j'ai surtout des jeux de test qui ne passent pas :

Code :

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

1
2
3
 
final int[] tab = { 0, 0, 1, 1, 1, 2, 2, 2, 3, 5, 6, 6, 11, 7, 7, 10, 8, 13, 20, 15, 15, 15, 16, 18, 30, 11, 11 };
final int[] tab = { 1, 1, 1, 2, 3, 3, 1, 1, 1 };

J'ai du m'embrouiller sur les indices mais je ne trouve pas où est mon erreur.

Quelqu'un peut m'aider ?

Merci d'avance,

[Grom61736]

Salut,

pour l'exemple

Code :

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

final int[] tab = { 1, 1, 1, 2, 3, 3, 1, 1, 1 };

Je suppose que tu avais vu tout de suite que le problème est là :

Code :

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

1
2
3
4
 
			while (g < d && pivot <= tab[d]) {
				d--;
			}

En effet, 1<= 1 donc il ne va plus considérer les éléments de droite pour le reste de l'éxécution.

Je n'ai pas d'IDE sous la main pour tester mais si tu remplaces

Code :

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

1
2
3
4
 
			while (g < d && tab[g] < pivot) {
				g++;
			}

par

Code :

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

1
2
3
4
 
			while (g < d && tab[g] <= pivot) {
				g++;
			}

?
De cette manière, les 1 de droite seront considérés quand on sera au 2 de gauche et il les mettra à la suite de tes 1 de gauche.

A+

[thierryler]

Bonjour,

Ca ne marche pas de faire une comparaison stricte :

java.lang.StackOverflowError
at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:619)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:561)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129)
at java.io.PrintStream.write(PrintStream.java:526)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)
at com.icauda.article.pgm.tri.algo.RapideTri.trier(RapideTri.java:32)
at com.icauda.article.pgm.tri.algo.RapideTri.trier(RapideTri.java:72)
...

[Kairos]

Bonjour,

J'ai essayé de debug ton programme avec cet exemple :

Code :

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

final int[] tab = { 1, 1, 1, 2, 3, 3, 1, 1, 1 };

Lorsque ton programme compare le 2 (tab[3]) au dernier 1 (tab[8]), le 2 se retrouve tout à la fin. On a donc :
{ 1, 1, 1, 1, 3, 3, 1, 1, 2 }

Après, ton algorithme fait passer les deux 1 (tab[6] et tab[7]) avant les 3. Il reste :
{ 1, 1, 1, 1, 1, 1, 3, 3, 2 }

Puis, ton programme se contente uniquement de comparer le dernier élément avec l'avant-dernier, puis les inversent. Le 2 se retrouve entre les deux 3. Et ça s'arrête là.

J'ai un peu de mal à comprendre ton l'algorithme (peut-être parce que je ne suis que débutant ).

EDIT:

A ce stade { 1, 1, 1, 1, 1, 1, 3, 3, 2 }, quand tes variables g et d sont toutes les deux à 6, ta méthode fait un appel récursif avec pour arguments les valeurs 7 et 8, donc le petit 2 n'est pas comparé avec le premier 3. Pour régler le problème il faudrait que g ne s'incrémente pas en même temps que d ne redevienne égal à tab.length !

Donc j'ai ajouté une petite condition à la dernière ligne de ta méthode :

Code :

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

1
2
3
4
5
 
if (g > d) // Si g > d et que le code continue, g < tab.length et donc d (avant d'être traité) != tab.length
    trier(tab, g , droite);
else
    trier(tab, g+1 , droite);

Le souci de ce tab est réglé. Mais il reste encore quelques erreurs avec celle-ci : final int[] tab = { 0, 0, 1, 1, 1, 2, 2, 2, 3, 5, 6, 6, 11, 7, 7, 10, 8, 13, 20, 15, 15, 15, 16, 18, 30, 11, 11 };
Je m'y penche de suite

[thierryler]

Le but de la partie avant les appels récursifs est de faire en sorte que le tableau soit scindé en deux :
* à gauche les élément strictement plus petits que le pivot
* à droite les éléments plus grands ou égaux au pivot.

[thierryler]

En partant de ta proposition, j'ai écris

Code :

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

1
2
3
4
5
6
 
if (d == g) {
	trier(tab, g + 1, droite);
} else {
	trier(tab, g, droite);
}

Que j'ai simplifié en :

Code :

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

1
2
 
trier(tab, g + d - g + 1, droite);

Puis finalement en :

Code :

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

1
2
 
trier(tab, d + 1, droite);