Pourquoi la méthode Arrays.sort de Java utilise-t-elle deux algorithmes de tri différents pour différents types?

121

La Arrays.sortméthode de Java 6 utilise Quicksort pour les tableaux de primitives et le tri par fusion pour les tableaux d'objets. Je pense que la plupart du temps, Quicksort est plus rapide que le tri par fusion et coûte moins de mémoire. Mes expériences soutiennent cela, bien que les deux algorithmes soient O (n log (n)). Alors, pourquoi différents algorithmes sont-ils utilisés pour différents types?

zjffdu
la source
14
Le pire des cas de tri rapide est N ^ 2 et non NlogN.
codaddict le
Attendez, que se passe-t-il si vous avez un tableau de Integers ou quelque chose?
Tikhon Jelvis le
1
N'est-ce pas expliqué dans la source que vous avez lue?
Humphrey Bogart
5
Ces informations ne sont plus d'actualité. À partir de Java SE 7, MergeSort a été remplacé par TimSort et QuickSort a été remplacé par Dual-Pivot QuickSort . Voir ma réponse ci-dessous pour les liens vers les documents de l'API Java.
Will Byrne

Réponses:

200

La raison la plus probable: le tri rapide n'est pas stable , c'est-à-dire que les entrées égales peuvent changer leur position relative pendant le tri; entre autres, cela signifie que si vous triez un tableau déjà trié, il risque de ne pas rester inchangé.

Puisque les types primitifs n'ont pas d'identité (il n'y a aucun moyen de distinguer deux entiers avec la même valeur), cela n'a pas d'importance pour eux. Mais pour les types de référence, cela pourrait poser des problèmes pour certaines applications. Par conséquent, un tri de fusion stable est utilisé pour ceux-ci.

OTOH, une raison de ne pas utiliser le tri de fusion stable (garanti n * log (n)) pour les types primitifs peut être qu'il nécessite de faire un clone du tableau. Pour les types de référence, où les objets référencés occupent généralement beaucoup plus de mémoire que le tableau de références, cela n'a généralement pas d'importance. Mais pour les types primitifs, le clonage du tableau double carrément l'utilisation de la mémoire.

Michael Borgwardt
la source
1
Une autre raison d'utiliser le tri rapide est que dans le cas moyen, le tri rapide est plus rapide que le tri par fusion. Bien que le tri rapide fasse plus de comparaisons que le tri par fusion, il effectue beaucoup moins d'accès aux tableaux. Le tri rapide à 3 voies peut également atteindre un temps linéaire si l'entrée contient beaucoup d'entrées dupliquées, ce qui n'est pas inhabituel dans les applications pratiques (je suppose que le tri rapide à double pivot a également cette propriété).
Jingguo Yao
Pour les types primitifs, il ne clone pas le tableau, il peut les trier sur place, donc je pense que la seule raison est le contrat de stabilité, en gros ...
rogerdpack
27

Selon la documentation de l'API Java 7 citée dans cette réponse , Arrays#Sort()pour les tableaux d'objets utilise désormais TimSort , qui est un hybride de MergeSort et InsertionSort. En revanche, Arrays#sort()pour les tableaux primitifs, utilise désormais Dual-Pivot QuickSort . Ces modifications ont été implémentées à partir de Java SE 7.

Will Byrne
la source
2
Ce n'est pas une réponse, pourquoi 2 algorithmes différents ont été choisis.
Alexandr
12

Une raison à laquelle je peux penser est que le tri rapide a une complexité temporelle dans le pire des cas de O ( n ^ 2 ) tandis que le tri-fusion conserve le temps du pire des cas de O ( n log n ). Pour les tableaux d'objets, on s'attend à ce qu'il y ait plusieurs références d'objet en double, ce qui est un cas où le tri rapide est le pire.

Il existe une comparaison visuelle décente de divers algorithmes , accordez une attention particulière au graphique le plus à droite pour différents algorithmes.

msw
la source
2
Le tri rapide java est un tri rapide modifié qui ne dérive pas en O (n ^ 2), de la documentation "Cet algorithme offre des performances n * log (n) sur de nombreux ensembles de données qui entraînent une dégradation des autres quicksorts en performances quadratiques"
sbridges
7

Je suivais un cours Coursera sur les algorithmes et dans l'une des conférences, le professeur Bob Sedgewick mentionnait l'évaluation du tri système Java:

"Si un programmeur utilise des objets, l'espace n'est peut-être pas une considération cruciale et l'espace supplémentaire utilisé par un tri par fusion n'est peut-être pas un problème. Et si un programmeur utilise des types primitifs, peut-être que la performance est la chose la plus importante donc ils utilisent tri rapide."

kukido
la source
4
Ce n'est pas la raison principale. Juste après cette phrase, il y avait une question, intégrée dans la vidéo sur "Pourquoi pour les types de référence est utilisé MergeSort?" (parce que c'est stable). Je pense que Sedgewick n'a pas mentionné cela dans la vidéo pour le laisser pour question.
likern le
1

java.util.Arrays utilise Quicksort pour les types primitifs tels que int et mergesort pour les objets qui implémentent Comparable ou utilisent un Comparator . L'idée d'utiliser deux méthodes différentes est que si un programmeur utilise des objets, peut-être que l'espace n'est pas une considération cruciale et donc l'espace supplémentaire utilisé par mergesort n'est peut-être pas un problème et si le programmeur utilise des types primitifs, peut-être que la performance est la chose la plus importante, alors utilisez le tri rapide .

Par exemple: voici l'exemple lorsque le tri est important.

entrez la description de l'image ici

C'est pourquoi les tris stables ont un sens pour les types d'objet, en particulier les types d'objet mutables et les types d'objet avec plus de données que la clé de tri, et le tri par fusion est un tel tri. Mais pour les types primitifs, la stabilité n'est pas seulement sans importance. Cela n'a aucun sens.

Source: INFO

Dinesh Kumar
la source
0

La Arrays.sortméthode Java utilise le tri rapide, le tri par insertion et le tri par fusion. Il existe même un tri rapide à pivot simple et double implémenté dans le code OpenJDK. L'algorithme de tri le plus rapide dépend des circonstances et les gagnants sont: le tri par insertion pour les petits tableaux (47 actuellement choisis), le tri par fusion pour les tableaux principalement triés, et le tri rapide pour les tableaux restants afin que Array.sort () de Java essaie de choisir le meilleur algorithme pour appliquer en fonction de ces critères.

David McManamon
la source