Pourquoi java.util.Arrays.sort (Object []) utilise-t-il 2 types d'algorithmes de tri?

Question

J'ai trouvé que java.util.Arrays.sort(Object[]) utilisent 2 types d'algorithmes de tri (dans JDK 1.6).

pseudocode:

 if(array.length<7)
   insertionSort(array);
else
   mergeSort(array);
 

Pourquoi a-t-il besoin de 2 types de tri ici? pour l'efficacité?

Answer 1

Il est important de noter qu'un algorithme, c'est - O(N log N) n'est pas toujours plus rapide dans la pratique qu'un O(N^2) de l'algorithme. Il dépend des constantes, et la gamme de N impliqués. (Rappelez-vous que asymptotique de la notation des mesures de taux relatif de croissance, pas de vitesse absolue).

Pour petite N, le tri par insertion, en fait, fait battre fusion de tri. Il est également plus rapide pour la quasi-trier les tableaux.

Voici une citation:

Bien qu'il soit une des primaires algorithmes de tri avec O(N^2) des cas les pires temps, le tri par insertion est l'algorithme de choix lorsque les données sont presque triées (parce que c'est adaptative) ou lorsque la taille du problème est de petite taille (car il a une faible surcharge).

Pour ces raisons, et parce qu'il est également stable, le tri par insertion est souvent utilisé comme récursive de la base de cas (lorsque la taille du problème est petit) pour la hausse des frais généraux divide-and-conquer algorithmes de tri, tels que la fusion de tri ou tri rapide.

Voici une autre citation de Meilleur algorithme de tri pour près de trier les listes de papier:

droite le tri par insertion est le meilleur pour les petits ou très près de listes triées

Ce que cela signifie est que, dans la pratique:

• Un algorithme Un₁ avec plus asymptotique limite supérieure peut être préférable qu'un autre algorithme connu Une₂ avec asymptotique inférieure à la limite supérieure de
  • Peut-être Un₂ est trop compliqué à mettre en œuvre
  • Ou peut-être qu'il n'a pas d'importance dans la gamme de Nconsidéré comme
    • Voir, par exemple, Chaudronnerie–algorithme de Winograd
• Certains algorithmes hybrides peut s'adapter à différents algorithmes en fonction de la taille de saisie

Questions connexes

• Qui algorithme de tri est le mieux adapté pour re-trier presque entièrement triée liste?
• Est-il toujours une bonne raison pour utiliser le Tri par Insertion?

---

Un exemple numérique

Considérons ces deux fonctions:

• f(x) = 2x^2; cette fonction est quadratique taux de croissance, c'est à dire "O(N^2)"
• g(x) = 10x; cette fonction est linéaire et le taux de croissance, c'est à dire "O(N)"

Maintenant, nous allons tracer les deux fonctions:

^{Source: WolframAlpha: plot 2x^2 and 10x for x from 0 to 10}

Notez qu'entre x=0..5, f(x) <= g(x), mais pour un gros x, f(x) rapidement épuiser g(x).

De la même façon, si Un₁ est un algorithme quadratique avec un minimum de coûts, et Une₂ est un algorithme linéaire avec un haut dans le ciel, pour les plus petites d'entrée, Un₁ peut être plus rapide qu' Un₂.

Ainsi, vous pouvez, si vous choisissez de le faire, créer un algorithme hybride d'Un₃ qui sélectionne simplement l'un des deux algorithmes en fonction de la taille de l'entrée. Si oui ou non cela vaut la peine de l'effort dépend de paramètres effectifs impliqués.

De nombreux tests et comparaisons des algorithmes de tri ont été faites, et il a été décidé que, parce que le tri par insertion battements de fusion de tri pour les petits tableaux, ça valait le coup de mettre en œuvre à la fois pour Arrays.sort.

Answer 2

C'est pour la vitesse. La surcharge de mergeSort est suffisamment élevée pour que pour les tableaux courts, elle soit plus lente que le tri par insertion.

Answer 3

Cité de: http://en.wikipedia.org/wiki/Insertion_sort

 Some divide-and-conquer algorithms such as quicksort and mergesort sort by 
recursively dividing the list into smaller sublists which are then sorted. 
A useful optimization in practice for these algorithms is to use insertion 
sort for sorting small sublists, where insertion sort outperforms these more 
complex algorithms. The size of list for which insertion sort has the advantage 
varies by environment and implementation, but is typically between eight and 
twenty elements.
 

Answer 4

Il semble qu'ils croient que mergeSort(array ) est plus lent pour les tableaux courts. J'espère qu'ils l'ont testé.