Recherche:

Voici le code de mon générateur de fichier. J'avais mis un MAX à 999 en effet.



public class Generator {

private static final Logger logger = LoggerFactory.getLogger(Generator.class);
...

Je pense que T4 et T5 sont équivalents. Par contre T5 a l'avantage de ne pas créer d'autres tableaux, en ne travaillant que sur la version d'origine. Il faudrait faire le test avec 100 000 000...

As-tu testé le T5 ?

Ca y est, j'ai enfin réussi à copier la version du JDK. J'ai un peu honte de ne pas y être arrivé plus tôt.

Disons que c'est la version T5. Sur mon ordi elle explose les autres algo.

Voici ce...

Le T4 est carrément plus rapide là. Tu peux redonner le code complet ?

Oui l'autoboxing a un coût énorme, surtout dans la zone de cache des 128.

D'ailleurs c'est pour ça que je travaille avec des int[] et non pas avec des Integer[].

Instinctivement j'avais...

Comment c'est possible que RTL2 soit plus rapide que L1 alors qu'il fait le même algo avec les étapes de passage en tableau en plus ?

Moi avec Java 7.

Après d'une machine à l'autres... Mais sur une même machine, avec le même jeu de données, et en moyenne, ça devrait être différent.

J'ai essayé de reprendre le code du "sort" de Java 6 en ne prenant que la partie Quick sort mais je n'arrive pas à l'adapter :-(

Pour info, Arrays.sort() de Java 6 utilise un tri par insertion...

Ma fonction permuter est très simple :



public static void permuter(final int indexA, final int indexB, final int[] tab) {
final int temp = tab[indexA];
tab[indexA] = tab[indexB];...

Pour l'instant, ça me donne ça :

RapideTri : 1027 ms



public void trier(final int[] tab) {

trier(tab, 0, tab.length - 1);

Heu, tu peux redonner carrément le code de chaque méthode en les nommant (genre 1, 2, 3) pour qu'il n'y ait pas d’ambiguïté ? Si tu peux inclure les deux que j'ai données aussi...

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 :


@Override

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.

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

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...

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



private void trier(final int[] tab, final int gauche, final int droite) {

if (droite <= gauche) {
return;
}

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

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

En partant de ta proposition, j'ai écris



if (d == g) {
trier(tab, g + 1, droite);
} else {
trier(tab, g, droite);
}

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...

Bonjour,

Ca ne marche pas de faire une comparaison stricte :

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 :



public class RapideTri...