Pourquoi Collections.sort utilise-t-il le tri par fusion au lieu du tri rapide ?

Question

Nous savons que le tri rapide est l'algorithme de tri le plus rapide.

Le JDK6 collections.sort utilise l'algorithme de tri par fusion au lieu du tri rapide. Mais Arrays.sort utilise l'algorithme de tri rapide.

Quelle est la raison pour laquelle Collections.sort utilise le tri par fusion au lieu du tri rapide ?

Answer 1

Très probable de la part 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 un seul meilleur algorithme de tri. QuickSort a deux déficiences majeures par rapport à mergesort :

1. Il n'est pas stable (comme l'a noté Parsifal).

2. Ce n'est pas le cas. garantie n log n ; il peut se dégrader en performance quadratique sur des entrées pathologiques.

La stabilité n'est pas un problème pour les types primitifs, car il n'y a pas de notion de l'identité comme distincte de l'égalité (de valeur). Et la possibilité d'un comportement quadratique n'a pas été considérée comme un problème dans la pratique pour l'implémentation de Bentely et McIlroy (ou, par la suite, de Pivot double Quicksort ), ce qui explique pourquoi ces variantes de QuickSort ont été utilisées pour les projets suivants les tris primitifs.

La stabilité est un élément important lors du tri d'objets arbitraires. Par exemple, supposons que vous ayez des objets représentant des messages électroniques, et que vous les triiez d'abord par date, puis par expéditeur. Vous vous attendez à ce qu'ils soient triés par date au sein de 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 (Merge Sort) pour trier les références d'objets. (Techniquement parlant, plusieurs tris stables séquentiels séquentiels stables résultent en un classement lexicographique des clés dans l'ordre inverse des dans l'ordre inverse des tris : le tri final détermine la sous-clé la plus significative. la sous-clé la plus significative).

C'est un avantage supplémentaire de Merge Sort. garanties n log n (temps) performance, quelle que soit l'entrée. Bien sûr, il y a un revers à la médaille : le tri rapide est un tri "en place" : il ne nécessite que log n d'espace externe (pour maintenir la pile d'appels). Le tri par fusion, en revanche, nécessite O(n) d'espace externe. La variante TimSort (introduite dans Java SE 6) nécessite beaucoup moins d'espace (O(k)) si le tableau d'entrée est presque trié. presque trié.

En outre, le suivant est pertinente :

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

Depuis 2003, le tri de listes de Python utilise un algorithme connu sous le nom de timsort (du nom de Tim Peters, qui l'a écrit). Il s'agit d'un tri par fusion stable, adaptatif et itératif. itérative, adaptative et stable, qui nécessite bien moins de n log(n) comparaisons en comparaisons lorsqu'elle s'exécute sur des tableaux partiellement triés, tout en offrant des performances comparables à celles d'un mergesort traditionnel lorsqu'il est exécuté sur des tableaux aléatoires. Comme toutes les mergesorts correctes, timsort est stable et s'exécute en O(n log n) temps (dans le pire des cas). Dans le pire des cas, timsort nécessite un espace de stockage temporaire pour n/2 références d'objets. temporaire pour n/2 références d'objets ; dans le meilleur des cas, elle ne nécessite qu'une petite quantité constante d'espace. Comparez cela avec l'implémentation actuelle actuelle, qui nécessite toujours de l'espace supplémentaire pour n références d'objets et ne bat n log n que 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'implémentation originale de Tim Peters est écrite en C. Joshua Bloch l'a portée de C à Java et a testé, évalué et réglé le code résultant de manière extensive. le code résultant. Le code résultant est un remplacement remplacement de java.util.Arrays.sort. Sur des données hautement ordonnées, ce ce code peut s'exécuter jusqu'à 25 fois plus vite que l'implémentation actuelle (sur la VM de la VM du serveur HotSpot). Sur des données aléatoires, les vitesses de l'ancienne et de la nouvelle implémentation sont comparables. implémentations sont comparables. Pour les listes très courtes, la nouvelle est sensiblement plus rapide que l'ancienne, même sur des données données aléatoires (parce qu'elle évite la copie inutile de données).

Voir aussi Java 7 utilise-t-il Tim Sort pour la méthode Arrays.Sort ? .

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