Pourquoi Collections.tri utilise de fusion au lieu de tri quicksort?

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

Les collections.tri utilisé de fusion algorithme de tri à la place du tri rapide. Mais Les Tableaux.tri utilise la fonction de tri rapide.

Quelle est la raison de Collections.tri utilise de fusion de tri à la place du tri rapide?

  • Sauf si vous pouvez obtenir un JDK auteur de la réponse, tout ce que vous allez obtenir est que pure conjecture. Pas une vraie question.
  • Bon point, mais certainement Pas "constructif" est la bonne fermeture de la raison. Il est clair pour moi que la question est ici.
  • Parce que le Java gars a décidé de faire comme cela. Demandez-leur. Vous ne pouvez pas obtenir une réponse légitime ici, je pense. Et tri rapide est pas le meilleur. C'est seulement le meilleur pour la utilisation générique.
  • D'accord. C'est un tossup. "Pas une vraie question' => 'Ne peut pas être raisonnablement répondu dans sa forme actuelle", mais s'il a été modifié pour demander: "quels sont les avantages respectifs de la fusion de tri et de quicksort' il pourrait être responsable.
  • On suppose que: Quicksort n'est pas stable, Mergesort est. Pour les primitives, stable/non-tri stable n'est pas pertinent, pour les objets qu'il pourrait être (ou au moins, vous pouvez obtenir des bugs déposée contre un tri instable).
  • Je pense que c'est la raison, mais son utilité n'a rien à voir avec le tri des primitives ou pas. Un tri stable s'assure juste que les éléments égaux ne sont pas modifiées dans leur ordre. Et cela a du sens pour les deux. Mais il n'est pas nécessaire dans tous les cas d'utilisation.
  • Rien n'empêche les intentions de JDK auteurs de public. Une fois que c'est public, nous n'avons pas besoin de l'auteur lui-même à répondre. Il est en effet possible d'obtenir une réponse qui est plus que deviner, même sans un JDK auteur de répondre.
  • En fait la réponse est assez légitime, dans la mesure légitime va.
  • Bonne nouvelle, apparemment un JDK auteur a répondu 🙂
  • Voulaient connaître des informations à ce sujet et google m'a dirigé ici. Et cette question est fermé pour cause de "pas une vraie question". Est-il un autre endroit dans la pile d'échange où ce genre de débat à faire?

InformationsquelleAutor MayurB | 2013-03-01
  1. 175

    Très 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, comparativement à mergesort:

    1. Il n'est pas stable (comme parsifal noté).

    2. Il n'a pas garantie n log n de la performance; il peut se dégrader pour quadratique de la performance sur pathologiques entrées.

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

    De la stabilité est une grosse affaire quand le tri des objets arbitraires. Par exemple,
    supposons que vous avez des objets représentant des messages e-mail, et vous
    d'abord par date, par expéditeur. Vous vous attendez à être triées par
    date au sein de chaque expéditeur, mais cela n'est vrai que si le tri est
    stable. C'est pourquoi nous avons choisi de faire un tri stable (Merge Sort)
    pour trier les références de l'objet. (Techniquement parlant, plusieurs séquentielle
    stable sortes résultat dans un lexicographique de la commande sur les touches de la
    l'ordre inverse de la sorte: le tri final détermine le plus
    d'importants sous-clé.)

    C'est un bel avantage que la Fusion de Tri garanties n n log (temps)
    les performances de n'importe quelle entrée. Bien sûr, il y a un côté vers le bas:
    tri rapide est un "à la place" de la sorte: il requies seulement log n espace extérieur
    (pour maintenir la pile d'appel). Fusion, de tri, d'autre part,
    nécessite O(n) un espace extérieur. Le TimSort variante (introduit dans Java
    SE 6) nécessite beaucoup moins d'espace (O(k)) si le tableau d'entrée est
    presque triées.

    Aussi, le la suite est pertinent:

    L'algorithme utilisé par java.util.Les tableaux de.trier et (indirectement) par
    java.util.Les Collections.trier pour trier les références de l'objet est un "modifié
    mergesort (dans lequel la fusion est omis si la plus haute de l'élément dans le
    faible sous-liste est inférieur au plus bas de l'élément dans le haut de sous-liste)." Il
    la situation est assez rapide tri stable qui garantit O(n log n)
    les performances et nécessite O(n) de l'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 Python de tri de la liste a utilisé un algorithme connu comme timsort
    (après Tim Peters, qui l'a écrit). Il est stable, l'adaptation, la itératif
    mergesort qui nécessite beaucoup moins de n log(n) comparaisons lorsque
    en cours d'exécution sur partiellement trié les tableaux, tout en offrant des performances
    comparable à un traditionnel mergesort lorsqu'il est exécuté sur des tableaux. Comme
    toutes les mergesorts timsort est stable et s'exécute en O(n log n) temps
    (pire des cas). Dans le pire des cas, timsort nécessite le stockage temporaire
    de l'espace pour les n/2 références de l'objet; dans le meilleur des cas, elle ne nécessite qu'une
    petite quantité constante de l'espace. Ceci contraste avec le courant
    la mise en œuvre, qui nécessite toujours plus d'espace pour les n objet
    les références, et les battements de n log n seulement sur près de listes triées.

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

    Tim Peters origine de la mise en œuvre est écrite en C. Joshua Bloch
    porté de C à Java et à la fin testé, évalué et à l'écoute de la
    code résultant largement. Le code résultant est un drop-in
    remplacement pour java.util.Les tableaux de.de tri. Sur très ordonnée de données, ce
    le code peut s'exécuter jusqu'à 25 fois plus rapide que l'implémentation actuelle (sur
    le point de connexion du serveur de VM). Sur des données aléatoires, les vitesses de l'ancien et du nouveau
    les implémentations sont comparables. Pour de très courtes listes, la nouvelle
    la mise en œuvre est beaucoup plus rapide que l'ancien, même sur le hasard
    données (parce qu'il évite de copie de données).

    Aussi, voir Est Java 7 à l'aide de Tim Tri pour la Méthode des Tableaux.Trier?.

    Il n'y a pas un seul "meilleur" choix. Comme beaucoup d'autres choses, c'est à propos de compromis.

    InformationsquelleAutor NPE