Welcher Algorithmus wird von der Scala-Bibliotheksmethode Vector.sorted verwendet?
Ich habe mir die Scala-Dokumentation aber bis jetzt habe ich keine Antwort auf meine Frage gefunden, nämlich welchen Sortieralgorithmus die Methode verwendet
%Vor%Die Dokumentation sagt, es ist eine stabile Sortierung, aber nicht der eigentliche Algorithmus. Ist es eine Merge-Sortierung?
2 Antworten
Die Methode sorted ist in SeqLike implementiert und scheint java.util.Arrays.sort für ihre Sortierung zu verwenden. Es baut ein Array aus dem Vektor auf, ruft Arrays.sort auf und konvertiert es dann zurück, so scheint es. Laut der Java 6 Dokumentation verwendet es daher quicksort :
Der Sortieralgorithmus ist ein abgestimmter Quicksort, der von Jon L. Bentley und M. Douglas McIlroys "Engineering a Sort Function", Software-Practice and Experience. 23 (11), S. 1249-1265 (November 1993). Dieser Algorithmus bietet eine n * log (n) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen.
Für Java 7 scheint der Algorithmus eine Änderung zu haben (wiederum unter Berufung auf die Dokumente ):
Der Sortieralgorithmus ist ein Dual-Pivot Quicksort von Vladimir Yaroslavskiy, Jon Bentley und Joshua Bloch. Dieser Algorithmus bietet O (n log (n)) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen, und ist in der Regel schneller als herkömmliche QuickSort-Implementierungen (ein Pivot).
Scalas SeqLike#sorted Quelle (von GitHub übernommen) :
Ich stimme weitgehend mit der angenommenen Antwort überein. Ich möchte jedoch einige Punkte hinzufügen, wenn Java 7 Arrays
Die Antwort ändert sich leicht gegenüber den Änderungen, die seit JAVA 7 vorgenommen wurden. Dabei wird eine Variante von QuickSort namens DualPivotQuickSort verwendet, um primitive Werte in Java zu sortieren. util.Arrays
JAVA 7 Array-Sortierung unterscheidet sich für Primitives und Objects .
Hinweis von Docs -
Für primitive Werte Arrays:
Der Sortieralgorithmus ist ein Dual-Pivot Quicksort von Vladimir Yaroslavskiy, Jon Bentley und Joshua Bloch. Dieser Algorithmus bietet O (n log (n)) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen, und ist in der Regel schneller als herkömmliche QuickSort-Implementierungen (ein Pivot).
Für Objekt-Arrays:
Die Implementierung wurde aus Tim Peters Liste nach Python ( TimSort ) angepasst. Es verwendet Techniken aus Peter McIlroys "Optimistic Sorting and Information Theoretic Complexity" in Proceedings des vierten jährlichen ACM-SIAM-Symposiums über diskrete Algorithmen, S. 467-474, Januar 1993.
%Vor%Also sollte Java Arrays.sort den TimSort verwenden !!!!!!
Zusätzliche Details -
Sie finden die JAVA7-Implementierung hier - Ссылка
Weiteres geniales Lesen auf JAVA 7 - Ссылка
Die Änderungen haben Auswirkungen auf die Scala-Sortierung, die hier diskutiert wird - Ссылка