[R] Help me with writing function sort()

[Martin Morgan]

On 04/11/2010 06:30 AM, maslakos wrote:
> 
> Hello everyone, i`m new here.. I just started with learning R language and i
> have hard "homework". I need to write function like sort().. Anyone know how
> to do it? Can u give me algorithm for sorting vector? x=c(1,2,-1,1,3,4) or
> something like that.. I`m sorry for my english..

Hi --

R usually works at a higher level than a 'sort' algorithm, which is
provided internally

> x <- rnorm(1000)
> res0 <- sort(x)

but you could write a sort function as

  qsort <- function(x)
  {
    n <- length(x)
    if (n <= 1) x
    else {
      mid <- x[ n/2L ]
      c(qsort(x[ x < mid ]), x[ x == mid ], qsort(x[ x > mid ]))
    }
  }

> res1 <- qsort(x)
> identical(res0, res1)
[1] TRUE
> system.time(sort(x))
   user  system elapsed
  0.000   0.000   0.002
> system.time(qsort(x))
   user  system elapsed
  0.024   0.000   0.024

some language features in the above: the last evaluated line of a
function is returned, so no need for an explicit 'return'; no ';' at the
end of lines; 'vectorized' operations like x < mid (compare all x to
mid) and '[' (create a subset of x); digits like '2' are treated as
numeric (i.e. double), integer values need to be created explicitly
(with the 'L', as in '2L'). The timing is probably pretty typical --
about 10x slower in R than with built-in (implemented in C) functions.
If the this thread catches on, then likely someone will provide
improvements that bring the R implementation speed closer to C.

Martin
-- 
Martin Morgan
Computational Biology / Fred Hutchinson Cancer Research Center
1100 Fairview Ave. N.
PO Box 19024 Seattle, WA 98109

Location: Arnold Building M1 B861
Phone: (206) 667-2793