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);

[Kairos]

J'ai fait du bricolage

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 !

Je problème est toujours le même. Mais il est un peu plus délicat avec la longue tab. Quand d et g sont égaux, g est incrémenté, ma condition ne passe donc pas car g n'est pas strictement plus grand que d. Le problème est là (par exemple le 13 peut se retrouver entre deux 15). Si je lance une condition qui regarde tout simplement si droite est plus petit que la longueur de tab, alors elle provoquera dans certains cas une boucle infini. J'ai donc changé le second argument passé à ma fonction, d'une part pour éviter un stack overflow, d'autre part parce qu'il est possible que la valeur tab[g] qui a été remplacé soit plus grande qu'une des valeurs entre tab[d] et tab[tab.length]. Il est donc nécessaire de refaire un test de comparaison en repartant à la fin de la table. Dans le cas contraire on peut incrémenter g.

Je ne sais pas si j'ai été assez clair ou si je me suis emmêlé les pinceaux ou si l'algorithme est au final bien implémenté mais au moins ça marche (oui j'adore ce smiley )

Code :

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

1
2
3
4
5
 
if (droite < tab.length - 1)
    trier(tab, g, tab.length - 1);
else 
    trier(tab, g+1 , droite);

[thierryler]

Ça m’embête un peu comme solution car ça reprend la taille complète du tableau, même pour les sous liste.

[thierryler]

Bon c'est vraiment loin d'être trivial en fait. Faut se remuer les neurones (mais j'en ai peu...)

J'ai fais une version avec des listes pour vérifier. Elle n'est pas performante mais elle marche :

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
 
	@Override
	public void trier(final int[] tab) {
 
		final List<Integer> liste = tabToList(tab);
 
		final List<Integer> result = trier(liste);
 
		ecraser(result, tab);
 
	}
 
	private List<Integer> trier(final List<Integer> liste) {
 
		if (liste == null || liste.isEmpty()) {
			return new ArrayList<>();
		}
 
		// Choix du pivot a gauche
		final int pivot = liste.get(0);
		// pour ne pas traiter le pivot dans la boucle
		liste.remove(0);
 
		final List<Integer> listeGauche = new ArrayList<>();
		final List<Integer> listeDroite = new ArrayList<>();
 
		// Separation en deux sous listes
		for (final int elt : liste) {
			if (elt < pivot) {
				listeGauche.add(elt);
			} else {
				listeDroite.add(elt);
			}
		}
 
		final List<Integer> result = new ArrayList<>();
 
		result.addAll(trier(listeGauche));
		result.add(pivot);
		result.addAll(trier(listeDroite));
 
		return result;
	}

avec :

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
 
	private List<Integer> tabToList(final int[] tab) {
		final List<Integer> liste = new ArrayList<>();
 
		for (final int elt : tab) {
			liste.add(elt);
		}
 
		return liste;
	}
 
	private void ecraser(final List<Integer> from, final int[] to) {
		int i = 0;
		for (final int elt : from) {
			to[i++] = elt;
		}
	}

A noter qu'on peut faire une belle optimisation en gérant une liste au centre avec tous les pivots. Pour un millions d'éléments, je passe de 8,7 secondes à 1,4 :

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
 
private List<Integer> trier(final List<Integer> liste) {
 
		if (liste == null || liste.isEmpty()) {
			return new ArrayList<>();
		}
 
		// Choix du pivot a gauche
		final int pivot = liste.get(0);
 
		final List<Integer> listeGauche = new ArrayList<>();
		final List<Integer> listeCentre = new ArrayList<>();
		final List<Integer> listeDroite = new ArrayList<>();
 
		// Separation en deux sous listes
		for (final int elt : liste) {
			if (elt < pivot) {
				listeGauche.add(elt);
			} else if (elt == pivot) {
				listeCentre.add(elt);
			} else {
				listeDroite.add(elt);
			}
		}
 
		final List<Integer> result = new ArrayList<>();
 
		result.addAll(trier(listeGauche));
		result.addAll(listeCentre);
		result.addAll(trier(listeDroite));
 
		return result;
	}

On gagne même encore un peu en travaillant directement sur les Integer (vu qu'ils ont été créés pour passer du tableau à la liste) et en réutilisant la liste passée en paramètre plutôt qu'une nouvelle liste :

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
 
	private List<Integer> trier(final List<Integer> liste) {
 
		if (liste == null || liste.isEmpty()) {
			return new ArrayList<>();
		}
 
		// Choix du pivot a gauche
		final Integer pivot = liste.get(0);
 
		final List<Integer> listeGauche = new ArrayList<>();
		final List<Integer> listeCentre = new ArrayList<>();
		final List<Integer> listeDroite = new ArrayList<>();
 
		// Separation en deux sous listes
		for (final Integer elt : liste) {
			final int comp = elt.compareTo(pivot);
			if (comp < 0) {
				listeGauche.add(elt);
			} else if (comp == 0) {
				listeCentre.add(elt);
			} else {
				listeDroite.add(elt);
			}
		}
 
		liste.clear();
 
		liste.addAll(trier(listeGauche));
		liste.addAll(listeCentre);
		liste.addAll(trier(listeDroite));
 
		return liste;
	}

D'ailleurs c'est étrangement plus rapide avec des ArrayList que des LinkedList...

Sinon, je bloque encore sur la version pure tableau...

[joel.drigo]

Salut,

Pour la version en tableau, je proposerais la solution suivante, fondée sur le même algo (et ayant le même défaut (à mon avis), celui de modifier la liste de départ, mais qu'on peut assumer).

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
public Integer[] trier(Integer[] array) {
  if (array == null || array.length==0) {
    return new Integer[0];
  }
  return trier(array, new Integer[array.length], 0, array.length);
}
 
private Integer[] trier(final Integer[] array, final Integer[] array2, final int debut, final int fin) {
 
  // Choix du pivot a gauche
  final int pivot = array[debut]; 
  int posGauche = debut;
  int posDroite = fin;
 
  // Separation en deux sous listes
  for (int index = debut+1; index < fin; index++) {
    Integer elt = array[index];
    final int comp = elt.compareTo(pivot);
    if (comp < 0) {
    	array2[posGauche++]=elt;
    } else if (comp> 0) {
    	array2[--posDroite]=elt;
    }
  } 
 
  Arrays.fill(array2, posGauche, posDroite, pivot); // assume que la même instance est utilisée pour toutes les instances égales 
 
  if ( posGauche>debut ) {
    trier(array2, array, debut, posGauche );
    System.arraycopy(array, debut, array2, debut, posGauche-debut);
  } 
  if ( posDroite<fin ) {
    trier(array2, array, posDroite, fin);
    System.arraycopy(array, posDroite, array2, posDroite, fin-posDroite);
  }
 
  return array2;
 
}

Elle utilise un buffer de la même taille que le tableau d'origine, ce qui est gourmand certes, mais moins que la méthode en liste, puisque les trois ArrayList intermédiaires, consomment ensemble autant de mémoire de celle d'origine, plus celle due à l'allocation supplémentaire des tableaux internes.

Mais je pense que le quicksort, ce serait plutôt ça (avec un seul 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
35
36
37
38
39
public Integer[] trier(Integer[] array) {
		if (array == null || array.length==0) {
			return new Integer[0];
		}
		trier(array, 0, array.length-1);
		return array;
	}
 
	private int trier(Integer[] array, int debut, int fin, int pivot) {
		echanger(array, pivot, fin);
		int j = debut;
		for( int i=debut; i<fin; i++) {
			if ( array[i].compareTo(array[fin])<=0 ) {
		            echanger(array, i, j);
		            j ++;
			}
		}
		echanger( array, fin, j);
		return j;
	} 
 
	protected int choixPivot(Integer[] array, int debut, int fin) {
		return debut;
	}
 
	private void echanger(Integer[] array, int i1, int i2) {
		Integer temp = array[i1];
		array[i1] = array[i2];
		array[i2] = temp;
	}
 
	private void trier(Integer[] array, int debut, int fin) {
		if ( debut<fin ) {
			int pivot = choixPivot(array, debut, fin);
			pivot = trier(array, debut, fin, pivot);
			trier(array, debut, pivot-1);
			trier(array, pivot+1, fin);
		}
	}

Et le même en liste :

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
public List<Integer> trier(List<Integer> list) {
		if (list == null || list.isEmpty() ) {
			return Collections.emptyList();
		}
		trier(list, 0, list.size()-1);
		return list;
	}
 
	private int trier(List<Integer> list, int debut, int fin, int pivot) {
		echanger(list, pivot, fin);
		int j = debut;
		for( int i=debut; i<fin; i++) {
			if ( list.get(i).compareTo(list.get(fin))<=0 ) {
		            echanger(list, i, j);
		            j ++;
			}
		}
		echanger( list, fin, j);
		return j;
	} 
 
	protected int choixPivot(List<Integer> list, int debut, int fin) {
		return debut;
	}
 
	private void echanger(List<Integer> list, int i1, int i2) {
		Integer temp = list.get(i1);
		list.set(i1, list.get(i2));
		list.set(i2, temp);
	}
 
	private void trier(List<Integer> list, int debut, int fin) {
		if ( debut<fin ) {
			int pivot = choixPivot(list, debut, fin);
			pivot = trier(list, debut, fin, pivot);
			trier(list, debut, pivot-1);
			trier(list, pivot+1, fin);
		}
	}

[thierryler]

Ah royal, ça passe tous mes tests. J'ai un peu rassemblé les méthodes :

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
 
	private void trier(final int[] tab, final int gauche, final int droite) {
 
		if (droite <= gauche) {
			return;
		}
 
		// Je commence avec un pivot à gauche
		int positionPivot = gauche;
 
		// positionPivot = trier(tab, gauche, droite, positionPivot);
		permuter(positionPivot, droite, tab);
 
		// int j = gauche;
		for (int i = gauche; i < droite; i++) {
			if (tab[i] <= tab[droite]) {
				permuter(i, positionPivot++, tab);
				// positionPivot++;
			}
		}
		permuter(droite, positionPivot, tab);
		// positionPivot = j;
 
		// tri recursif des sous-listes
		// Bien entendu on ne tri pas le pivot
		trier(tab, gauche, positionPivot - 1);
		trier(tab, positionPivot + 1, droite);
	}

Par contre, sur un million d'éléments, ce n'est pas plus rapide que ma dernière version avec les listes. Et ça c'est vraiment gênant.

Qui plus est, je me rend compte que ça change l'ordre des éléments dans les sous listes.

[joel.drigo]

Pourtant c'est le cas quand je le fais moi :

- ta méthode avec les listes : 780 à 800 ms.
- ma méthode avec les tableau : 560 à 590 ms
- la seconde méthode avec une liste : 350 à 365 ms
- la seconde méthode avec un tableau : 220 à 230 ms

Je lance plusieurs fois le test suivant (ou l'équivalent avec une List) :

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
public static void main(String[] args) {
 
		int nb=1000000;
		Integer[] array = new Integer[nb];
 
		Random random = new Random(424242);
 
		for(int i=0;i<array.length; i++) {
			array[i]=random.nextInt();
		}
 
		long time = System.currentTimeMillis();
		try {
			array = new QuickSort().trier(array); 
		}
		finally {
			System.out.println(System.currentTimeMillis()-time+" ms");
		}
 
}

[thierryler]

Il faut que tu utilises tout le temps la même liste pour comparer. La mienne a été enregistrée dans un fichier à l'avance (cf. fichier joint). En fait, j'ai des dizaines de cas de test.

As-tu essayé avec la méthode que j'ai donné en dernier ?

[joel.drigo]

Le fait d'utiliser une graine identique me donne une même liste à chaque exécution.

[thierryler]

Tu veux dire quand tu fais new Random(12346) ça génère la même suite après ?

[thierryler]

Je viens de refaire des tests et ça ne change rien. Mais ça vient peut être de JUnit. Il faudrait que je fasse des tests avec un main peut être.

[joel.drigo]

En partant sur ta liste, voici mes résultats :

- 336 à 344 ms
- 255 à 265 ms
- 3654 à 3678 ms
- 2551 à 2466 ms

Un écart moindre pour les 2 premiers cas, probablement parce que la liste est plus "prétriée". Je ne m'explique pas pour l'instant, par contre cet immense écart entre les deux algos, à part une erreur de ma part quelque part

[thierryler]

Tu peux préciser à quoi correspondent tes valeurs stp. ?

Tu utilises ma version ou ta version ?

Sachant que les version finales que j'utilise sont les suivantes :

En 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
35
 
	@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 commence avec un pivot à gauche
		int positionPivot = gauche;
 
		// positionPivot = trier(tab, gauche, droite, positionPivot);
		permuter(positionPivot, droite, tab);
 
		// int j = gauche;
		for (int i = gauche; i < droite; i++) {
			if (tab[i] <= tab[droite]) {
				permuter(i, positionPivot++, tab);
				// positionPivot++;
			}
		}
		permuter(droite, positionPivot, tab);
		// positionPivot = j;
 
		// tri recursif des sous-listes
		// Bien entendu on ne tri pas le pivot
		trier(tab, gauche, positionPivot - 1);
		trier(tab, positionPivot + 1, droite);
	}

En liste :

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
	@Override
	public void trier(final int[] tab) {
 
		final List<Integer> liste = tabToList(tab);
 
		final List<Integer> result = trier(liste);
 
		ecraser(result, tab);
 
	}
 
	private List<Integer> trier(final List<Integer> liste) {
 
		if (liste == null || liste.isEmpty()) {
			return new ArrayList<>();
		}
 
		// Choix du pivot a gauche
		final int pivot = liste.get(0);
		// pour ne pas traiter le pivot dans la boucle
		liste.remove(0);
 
		final List<Integer> listeGauche = new ArrayList<>();
		final List<Integer> listeDroite = new ArrayList<>();
 
		// Separation en deux sous listes
		for (final int elt : liste) {
			if (elt < pivot) {
				listeGauche.add(elt);
			} else {
				listeDroite.add(elt);
			}
		}
 
		final List<Integer> result = new ArrayList<>();
 
		result.addAll(trier(listeGauche));
		result.add(pivot);
		result.addAll(trier(listeDroite));
 
		return result;
	}
 
	private List<Integer> tabToList(final int[] tab) {
		final List<Integer> liste = new ArrayList<>();
 
		for (final int elt : tab) {
			liste.add(elt);
		}
 
		return liste;
	}
 
	private void ecraser(final List<Integer> from, final int[] to) {
		int i = 0;
		for (final int elt : from) {
			to[i++] = elt;
		}
	}

[joel.drigo]

Les dernières valeurs sont les intervalles de mesures effectuées par exécutions successives (une dizaine pour chacun des quatre cas) correspondants au même mesures que j'ai faite dans le premier jeu de mesure, en utilisant ton fichier de valeurs appelé rand_1000000.txt et mes codes, sauf pour le tri par liste qui correspond à celui que tu as mis. Je remets les légendes :

- ta méthode avec les listes : 336 à 344 ms.
- ma méthode avec les tableau : 255 à 265 ms
- la seconde méthode avec une liste : 3654 à 3678 ms
- la seconde méthode avec un tableau : 2551 à 2466 ms

Je n'ai pas (encore) tenté avec le dernier code que tu as mis.

[joel.drigo]

Tu veux dire quand tu fais new Random(12346) ça génère la même suite après ?

Oui, comme le précise la doc (mais j'ai vérifié tu penses bien ) :

If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers