Алгоритм Divide & Conquer для проверки сортировки списка в порядке убывания

Question

Мне нужно написать функцию, которая проверяет, отсортирован ли массив/список/вектор (в R)/ в порядке убывания. Ответ должен быть реализован с использованием Divide & Conquer.

Вот что я пытался (по выполнению в 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)) 
} 

Но то всегда возвращает T:/ Спасибо за помощь

Answer 1

Это довольно неудобно осуществить это с помощью D & C. Однако давайте попробуем.

1. Последовательность длины 1 всегда сортируется.
2. Если x имеет длину> = 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])) 
} 

BTV, 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; 
} 
')