Warum verwendet Collections.sort Mergesort, Arrays.sort jedoch nicht?

94

Ich verwende JDK-8 (x64). Für Arrays.sort(Grundelemente) habe ich in der Java-Dokumentation Folgendes gefunden:

Der Sortieralgorithmus ist ein Dual-Pivot- Quicksort von Vladimir Yaroslavskiy, Jon Bentley und Joshua Bloch. "

Für Collections.sort(Objekte) habe ich dieses "Timsort" gefunden:

Diese Implementierung ist eine stabile, adaptive, iterative Zusammenführung ... Diese Implementierung speichert die angegebene Liste in einem Array, sortiert das Array und iteriert über die Liste, wobei jedes Element von der entsprechenden Position im Array zurückgesetzt wird.

Wenn Collections.sortein Array verwendet wird, warum wird dann nicht einfach QuickSortArrays.sort mit zwei Pivots aufgerufen oder verwendet ? Warum Mergesort verwenden ?

Quest Monger
quelle
8
Das ist das Javadoc für Arrays von Primitiven - Arrays von Objekten werden mit meregsort sortiert.
Assylias
2
mergesort gibt u nlogn immer während quicksort irgendwann kann give nlogn2 geneally Arrays Größe ist nicht so groß , aber Sammlungen leicht bis zu Millionen von Einträgen geht so ein Risiko von nlogn2 Einnahme ist es nicht wert PS nlogn2 i sqaure von n gemeint
Kumar Saurabh
O (n ^ 2) für Quicksort ist der extremste Worst-Case. In der Praxis ist es schneller
James Wierzba
Aber du kannst diese Caese nicht ignorieren, während du eine API machst
Kumar Saurabh
2
Dieser Link ist sehr verwandt.
Qartal

Antworten:

98

Die API garantiert eine stabile Sortierung, die Quicksort nicht bietet. Wenn Sie jedoch primitive Werte nach ihrer natürlichen Reihenfolge sortieren, werden Sie keinen Unterschied bemerken, da primitive Werte keine Identität haben. Daher kann Quicksort für primitive Arrays verwendet werden und wird verwendet, wenn es als effizienter angesehen wird¹.

Bei Objekten können Sie feststellen, dass Objekte mit unterschiedlicher Identität, die je nach equalsImplementierung oder Bereitstellung als gleich angesehen werden, Comparatorihre Reihenfolge ändern. Daher ist Quicksort keine Option. Daher wird eine Variante von MergeSort verwendet, die aktuellen Java-Versionen verwenden TimSort . Dies gilt für beide, Arrays.sortund Collections.sortobwohl mit Java 8 Listselbst die Sortieralgorithmen überschrieben werden können.


¹ Der Effizienzvorteil von Quicksort besteht darin, dass an Ort und Stelle weniger Speicher benötigt wird. Es hat jedoch eine dramatische Worst-Case-Leistung und kann keine Läufe vorsortierter Daten in einem Array ausnutzen, wie dies TimSort tut.

Daher wurden die Sortieralgorithmen von Version zu Version überarbeitet, während sie in der jetzt irreführend benannten Klasse blieben DualPivotQuicksort. Außerdem hat die Dokumentation nicht aufgeholt, was zeigt, dass es im Allgemeinen eine schlechte Idee ist, einen intern verwendeten Algorithmus in einer Spezifikation zu benennen, wenn dies nicht erforderlich ist.

Die aktuelle Situation (einschließlich Java 8 bis Java 11) ist wie folgt:

  • Im Allgemeinen verwenden die Sortiermethoden für primitive Arrays Quicksort nur unter bestimmten Umständen. Bei größeren Arrays versuchen sie zunächst, Läufe vorsortierter Daten zu identifizieren, wie dies bei TimSort der Fall ist, und führen sie zusammen, wenn die Anzahl der Läufe einen bestimmten Schwellenwert nicht überschreitet. Andernfalls werden sie auf Quicksort zurückgreifen , jedoch mit einer Implementierung, die für kleine Bereiche auf die Einfügesortierung zurückgreift , was nicht nur kleine Arrays, sondern auch die Rekursion der schnellen Sortierung betrifft.
  • sort(char[],…)und sort(short[],…)fügen Sie einen weiteren Sonderfall hinzu, um die Zählsortierung für Arrays zu verwenden, deren Länge einen bestimmten Schwellenwert überschreitet
  • Ebenso sort(byte[],…)wird die Zählsortierung verwendet , jedoch mit einem viel kleineren Schwellenwert, der den größten Kontrast zur Dokumentation bildet, da sort(byte[],…)Quicksort niemals verwendet wird. Es wird nur die Einfügesortierung für kleine Arrays und die Zählsortierung verwendet .
