Quel est l'algorithme de tri pour Java [fermé]

Collections.sort() utilise une version modifiée de mergesort. Arrays.sort() utilise une variante de quicksort pour les primitives et mergesort pour le tri Object.

Pour Java 7, lisez le commentaire de @SebastianPaaskeTørholm ci-dessous

OK essayer de trouver la liste canonique. Fondamentalement, le contrat est que Collections.sort doit être un tri "stable" (c'est-à-dire que les éléments égaux ne seront pas réorganisés), où Arrays.sort (pour les tableaux de type natif) peut les réorganiser, car ils sont identiques, donc il a plus de liberté d'utiliser différents algorithmes (c'est-à-dire plus rapides). La justification de vouloir un contrat stable est donnée ici. En outre, il est présumé que la comparaison d'objets (par rapport aux natifs) est "beaucoup plus chère" (c'est généralement le cas), donc un objectif secondaire pour Collections.sort est de minimiser le nombre de comparaisons, et être stable.

Pour toutes les versions, Collections.sorteffectue initialement une copie de la liste (dans un tableau), la modifie, puis copie les éléments triés dans la liste initiale, pour éviter O(n^2) complexité pour trier les listes chaînées. Devinez qu'ils pensaient que la copie supplémentaire ne serait pas trop chère car il ne s'agit que de copier des références, pas des valeurs réelles (?).

Dans JDK 6:

Les Tableaux de types natifs: à l'écoute quicksort

 * The sorting algorithm is a tuned quicksort, adapted from Jon
 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
 * 1993).  This algorithm offers n*log(n) performance on many data sets
 * that cause other quicksorts to degrade to quadratic performance.

Il a été jugé que le comportement quadratique du "pire des cas" O(n^2) n'était pas un problème pour ce quicksort modifié.

Quicksort lui-même a été choisi pour performance.

Liste des Objets: modifié mergesort

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

"Il est un tri stable raisonnablement rapide qui garantit les performances O(n log n) et nécessite O(n) d'espace supplémentaire."

Il est également par défaut un tri d'insertion pour small tableaux .

JDK 7:

Tableaux de types natifs: tri rapide à double pivot

 * ...The sorting algorithm is a Dual-Pivot Quicksort
 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
 * offers O(n log(n)) performance on many data sets that cause other
 * quicksorts to degrade to quadratic performance, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.

"Le nouvel algorithme réduit, le nombre moyen de swaps de 20%."

Il y a aussi certains seuils où si la taille est "inférieure à x", il fera simplement un tri de comptage, un tri d'insertion ou un tri rapide au lieu du "tri rapide à double pivot."(selon le type de primitive triée) https://stackoverflow.com/a/41129231/32453

Liste des Objets: Timsort une sorte de hybride fusion/le tri par insertion.

"C'est un mergesort stable, adaptatif et itératif qui nécessite beaucoup moins de n comparaisons de log(n) lorsqu'il est exécuté sur des tableaux partiellement triés, tout en offrant des performances comparables à un mergesort traditionnel lorsqu'il est exécuté sur des tableaux aléatoires. Comme tous les mergesorts appropriés, timsort est stable et s'exécute en temps O(n log n) (pire cas). Dans dans le pire des cas, timsort nécessite un espace de stockage temporaire pour n/2 références d'objet; dans le meilleur des cas, il ne nécessite qu'une petite quantité constante d'espace. Contrastez cela avec l'implémentation actuelle, qui nécessite toujours un espace supplémentaire pour n références d'objets, et ne bat n log n que sur des listes presque triées."

"Sur des données hautement ordonnées, ce code peut s'exécuter jusqu'à 25 fois plus vite que l'implémentation actuelle."

"1) Garanti O(n*log(n)) ou moins les comparaisons avec une faible constant. 2) Exactement n-1 comparaisons pour les données pré-triées (ou révisées). 3) Tri stable."

Vous pouvez revenir à l'utilisation de LegacyMergeSort avec un env. paramètre.

JDK 8:

Tableaux de types natifs: quicksort à double pivot , avec quelques petites modifications sur jdk 7 (quoi?).

Liste des objets: Timsort (same)

Tri parallèle: ???

JDK 9:

Les Tableaux de types natifs: quicksort à double pivot , avec au moins quelques petites modifications donc si les données sont "principalement ordonnées", il suffit de faire un tri de fusion modifié dessus.

Liste des Objets: Timsort (même)

Tri Parallèle: ???

JDK 10:

Tableaux de types natifs: quicksort à double pivot , quelques modifications ont étéproposées .

Liste des objets: Timsort (same)

Tri parallèle: ???

Ceci est un wiki communautaire n'hésitez pas à le mettre à jour et/ou à l'élaborer.