用于检查列表是否按降序排序的分而治之算法

Question

我需要编写一个函数来检查 array/list/vector(在 R 中)/ 按降序排列。答案必须使用分而治之来实现。

这是我尝试过的（实现在 R 中）：

is.sort<-function(x){    
  n<-length(x)
  if (n==1)
    return(T)

  mid<-floor(n/2)   
  x1<-is.sort(x[1:mid])
  x2<-is.sort(x[(mid+1):n])
  return(ifelse(x1>=x2,T,F))
}

但那总是 returns T:/ 感谢帮助

Answer 1

使用 D&C 来实现它是相当尴尬的。不过，让我们试试吧。

长度为 1 的序列总是排序的。
如果x的长度>=2，则将其分成2个非空子序列x1和x2。然后 x 被排序，如果 x1 被排序， x2 被排序，并且 x1 中的最后一个元素大于或等于（假设非递增排序） x2 中的第一个元素。

这可以实现为：

is.sort<-function(x){
   n<-length(x)
   if (n==1)
      return(TRUE)
   mid<-floor(n/2)
   return(x[mid] >= x[mid+1] && is.sort(x[1:mid]) && is.sort(x[(mid+1):n]))
}

顺便说一句，R 有一个 is.unsorted 函数，但它只确定序列是否已排序 w.r.t。 < 或 <=。对于那些错过它的 >= 等价物的人来说，这是一个简单的 Rcpp 实现：

Rcpp::cppFunction('
bool is_sort(NumericVector x) {
   int n=x.size();
   for (int i=0; i<n-1; ++i)
      if (x[i] < x[i+1]) return false;
   return true;
}
')

用于检查列表是否按降序排序的分而治之算法

Divide&Conquer Algorithm for Checking if a list is sorted in Descending order

algorithm

recursion

r

divide-and-conquer