Holger
quelle
1
Hmm, interessanterweise heißt es in Collections.sort Javadoc: "Diese Sortierung ist garantiert stabil", aber da sie an List.sort delegiert wird, die von Listenimplementierungen überschrieben werden kann, kann die stabile Sortierung von Collections.sort nicht für alle Listen garantiert werden Implementierungen. Oder vermisse ich etwas? Und List.sort erfordert nicht, dass der Sortieralgorithmus stabil ist.
Puce
11
@Puce: Das bedeutet einfach, dass die Verantwortung für diese Garantie jetzt in den Händen derer liegt, die die übergeordnete List.sortMethode implementieren . Collections.sortkönnte niemals garantieren, dass die korrekte Arbeitsweise für jede ListImplementierung korrekt ist, da sie nicht garantieren kann, z. B. dass der ListInhalt nicht fälschlicherweise geändert wird. Alles läuft darauf hinaus, dass die Garantie von Collections.sortnur für korrekte ListImplementierungen (und korrekte Comparatoroder equalsImplementierungen) gilt.
Holger
1
@Puce: Aber Sie haben Recht, der Javadoc ist nicht gleichermaßen explizit über diese Einschränkung in beiden Methoden. Aber zumindest die neuesten Dokumentationszustände, an Collections.sortdie delegiert wird List.sort.
Holger
@Puce: Es gibt unzählige Beispiele dafür, bei denen wichtige Eigenschaften nicht Teil des Typs sind, sondern nur in der Dokumentation erwähnt werden (und daher vom Compiler nicht überprüft werden). Das Typensystem von Java ist einfach zu schwach, um interessante Eigenschaften auszudrücken. (Diesbezüglich unterscheidet es sich nicht wesentlich von einer dynamisch typisierten Sprache. Auch dort sind Eigenschaften in der Dokumentation definiert, und es ist Sache des Programmierers, sicherzustellen, dass sie nicht verletzt werden.) Es geht sogar noch weiter: Haben Sie es bemerkt? das Collections.sorterwähnt nicht einmal in seiner Typensignatur, dass die Ausgabe sortiert ist?
Jörg W Mittag
1
In einer Sprache mit einem ausdrucksstärkeren Typsystem Collections.sortwäre der Rückgabetyp so etwas wie "eine Sammlung des gleichen Typs und der gleichen Länge wie die Eingabe mit den Eigenschaften, dass 1) jedes in der Eingabe vorhandene Element auch in der Ausgabe vorhanden ist, 2 ) für jedes Elementpaar aus der Ausgabe ist das linke nicht größer als das rechte, 3) für jedes Paar gleicher Elemente aus der Ausgabe ist der linke Index in der Eingabe kleiner als der rechte "oder so ähnlich Das.
Jörg W Mittag
19

Ich weiß nichts über die Dokumentation, aber die Implementierung java.util.Collections#sortin Java 8 (HotSpot) sieht folgendermaßen aus:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

Und List#sorthat diese Implementierung:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

Collections#sortVerwendet also am Ende Arrays#sort(von Objektelementen) hinter den Kulissen. Diese Implementierung verwendet Merge Sort oder Tim Sort.

Luiggi Mendoza
quelle
16

Laut Javadoc werden nur primitive Arrays mit Quicksort sortiert. Objektarrays werden ebenfalls mit einem Mergesort sortiert.

Collections.sort scheint also denselben Sortieralgorithmus wie Arrays.sort für Objekte zu verwenden.

Eine andere Frage wäre, warum für primitive Arrays ein anderer Sortieralgorithmus verwendet wird als für Objekt-Arrays.

Puce
quelle
2

Wie in vielen Antworten angegeben.

Das Quicksort wird von Arrays.sort zum Sortieren primitiver Sammlungen verwendet, da keine Stabilität erforderlich ist (Sie wissen nicht, ob zwei identische Ints in der Sortierung ausgetauscht wurden).

MergeSort oder genauer gesagt Timsort wird von Arrays.sort zum Sortieren von Sammlungen von Objekten verwendet. Stabilität ist erforderlich. Quicksort sorgt nicht für Stabilität, Timsort schon.

Collections.sort delegiert an Arrays.sort, weshalb das Javadoc auf MergeSort verweist.

Cogitoboy
quelle
1

Die schnelle Sortierung hat zwei Hauptnachteile beim Zusammenführen der Sortierung:

  • Es ist nicht stabil, wenn es nicht primitiv ist.
  • Es garantiert keine n log n Leistung.

Stabilität ist für primitive Typen kein Thema, da es keinen Begriff von Identität gibt, der sich von (Wert-) Gleichheit unterscheidet.

Stabilität ist eine große Sache beim Sortieren beliebiger Objekte. Es ist ein netter Nebeneffekt, dass Merge Sort unabhängig von der Eingabe eine Leistung von n log n (Zeit) garantiert. Aus diesem Grund wird die Zusammenführungssortierung ausgewählt, um eine stabile Sortierung (Zusammenführungssortierung) zum Sortieren von Objektreferenzen bereitzustellen.

Krutik
quelle
1
Was meinst du mit "Nicht stabil"?
Arun Gowda