R中mergesort的比較次數

我在R中寫入一個合併排序。我有2個函數。首先是mergelist（）R中mergesort的比較次數

mergelist <- function(a, b) 
{ 
    al <- length(a$data) 
    bl <- length(b$data)   
    r <- numeric(al + bl) 
    numberOfComparisions <-0 
    ai <- 1 
    bi <- 1 
    j <- 1 

    while((ai <= al) && (bi <= bl)) 
    { 
     if(a$data[ai]<b$data[bi]) 
     { 
      r[j] <- a$data[ai] 
      ai <- ai + 1 
      numberOfComparisions = numberOfComparisions + 1 
     } 
     else 
     { 
      r[j] <- b$data[bi] 
      bi <- bi + 1  
      numberOfComparisions = numberOfComparisions + 1 
     }  
     j <- j + 1 
    } 
    if(ai<=al) 
    r[j:(al+bl)] <- a$data[ai:al]  
    else if(bi <= bl) 
    r[j:(al+bl)] <- b$data[bi:bl]  

    returnList <- list(number=numberOfComparisions + a$number + b$number , data = r) 
    return(returnList) 
}

這種方法需要在2排序的列表作爲參數a和b，並返回一個排序列表與列表告訴我有多少comparisions那裏已經做出的人數屬性。

我也有這個方法歸併（）

mergesort <- function(x) 
{ 
    l <- length(x) 

    if(l > 1) { 
     p <- ceiling(1/2) 
     a <- mergesort(x[1:p])   
     b <- mergesort(x[(p+1):l]) 
     return(mergelist(a,b))  
    } 
    lister <- list(number=0, data = x) 
    return(lister) 
}

這需要在向量x中進行排序。它正在像mergelist（）那樣返回一個列表，其number屬性與mergelist中的相同。

現在我的問題是，我有下面的例子：mergesort(c(11,10,9,15,6,12,17,8,19,7))，

應返回

$number [1] 22 
$data [1] 6 7 8 9 10 11 12 15 17 19

但它返回

$number 
[1] 30 

$data 
[1] 6 7 8 9 10 11 12 15 17 19

因此，這意味着它計算一個對比它不該'T。我不知道在哪裏。有人能告訴我我做錯了什麼嗎？

來源

2017-07-01 Numan Takács

應該不是你的代碼

p <- ceiling(**1**/2)

是這樣

p <- ceiling(**l**/2)

來源

2017-07-01 19:05:29 Prem

哥們我不知道怎麼感謝你纔好。 –

很高興它幫助:) – Prem

R中mergesort的比較次數

回答

相關問題