Le tri le plus rapide pour les petites collections

Question

Plusieurs fois, je dois trier de grandes quantités de petites listes, de tableaux. Il est assez rare que j'ai besoin de trier de grands tableaux. Quelle est l'algorithme de tri rapide pour le tri:

• tableaux
• (tableau) énumère

de taille 8-15 éléments de ces types:

• entier
• chaîne de 10 à 40 caractères

?

Je répertorie les types d'éléments car certains algorithmes comparent plus les opérations et moins les opérations d'échange. J'envisage le tri par fusion, le tri rapide, le tri par insertion et le tri des coques (incrément de 2^k - 1).

Answer 1

Arrays.sort(..)/Collections.sort(..) prendra cette décision pour vous.

Par exemple, le openjdk-7 implementation of Arrays.sort(..) a INSERTION_SORT_THRESHOLD = 47 - il utilise le tri d'insertion pour ceux avec moins de 47 éléments.

Answer 2

Sauf si vous pouvez prouver que cela est un goulot d'étranglement alors construit en sortes sont très bien:

Collections.sort(myIntList); 

Arrays.sort(myArray); 

Answer 3

En fait, il n'y a pas une réponse universelle. Entre autres choses, la performance d'un algorithme de tri Java dépendra du coût relatif de l'opération de comparaison, et (pour certains algorithmes) de l'ordre de l'entrée. Dans le cas d'une liste, cela dépend également du type d'implémentation de la liste.

Mais les conseils de @ Bozho sont sains, tout comme le commentaire de @Sean Patrick Floyd.

---

FOLLOWUP

Si vous pensez que la différence de performance va être important pour votre cas d'utilisation, alors vous devriez mettre la main sur certaines implémentations d'algorithmes différents, et de les tester à l'aide du données réelles que votre application doit traiter. (Et si vous n'avez pas encore les données, il est trop tôt pour commencer à régler votre application, car les performances de tri dépendront des données réelles.)

En bref, vous devrez effectuer vous-même l'analyse comparative.