Welche ist Java Collections.sort (Knoten) verwenden?

Question

Ich denke, es MergeSort ist, die O (n log n) ist.

Allerdings ist die folgende Ausgabe nicht einverstanden ist:

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

Ich bin ein Nodelist von 4 Knoten durch Sequenznummer sortiert wird, und die Art 6 Vergleiche tut. Ich bin verwirrt, weil 6> (4 log (4)). Kann jemand mir dies erklären?

PS Es ist mergesort, aber ich immer noch nicht meine Ergebnisse verstehen.

Danke für die Antworten jeder. Danke Tom für meine Mathe zu korrigieren.

Answer 1

O (n log n) bedeutet nicht, dass die Anzahl der Vergleiche gleich sein oder weniger als n log n, nur, dass die Zeit wird Skala proportional zu n log n genommen. Versuchen Sie, Tests mit 8 Knoten oder 16 Knoten oder 32 Knoten, und das Timing Check-out.

Answer 2

Sie sortiert vier Knoten, so dass Sie nicht sortieren hast fusionieren; Art geschaltet Insertionsort.

  

In Java, die Arrays.sort () Methoden merge Sortier- oder ein abgestimmter quicksort auf den Datentypen abhängig und für die Umsetzung Effizienz Schalter Insertionsort wenn weniger als sieben Array-Elemente sortiert werden. ( Wikipedia, Hervorhebung hinzugefügt)

Arrays.sort wird indirekt durch die Sammlungen Klassen verwendet.

Ein kürzlich akzeptierte Fehlerbericht zeigt, dass die Sun Java-Implementierung von Python verwenden Timsort in die Zukunft: http://bugs.sun.com /bugdatabase/view_bug.do?bug_id=6804124

(Die Timsort Monographie, oben verbunden ist, lohnt sich das Lesen.)

Answer 3

Ein Algorithmus A (n), die eine Datenmenge verarbeitet n ist in O (f (n)), für eine Funktion f, wenn es zwei streng positive Konstanten C_inf und C_sup so dass:

C_inf. f (n)

Zwei Dinge zu beachten:

• Die tatsächlichen Konstanten C könnte alles sein, und tun ist abhängig von den relativ Kosten von Operationen (abhängig von der Sprache, die VM, die Architektur, oder Ihre aktuelle Definition einer Operation) . Auf einigen Plattformen, zum Beispiel, + und * die gleichen Kosten, auf einem anderen der spätere ist eine Größenordnung langsamer.

• Die Menge zugeschrieben als "in O (f (n))" ist eine erwartet Betrieb Zahl, basierend auf einiges wahrscheinlich beliebiges Modell der Daten, die Sie zu tun haben. Zum Beispiel wird, wenn Ihre Daten fast vollständig geordnet, ein Merge-Sort-Algorithmus wird meist O (n) sein, nicht O (n. Log (n)).

Answer 4

Ich habe einige Sachen geschrieben Sie über den Java-Sortieralgorithmus interessiert sein und genommen einige Leistungsmessungen von Collections.sort () . Der Algorithmus zur Zeit ist ein mergesort mit einem Insertionsort , wenn Sie auf eine bestimmte Größe von Sublisten get down ( NB ist dieser Algorithmus sehr wahrscheinlich in Java wird sich ändern 7 ).

Sie sollten wirklich die Big O-Notation als Hinweis auf nehmen, wie der Algorithmus insgesamt skaliert; für eine bestimmte Art, die genaue Zeit von der Zeit nach dieser Berechnung vorhergesagten abweichen wird (wie Sie auf meinem Diagramm sehen werden, sind die beiden Sortieralgorithmen, die jeweils unterschiedliche Leistungsmerkmale kombiniert werden, so dass die Gesamtzeit für eine Art ist ein etwas komplexe).

Das heißt, als grobe Orientierung für jedes Mal, wenn Sie die Anzahl der Elemente verdoppeln, wenn man die erwartete Zeit um 2,2 multiplizieren, werden Sie nicht weit sein. (Es macht nicht viel Sinn machen das wirklich von ein paar Elemente für sehr kleine Listen zu tun, though.)