| sort {base} | R Documentation |
Sort (or order) a vector or factor (partially) into
ascending (or descending) order. For ordering along more than one
variable, e.g., for sorting data frames, see order.
sort(x, decreasing = FALSE, ...)
## Default S3 method:
sort(x, decreasing = FALSE, na.last = NA, ...)
sort.int(x, partial = NULL, na.last = NA, decreasing = FALSE,
method = c("shell", "quick"), index.return = FALSE)
is.unsorted(x, na.rm = FALSE)
x |
for sort, an R object with a class or a numeric,
complex, character or logical vector. For sort.int, a
numeric, complex, character or logical vector, or a factor. |
decreasing |
logical. Should the sort be increasing or decreasing? Not available for partial sorting. |
... |
arguments to be passed to or from methods or (for the
default methods and objects without a class) to sim.int. |
na.last |
for controlling the treatment of NAs.
If TRUE, missing values in the data are put last; if
FALSE, they are put first; if NA, they are removed. |
partial |
NULL or an integer vector of indices for
partial sorting. |
method |
character string specifying the algorithm used. |
index.return |
logical indicating if the ordering index vector should
be returned as well; this is only available for a few cases, the default
na.last = NA and full sorting of non-factors. |
na.rm |
logical. Should missing values be removed? |
sort is a generic function for which methods can be written,
and sort.int is the internal method which is compatible
with S if only the first three arguments are used.
If partial is not NULL, it is taken to contain indices
of elements of x which are to be placed in their correct
positions by partial sorting. After the sort, the values specified in
partial are in their correct position in the sorted array. Any
values smaller than these values are guaranteed to have a smaller
index in the sorted array and any values which are greater are
guaranteed to have a bigger index in the sorted array. (This is included
for efficiency, and many of the options are not available for partial
sorting. It is only substantially more efficient if partial has a
handful of elements, and a full sort is done if there
are more than 10.) Names are discarded for partial sorting.
Complex values are sorted first by the real part, then the imaginary part.
The sort order for character vectors will depend on the collating
sequence of the locale in use: see Comparison.
The sort order for factors is the order of their levels (which is
particularly appropriate for ordered factors).
is.unsorted returns a logical indicating if x is sorted
increasingly, i.e., is.unsorted(x) is true if any(x !=
sort(x)) (and there are no NAs).
Method "shell" uses Shellsort (an O(n^{4/3}) variant
from Sedgewick (1996)). If x has names a stable sort is used,
so ties are not reordered. (This only matters if names are present.)
Method "quick" uses Singleton's Quicksort implementation and is
only available when x is numeric (double or integer) and
partial is NULL. (For other types of x Shellsort
is used, silently.) It is normally somewhat faster than Shellsort
(perhaps twice as fast on vectors of length a million) but has poor
performance in the rare worst case. (Peto's modification using a
pseudo-random midpoint is used to make the worst case rarer.) This is
not a stable sort, and ties may be reordered.
For sort, the result depends on the S3 method which is
dispatched. If x does not have a class the rest of this section
applies. For classed objects which do not have a specific method the
default method will be used and is equivalent to x[order(x,
...)]: this depends on the class having a suitable method for
[ (and also that order will work, which is not
the case for a class based on a list).
For sort.int the sorted vector unless
index.return is true, when the result is
a list with components named x and ix containing the
sorted numbers and the ordering index vector. In the latter case,
if method == "quick" ties may be reversed in the ordering,
unlike sort.list, as quicksort is not stable.
All attributes are removed from the return value (see Becker et
al, 1988, p.146) except names, which are sorted. (If
partial is specified even the names are removed.) Note that
this means that the returned value has no class, except for factors
and ordered factors (which are treated specially and whose result is
transformed back to the original class).
Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole.
Sedgewick, R. (1986) A new upper bound for Shell sort. J. Algorithms 7, 159–173.
Singleton, R. C. (1969) An efficient algorithm for sorting with minimal storage: Algorithm 347. Communications of the ACM 12, 185–187.
order for sorting on or reordering multiple variables.
rank.
require(stats)
x <- swiss$Education[1:25]
x; sort(x); sort(x, partial = c(10, 15))
stats:::median.default # shows you another example for 'partial'
## illustrate 'stable' sorting (of ties):
sort(c(10:3,2:12), method = "sh", index=TRUE) # is stable
## $x : 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 12
## $ix: 9 8 10 7 11 6 12 5 13 4 14 3 15 2 16 1 17 18 19
sort(c(10:3,2:12), method = "qu", index=TRUE) # is not
## $x : 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 12
## $ix: 9 10 8 7 11 6 12 5 13 4 14 3 15 16 2 17 1 18 19
## ^^^^^
## Not run: ## Small speed comparison simulation:
N <- 2000
Sim <- 20
rep <- 1000 # << adjust to your CPU
c1 <- c2 <- numeric(Sim)
for(is in 1:Sim){
x <- rnorm(N)
c1[is] <- system.time(for(i in 1:rep) sort(x, method = "shell"))[1]
c2[is] <- system.time(for(i in 1:rep) sort(x, method = "quick"))[1]
stopifnot(sort(x, method = "s") == sort(x, method = "q"))
}
rbind(ShellSort = c1, QuickSort = c2)
cat("Speedup factor of quick sort():\n")
summary({qq <- c1 / c2; qq[is.finite(qq)]})
## A larger test
x <- rnorm(1e7)
system.time(x1 <- sort(x, method = "shell"))
system.time(x2 <- sort(x, method = "quick"))
stopifnot(identical(x1, x2))
## End(Not run)