Sorteer

Details

sort is een generieke functie waarvoor methoden kunnen worden geschreven, en sort.int is de interne methode die compatibel is met S als alleen de eerste drie argumenten worden gebruikt.

De standaard sort methode maakt gebruik van order voor geklasseerde objecten, die op hun beurt gebruik maakt van de generieke functie xtfrm (en kan traag zijn tenzij een xtfrm methode is gedefinieerd of is.numeric(x) is waar).,

complexe waarden worden eerst gesorteerd op het reële deel, dan op het imaginaire deel.

behalve voor methode "radix", zal de sorteervolgorde voor tekenvectoren afhangen van de volgorde van het sorteren van de gebruikte landinstelling: zie Comparison. De sorteervolgorde voor factoren is de volgorde van hun niveaus (die bijzonder geschikt is voor geordende factoren).

als partial niet NULL is, worden indices van elementen van het resultaat gebruikt die op hun juiste positie in de gesorteerde array moeten worden geplaatst door gedeeltelijke sortering., Voor elk van de resultaatwaarden in een opgegeven positie, zijn alle waarden kleiner dan die een gegarandeerd een kleinere index in de gesorteerde array en alle waarden die groter zijn gegarandeerd een grotere index in de gesorteerde array. (Dit is inbegrepen voor efficiëntie, en veel van de opties zijn niet beschikbaar voor gedeeltelijke sortering. Het is alleen aanzienlijk efficiënter als partial een handvol elementen heeft, en een volledige sorteermethode wordt gedaan (een Snelsort indien mogelijk) als er meer dan 10 zijn.) Namen worden weggegooid voor gedeeltelijke sortering.,

methode "quick" gebruikt Singleton (1969) ’s implementatie van Hoare’ s Quicksort methode en is alleen beschikbaar als x numeriek (dubbel of geheel getal) is en partial is NULL. (Voor andere types van x wordt stilletjes Shellsort gebruikt.) Het is normaal gesproken iets sneller dan Shellsort (misschien 50% sneller op vectoren met een lengte van een miljoen en twee keer zo snel op een miljard) maar heeft slechte prestaties in het zeldzame ergste geval., (Peto ‘ s Wijziging met behulp van een pseudo-willekeurig middelpunt wordt gebruikt om het ergste geval zeldzamer te maken.) Dit is geen stabiele soort, en banden kunnen opnieuw worden gerangschikt.

methode "radix" vertrouwt op eenvoudige hashing om tijd lineair te schalen met de invoergrootte, d.w.z. de asymptotische tijdcomplexiteit is O(n). De specifieke variant en de uitvoering ervan zijn voortgekomen uit de gegevens.tafel pakket en zijn te wijten aan Matt Dowle en Arun Srinivasan., Voor kleine ingangen (< 200) gebruikt de implementatie een invoegsort (O(n^2)) die op zijn plaats werkt om de allocatie overhead van de radix soort te vermijden. Voor integer vectoren met een bereik van minder dan 100.000, schakelt het over naar een eenvoudigere en snellere lineaire tijdtelling. In alle gevallen is de soort stabiel; de Orde van banden wordt bewaard. Het is de standaardmethode voor integer vectoren en factoren.

de "radix" methode presteert over het algemeen beter dan de andere methoden, vooral voor tekenvectoren en kleine gehele getallen., Vergeleken met quick sort is het iets sneller voor vectoren met grote integer of reële waarden (maar in tegenstelling tot quick sort is radix stabiel en ondersteunt alle na.last opties). De implementatie is ordes van grootte sneller dan shell Sorteer voor karaktervectoren, deels dankzij slim gebruik van de interne CHARSXP tabel.

Er zijn echter enkele kanttekeningen bij de radix sort:

• als x een character vector is, moeten alle elementen dezelfde codering delen., Alleen UTF-8 (inclusief ASCII) en Latin-1 coderingen worden ondersteund. Collation volgt altijd de ” C ” locale.

• lange vectoren (met meer dan 2^32 elementen) en complex vectoren worden nog niet ondersteund.