What is an effective way to check the sorting of rows in a matrix? [Update: see Aaron Rcpp's answer - directly and very quickly.]
I am porting code that uses issorted(,'rows') from Matlab . It seems that is.unsorted doesn't go beyond vectors, I'm writing or looking for something else. The naive method is to verify that the sorted version of the matrix (or data frame) is the same as the original, but which is clearly inefficient.
NB: to sort aa sortrows() in Matlab, my code essentially uses SortedDF <- DF[do.call(order, DF),] (it completes a large function that converts matrices into data frames, passes parameters to order , etc. d.). I would not be surprised if there are faster implementations (a data table comes to mind).
Update 1: To clarify: I am not testing the sorting of intra-root or intra-column columns. (This sorting usually results in an algebraically different matrix.)
As an example, to create an unsorted matrix:
set.seed(0) x <- as.data.frame(matrix(sample(3, 60, replace = TRUE), ncol = 6, byrow = TRUE))
Its sorted version:
y <- x[do.call(order, x),]
A testSorted test, say testSorted , will return FALSE for testSorted(x) and TRUE for testSorted(y) .
Update 2: The answers below are all good - they are concise and do the test. In terms of efficiency, it looks like they sort the data in the end.
I tried them with fairly large matrices such as 1M x 10 (just changing the creation of x above), and they all have the same cost of time and memory. What is special, they all consume more time for unsorted objects (about 5.5 seconds for 1Mx10) than for sorted objects (about 0.5 seconds for y ). This suggests that they are sorted before testing.
I tested by creating a z matrix:
z <- y z[,2] <- y[,1] z[,1] <- y[,2]
In this case, all methods take about 0.85 seconds. In any case, the completion in 5.5 seconds is not scary (in fact, it seems correct in terms of the time required to sort the object), but knowing that the sorted matrix is 11 times faster suggests that a test that does not sort can be even faster. In the case of the row matrix 1M, the first three rows x :
V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 1 3 1 2 2 3 1 3 3 2 2 2 1 1 1 3 2 3 2 3 3 2 3 3 3 1 2 1 1 2 1 2 3
There is no need to look at line 2, although vectorization is a good idea.
(I also added a byrow argument to create x , so the string values are independent of x size.)
Update 3: Another comparison for this test can be found using the sort -c command on Linux. If the file is already written (using write.table() ), with 1M lines, then time sort -c myfile.txt takes 0.003 seconds for unsorted data and 0.101 seconds for sorted data. I am not going to write the file, but this is a useful comparison.
Update 4: The Aaron Rcpp method used all the other methods suggested here and what I tried (including sort -c comparison above: it is expected that it will hit the disk in memory). As for the attitude towards other methods, it is difficult to say: the denominator is too small to give an accurate measurement, and I have not studied its microbenchmark in detail. The acceleration can be very large (4-5 orders of magnitude) for some matrices (for example, made using rnorm ), but this is misleading - the check can only complete after a few lines. I had acceleration with examples of matrices about 25-60 for unsorted and about 1.1X for sorted ones, since competing methods were very fast if the data was sorted.
Since this does the right thing (i.e. sorting, just testing), and does it very quickly, this is an accepted answer.