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

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

Source

2010-09-14 zjffdu

+11

Le cas le plus défavorable de Quicksort est N^2 non NlogN. – codaddict

Attendez, que se passe-t-il si vous avez un tableau de 'Integer's ou quelque chose? –

N'est-ce pas expliqué * dans * la source que vous avez lue? –

146

La raison la plus probable: quicksort n'est pas stable, c'est-à-dire que des entrées égales peuvent changer leur position relative pendant le tri; entre autres choses, cela signifie que si vous triez un tableau déjà trié, il ne peut 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 causer des problèmes pour certaines applications. Par conséquent, un tri de fusion stable est utilisé pour ceux-ci. OTOH, une raison pour ne pas utiliser le tri de fusion (garanti n * log (n)) pour les types primitifs pourrait ê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 aucune importance. Mais pour les types primitifs, le clonage du tableau double l'utilisation de la mémoire.

Source

2010-09-14 08:33:18

Une autre raison d'utiliser quicksort est que dans le cas moyen, quicksort est plus rapide que mergesort. Bien que quicksort fasse plus de comparaison que mergesort, il fait beaucoup moins d'accès au tableau. 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 (j'imagine que le tri rapide à double pivot a également cette propriété). –

Une raison pour laquelle je peux penser est que quicksort a une complexité dans le pire temps de cas de O (n^2 ) tandis que mergesort conserve le pire temps de cas de O (n log n). Pour les tableaux d'objets, il existe une attente raisonnable qu'il y aura plusieurs références d'objet en double, ce qui est un cas où le tri rapide fait le plus mauvais.

Il y a un décent, faites particulièrement attention au graphique le plus à droite pour différents algorithmes.

Source

2010-09-14 08:33:36 msw

+1 pour mon site préféré sur internet pour aujourd'hui. –

Le quicksort java est un quicksort modifié qui ne dérive pas à O (n^2), des docs "Cet algorithme offre des performances n * log (n) sur de nombreux jeux de données qui dégradent les performances en performances quadratiques" – sbridges

" Sur de nombreux ensembles de données "n'est pas la même chose que" sur tous "... – Puce

je prenais classe Coursera sur les algorithmes et dans l'une des conférences Professeur Bob Sedgewick mentionnant l'évaluation pour le tri Java système:

« Si un programmeur utilise des objets, peut-être l'espace n'est pas une importance critique considération et l'espace supplémentaire utilisé par un tri de fusion peut-être pas et si un programmeur utilise des types primitifs, peut-être la performance est la chose la plus importante afin qu'ils utilisent le tri rapide. "

Source

2014-02-20 19:16:54 kukido

Ce n'est pas la raison principale. Juste après cette phrase, il y avait une question, intégrée dans la vidéo à propos de "Pourquoi MergeSort?" (parce que c'est stable). Je pense que Sedgewick n'a pas mentionné cela en vidéo pour le laisser en question. – likern

Selon Java 7 API docs cités dans this answer, Arrays#Sort() pour les tableaux d'objets utilise maintenant TimSort, qui est un hybride de mergesort et InsertionSort. D'autre part, Arrays#sort() pour les tableaux primitifs utilise maintenant Dual-Pivot QuickSort. Ces modifications ont été implémentées à partir de Java SE 7.

Source

2015-05-08 05:48:26

La méthode Java Arrays.sort utilise le tri rapide, le tri par insertion et le fusionnement. Il y a même un quicksort à un et deux pivots implémenté dans le code OpenJDK. L'algorithme de tri le plus rapide dépend des circonstances et les gagnants sont: tri d'insertion pour les petits tableaux (47 actuellement choisis), mergesort pour les tableaux triés en majeure partie, et tri rapide pour les tableaux restants afin que Java Array.sort() essaie de choisir le meilleur algorithme appliquer en fonction de ces critères.

Source

2017-11-23 16:14:00

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

Répondre

Questions connexes