Ordering Permutation

Description

order returns a permutation which rearranges its firstargument into ascending or descending order, breaking ties by furtherarguments.sort.list does the same, using only one argument.
See the examples for how to use these functions to sort data frames,etc.

Usage

order(..., na.last = TRUE, decreasing = FALSE,      method = c("auto", "shell", "radix"))sort.list(x, partial = NULL, na.last = TRUE, decreasing = FALSE,          method = c("auto", "shell", "quick", "radix"))

Arguments

Details

In the case of ties in the first vector, values in the second are usedto break the ties. If the values are still tied, values in the laterarguments are used to break the tie (see the first example).The sort used isstable (except formethod = "quick"),so any unresolved ties will be left in their original ordering.

Complex values are sorted first by the real part, then the imaginarypart.

Except for method"radix", the sort order for character vectorswill depend on the collating sequence of the locale in use: seeComparison.

The"shell" method is generally the safest bet and is thedefault method, except for short factors, numeric vectors, integervectors and logical vectors, where"radix" is assumed. Method"radix" stably sorts logical, numeric and character vectors inlinear time. It outperforms the other methods, although there aredrawbacks, especially for character vectors (seesort).Method"quick" forsort.list is only supported fornumericx withna.last = NA, is not stable, and isslower than"radix".

partial = NULL is supported for compatibility with otherimplementations of S, but no other values are accepted and ordering isalways complete.

For a classedR object, the sort order is taken fromxtfrm: as its help page notes, this can be slow unless asuitable method has been defined oris.numeric(x) istrue. For factors, this sorts on the internal codes, which isparticularly appropriate for ordered factors.

Value

An integer vector unless any of the inputs has2^31 ormore elements, when it is a double vector.

Warning

In programmatic use it is unsafe to name the... arguments,as the names could match current or future controlarguments such asdecreasing. A sometimes-encountered unsafepractice is to calldo.call('order', df_obj) wheredf_obj might be a data frame: copydf_obj andremove any names, for example usingunname.

Note

sort.list can get called by mistake as a method forsort with a list argument: it gives a suitable errormessage for listx.

There is a historical difference in behaviour forna.last = NA:sort.list removes theNAs and then computes the orderamongst the remaining elements:order computes the orderamongst the non-NA elements of the original vector. Thus

   x[order(x, na.last = NA)]   zz <- x[!is.na(x)]; zz[sort.list(x, na.last = NA)]

both sort the non-NA values ofx.

Prior toR 3.3.0method = "radix" was only supported forintegers of range less than 100,000.

References

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988)The New S Language.Wadsworth & Brooks/Cole.

Knuth, D. E. (1998)The Art of Computer Programming, Volume 3: Sorting andSearching. 2nd ed. Addison-Wesley.

See Also

sort,rank,xtfrm.

Examples

require(stats)(ii <- order(x <- c(1,1,3:1,1:4,3), y <- c(9,9:1), z <- c(2,1:9)))## 6  5  2  1  7  4 10  8  3  9rbind(x, y, z)[,ii] # shows the reordering (ties via 2nd & 3rd arg)## Suppose we wanted descending order on y.## A simple solution for numeric 'y' isrbind(x, y, z)[, order(x, -y, z)]## More generally we can make use of xtfrmcy <- as.character(y)rbind(x, y, z)[, order(x, -xtfrm(cy), z)]## The radix sort supports multiple 'decreasing' values:rbind(x, y, z)[, order(x, cy, z, decreasing = c(FALSE, TRUE, FALSE),                       method="radix")]## Sorting data frames:dd <- transform(data.frame(x, y, z),                z = factor(z, labels = LETTERS[9:1]))## Either as above {for factor 'z' : using internal coding}:dd[ order(x, -y, z), ]## or along 1st column, ties along 2nd, ... *arbitrary* no.{columns}:dd[ do.call(order, dd), ]set.seed(1)  # reproducible example:d4 <- data.frame(x = round(   rnorm(100)), y = round(10*runif(100)),                 z = round( 8*rnorm(100)), u = round(50*runif(100)))(d4s <- d4[ do.call(order, d4), ])(i <- which(diff(d4s[, 3]) == 0))#   in 2 places, needed 3 cols to break ties:d4s[ rbind(i, i+1), ]## rearrange matched vectors so that the first is in ascending orderx <- c(5:1, 6:8, 12:9)y <- (x - 5)^2o <- order(x)rbind(x[o], y[o])## tests of na.lasta <- c(4, 3, 2, NA, 1)b <- c(4, NA, 2, 7, 1)z <- cbind(a, b)(o <- order(a, b)); z[o, ](o <- order(a, b, na.last = FALSE)); z[o, ](o <- order(a, b, na.last = NA)); z[o, ]##  speed examples on an average laptop for long vectors:##  factor/small-valued integers:x <- factor(sample(letters, 1e7, replace = TRUE))system.time(o <- sort.list(x, method = "quick", na.last = NA)) # 0.1 secstopifnot(!is.unsorted(x[o]))system.time(o <- sort.list(x, method = "radix")) # 0.05 sec, 2X fasterstopifnot(!is.unsorted(x[o]))##  large-valued integers:xx <- sample(1:200000, 1e7, replace = TRUE)system.time(o <- sort.list(xx, method = "quick", na.last = NA)) # 0.3 secsystem.time(o <- sort.list(xx, method = "radix")) # 0.2 sec##  character vectors:xx <- sample(state.name, 1e6, replace = TRUE)system.time(o <- sort.list(xx, method = "shell")) # 2 secsystem.time(o <- sort.list(xx, method = "radix")) # 0.007 sec, 300X faster##  double vectors:xx <- rnorm(1e6)system.time(o <- sort.list(xx, method = "shell")) # 0.4 secsystem.time(o <- sort.list(xx, method = "quick", na.last = NA)) # 0.1 secsystem.time(o <- sort.list(xx, method = "radix")) # 0.05 sec, 2X faster