Quel est le type utilisé par Java Collections.sort (nodes)?

Je pense que c'est MergeSort, qui est O(n log n).

Cependant, la sortie suivante n'est pas d'accord:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

Je suis le tri d'une nodelist de 4 nœuds par numéro de séquence, et le tri est fait 6 comparaisons.
Je suis perplexe, car 6 > (4 log(4)). Quelqu'un peut-il m'expliquer cela?

P. S. C'est mergesort, mais je ne comprends toujours pas mes résultats.

Merci pour les réponses de tout le monde. Merci Tom pour la correction de mes maths.

source d'informationauteur Kyle Jones

  1. 29

    O(n log n) ne signifie pas que le nombre de comparaisons sera égal ou inférieur à n log n, c'est juste que le temps sera échelle proportionnellement à n log n. Essayez de faire des tests avec 8 nœuds, ou de 16 nœuds, ou de 32 nœuds, et de vérifier le calendrier.

  2. 24

    Vous triées quatre nœuds, si vous n'obtenez pas de fusion tri tri de commutation pour le tri par insertion.

    En Java, les Tableaux.sort() utilisation de méthodes de fusion de tri ou à l'écoute de quicksort selon les types de données et pour la mise en œuvre de l'efficacité interrupteur pour le tri par insertion lorsque moins de sept éléments du tableau sont triés. (Wikipédia, emphase ajoutée)

    Tableaux.le tri est utilisé indirectement par les Collections de classes.

    Un, a récemment accepté un rapport de bug indique que le Soleil de la mise en œuvre de Java va utiliser Python timsort dans l'avenir: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124

    (Le timsort monographie, ci-dessus, est bien la peine de lire.)

  3. 3

    Un algorithme A(n) qui traite une quantité de données n est en O(f(n)) pour une certaine fonction f, s'il existe deux strictement positifs constantes C_inf et C_sup tels que:

    C_inf . f(n) < ExpectedValue(OperationCount(A(n))) < C_sup . f(n)

    Deux choses à noter:

    • Le réel constantes C pourrait être n'importe quoi, et ne dépend du coût relatif des opérations (en fonction de la langue, de la VM, l'architecture, ou de votre définition d'une opération). Sur certaines plates-formes, par exemple, + et * ont le même coût, sur certaines autres, plus tard, est d'un ordre de grandeur inférieur.

    • La quantité attribuée "en O(f(n))" est un devrait nombre de fonctionnement, basé sur certains probablement arbitraire modèle des données qui vous avez affaire. Par exemple, si vos données est presque complètement trié, une fusion algorithme de tri va être la plupart du temps O(n), pas de O(n . Log(n)).

  4. 2

    J'ai écrit quelques trucs qui pourraient vous intéresser à propos de la Java algorithme de tri et de prises certaines mesures de la performance des Collections.sort(). L'algorithme à l'heure actuelle est une mergesort avec une insertion de tri une fois que vous obtenez jusqu'à une certaine taille de sous-listes (N. B. cet algorithme est très probablement va changer dans Java 7).

    Vous devriez vraiment prendre le Big O la notation comme une indication de la façon dont l'algorithme de mise à l'échelle globale; pour un type particulier, le moment précis va s'écarter de la temps prédit par ce calcul (comme vous le verrez sur mon graphe, les deux algorithmes de tri qui sont combinés ont chacun des caractéristiques de performance, et donc le temps total pour un tri est un peu plus complexe).

    Cela dit, à titre indicatif, pour chaque fois que vous doublez le nombre d'éléments, si vous multipliez le temps prévu par 2.2, vous ne serez pas loin. (Il ne fait pas beaucoup de sens de faire cela pour de très petites listes de quelques éléments, cependant).