R-alpha: Sorting Efficiency -- thoughts.. : if(!is.sorted(x)) x <- sort(x)
Peter Dalgaard BSA
05 Sep 1997 17:02:10 +0200
Martin Maechler <firstname.lastname@example.org> writes:
> 1. is.sorted is O(n)
> whereas sort is O(n*log(n))
> 2. for sorted x, the two assignments are superfluous even when order(x) was
> very fast (for SORTED x).
Actually, if it's a Shell sort, it's O(n^1.5) worst case and O(n^1.27)
average. For O(n log n) average you need quicksort or heapsort. The
former has the draw back of O(n^2) worst case, but heapsort has quite
a good reputation and is unconditionally n log n (that info comes from
Numerical Recipes, which was the best could dig out at the moment).
Maybe we should switch?
> superfluous, but the situation with order(.) above
> (which is NOT infrequent in statistics !!) would still profit from not
> doing 'x <- x[1:length(x)]' when x is sorted.
Yes.. Of course the case is often that you *know* that things are
sorted (because you just did it yourself), but modularity prevents you
from getting that information to the spot where it is needed.
O__ ---- Peter Dalgaard Blegdamsvej 3
c/ /'_ --- Dept. of Biostatistics 2200 Cph. N
(*) \(*) -- University of Copenhagen Denmark Ph: (+45) 35327918
~~~~~~~~~~ - (email@example.com) FAX: (+45) 35327907
r-devel mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !) To: firstname.lastname@example.org