Pourquoi Collections.sort utilise le tri par fusion au lieu de quicksort? [fermé]

Fortement probable de Josh Bloch §:

J'ai écrit ces méthodes, donc je suppose que je suis qualifié pour répondre. Il est vrai qu'il n'y a pas de meilleur algorithme de tri. QuickSort a deux lacunes majeures par rapport à mergesort:

1. Ce n'est pas stable (comme l'a noté parsifal).

2. Il ne garantit pas n log n performance; il peut se dégrader en performance quadratique sur les entrées pathologiques.

La stabilité est un non-problème pour les types primitifs, car il n'y a pas de notion de l'identité distincte de l'égalité (de valeur). Et la possibilité de quadratique comportement était réputé ne pas être un problème dans la pratique pour L'implémentation de Bentely et McIlroy (ou par la suite pour Dual Pivot Quicksort), c'est pourquoi ces variantes QuickSort ont été utilisées pour les sortes primitives.

La stabilité est un gros problème lors du tri d'objets arbitraires. Exemple, supposons que vous avez objets représentant des messages électroniques, et vous triez d'abord par date, par expéditeur. Vous vous attendez à être triées par date dans chaque expéditeur, mais cela ne sera vrai que si le tri est stable. C'est pourquoi nous avons choisi de fournir un tri stable (Tri par fusion) pour trier les références de l'objet. (Techniquement parlant, plusieurs séquentielle les tris stables entraînent un ordre lexicographique sur les clés dans le ordre inverse des tri: le tri final détermine le plus d'importants sous-clé.)

C'est un bon avantage secondaire que le tri de fusion garantit n log n (time) performance peu importe ce que l'entrée. Bien sûr il y a un côté négatif: le tri rapide est un tri "en place": il ne nécessite que n espace externe (pour maintenir la pile d'appel). Fusionner, trier, d'autre part, nécessite O (n) espace externe. La variante TimSort (introduite en Java SE 6) nécessite sensiblement moins d'espace(O (k)) si le tableau d'entrée est presque trié.

Aussi, le suivant est pertinent:

L'algorithme utilisé par java.util.Tableau.trier et (indirectement) par Java.util.Collection.trier pour trier les références d'objet est un " modifié mergesort (dans lequel la fusion est omise si l'élément le plus élevé la sous-liste basse est inférieure à l'élément le plus bas de la sous-liste haute)." Il est un tri stable raisonnablement rapide qui garantit O (n log n) performance et nécessite O (n) d'espace supplémentaire. En son temps (il a été écrit en 1997 par Joshua Bloch), c'était un bon choix, mais aujourd'hui, mais nous pouvons faire beaucoup mieux.

Depuis 2003, le tri de liste de Python utilise un algorithme appelé timsort (d'après Tim Peters, qui l'a écrit). C'est un stable, adaptatif, itératif mergesort qui nécessite beaucoup moins de n log(n) comparaisons lorsque exécution sur des tableaux partiellement triés, tout en offrant des performances comparable à 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 des cas). Dans le pire des cas, timsort nécessite un stockage temporaire espace pour n / 2 références d'objet; dans le meilleur des cas, il ne nécessite petite quantité constante de l'espace. Contrastez cela avec le courant implémentation, qui nécessite toujours un espace supplémentaire pour n objet références, et beats n log n uniquement sur des listes presque triées.

Timsort est décrit en détail ici: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

L'original de Tim Peters l'implémentation est écrite en C. Joshua Bloch il a été porté de C vers Java et a été testé, comparé et réglé code résultant largement. Le code résultant est un drop-in remplacement pour java.util.Tableau.sorte. Sur des données hautement ordonnées, ceci le code peut s'exécuter jusqu'à 25 fois plus rapide que l'implémentation actuelle (sur la machine virtuelle du serveur HotSpot). Sur des données aléatoires, les vitesses de l'ancien et du nouveau les implémentations sont comparables. Pour les listes très courtes, le nouveau la mise en œuvre est nettement plus rapide que le vieux même au hasard données (car cela évite la copie de données inutile).

Aussi, voir Java 7 utilise-t-il Tim Sort pour les tableaux de méthodes.Trier?.

Il n'y a pas un seul "meilleur" choix. Comme pour beaucoup d'autres choses, il s'agit de compromis.