sortieren

Details

sort ist eine generische Funktion, für die Methoden geschrieben werden können, und sort.int ist die interne Methode, die mit S kompatibel ist, wenn nur die ersten drei Argumente verwendet werden.

Die Standardmethode sort verwendet order für klassifizierte Objekte, die wiederum die generische Funktion xtfrm (und kann langsam sein, es sei denn, eine xtfrm – Methode wurde definiert oder is.numeric(x) ist true).,

Komplexe Werte werden zuerst nach dem Realteil, dann nach dem Imaginärteil sortiert.

Mit Ausnahme der Methode "radix" hängt die Sortierreihenfolge für Zeichenvektoren von der Sortierfolge des verwendeten Gebietsschemas ab: siehe Comparison. Die Sortierreihenfolge für Faktoren ist die Reihenfolge ihrer Ebenen (was besonders für geordnete Faktoren geeignet ist).

Wenn partial ist nicht NULL„, es wird enthalten die Indizes der Elemente der Folge sind zu platziert werden in die korrekte Position in der sortierten array von der teilweisen Sortierung., Für jeden der Ergebniswerte an einer bestimmten Position wird garantiert, dass alle Werte, die kleiner als dieser sind, einen kleineren Index im sortierten Array haben, und alle Werte, die größer sind, haben garantiert einen größeren Index im sortierten Array. (Dies ist für die Effizienz enthalten, und viele der Optionen sind für die teilweise Sortierung nicht verfügbar. Es ist nur wesentlich effizienter, wenn partial eine Handvoll Elemente hat und eine vollständige Sortierung durchgeführt wird (wenn möglich ein Quicksort), wenn mehr als 10 vorhanden sind.) Namen werden zur Teilsortierung verworfen.,

Methode "quick" verwendet die Implementierung der Quicksort-Methode von Hoare durch Singleton (1969) und ist nur verfügbar, wenn x numerisch (doppelt oder Ganzzahl) und partial NULList. (Für andere Typen von x Shellsort verwendet wird, schweigend.) Es ist normalerweise etwas schneller als Shellsort (vielleicht 50% schneller auf Vektoren der Länge eine Million und doppelt so schnell bei einer Milliarde), hat aber im seltenen schlimmsten Fall eine schlechte Leistung., (Petos Modifikation mit einem pseudozufälligen Mittelpunkt wird verwendet, um den schlimmsten Fall seltener zu machen.) Dies ist nicht eine stabile Art und Krawatten können nachbestellt werden.

Methode "radix" beruht auf einfachem Hashing, um die Zeit linear mit der Eingabegröße zu skalieren, dh ihre asymptotische Zeitkomplexität ist O(n). Die spezifische Variante und ihre Implementierung stammen aus den Daten.tabelle Paket und sind aufgrund Matt Dowle und Arun Srinivasan., Für kleine Eingaben (< 200) verwendet die Implementierung eine Einfügesorte(O (n^2)), die an Ort und Stelle arbeitet, um den Zuweisungsaufwand der Radix-Sortierung zu vermeiden. Für ganzzahlige Vektoren mit einem Bereich von weniger als 100.000 wechselt es zu einer einfacheren und schnelleren linearen Zeitzählsortierung. In allen Fällen ist die Sortierung stabil; Die Reihenfolge der Bindungen bleibt erhalten. Es ist die Standardmethode für ganzzahlige Vektoren und Faktoren.

Die"radix" – Methode übertrifft im Allgemeinen die anderen Methoden, insbesondere für Zeichenvektoren und kleine Ganzzahlen., Im Vergleich zur Schnellsortierung ist es für Vektoren mit großen ganzzahligen oder reellen Werten etwas schneller (aber im Gegensatz zur Schnellsortierung ist radix stabil und unterstützt alle na.last Optionen). Die Implementierung ist um Größenordnungen schneller als die Shell-Sortierung für Zeichenvektoren, zum Teil dank der cleveren Verwendung der internen CHARSXP – Tabelle.

Bei der Radix-Sortierung gibt es jedoch einige Einschränkungen:

• Wenn x ein character Vektor ist, müssen alle Elemente dieselbe Codierung haben., Es werden nur UTF-8-(einschließlich ASCII) und Latin-1-Codierungen unterstützt. Die Sortierung folgt immer dem Gebietsschema „C“.

• Lange Vektoren (mit mehr als 2^32 Elementen) und complex Vektoren werden noch nicht unterstützt.