Discussion :

[Ceubex]

Bonjour,

Savez vous quel algorithme est utilisé lorsqu'on met en place la fonction compareTo sur un objet (tri rapide, tri Shell, etc)
Par curiosité, dans les autres langages le savez vous aussi ?

Merci d'avance

[sinok]

En java c'est un algo de type merge sort.
De souvenir en C# c'est un quicksort.
Python fait du timsort.

Pour les autres, je n'en sais rien.

[thelvin]

En même temps Comparator et compareTo() ne trient rien du tout. Ils comparent deux éléments l'un à l'autre. Deux. Pas plus, pas moins.

Ils sont appelés par l'algorithme qui se charge de trier (et ça peut être n'importe lequel. Collections.sort() utilise en effet un merge sort.)

[deathness]

Tu peux toujours allez voir dans le code source, même si ce n'est pas simple à comprendre.

[thelvin]

Tu peux toujours allez voir dans le code source, même si ce n'est pas simple à comprendre.

Pas besoin, la JavaDoc indique ce genre de choses elle-même, pour qu'on puisse évaluer la complexité de l'algorithme.

[Ceubex]

Je n'ai rien vu de tel dans la javadoc, pourtant j'ai cherché à Collections et Arrays

[deathness]

Si c'est précisé dans la description de la méthode sort par exemple:

This algorithm offers guaranteed n log(n) performance.

[deltree]

Oui, le type d'algo est dans la javadoc, un peu plus haut que le "n log(n)"

* The sorting algorithm is a modified mergesort (in which the merge is
* omitted if the highest element in the low sublist is less than the
* lowest element in the high sublist). This algorithm offers guaranteed
* n log(n) performance.

et en regardant la source en jdk6, qui est en fait dans Arrays.sort, on voit que la limite de MergeSort à insertion est à 7, donc ça trie par groupe de 7 elements maximum en tri par insertion, puis ensuite en mergesort pour les tailles supplémentaires.

Code :

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

1
2
3
4
5
6
 
    /**
     * Tuning parameter: list size at or below which insertion sort will be
     * used in preference to mergesort or quicksort.
     */
    private static final int INSERTIONSORT_THRESHOLD = 7;

[Ceubex]

C'est curieux tout de même je pensais que le tri rapide était toujours meilleur que le tri fusion. Il y a d'ailleurs une variante Sedgesort à ce tri qui j'avais cru comprendre était la meilleure de toutes

[thelvin]

Ça dépend ce qu'on appelle meilleur. Le tri fusion est stable, le tri rapide ne l'est pas.
Dans les deux cas la complexité est en moyenne n log n, le tri rapide l'est juste plus souvent.

Personnellement j'aurais pas dit non à un mécanisme pour choisir son algo de tri, pour les cas par exemple où on s'en tape de la stabilité, ou bien où elle n'a pas de sens.