問題在C++歸併排序實現

我在執行從僞代碼算法獲得兩個錯誤：問題在C++歸併排序實現

我的一個問題是int L[n1+1];錯誤：必須是一個常數;不能分配恆定的大小0.唯一的方法來運行這個是使大小數字爲10.我可能正在實施錯誤的psuedocode，這就是爲什麼我包含在上面的聲明。這可能是我下一個問題的原因。

我的其他問題是我打印只有一行代碼unsorted。我的打印功能完美無缺，適用於所有分類程序。我相信MERGE函數只運行一次。我在底部發布了排序的輸出。

我有一個數組A的隨機數發生器，從0到RAND_MAX。初始呼叫MERGESORT(A,1,n);

void MERGE(int *A, int p, int q, int r) 
{ 
    int n1 = q-(p+1); 
    int n2 = r-q; 

    //psuedocode states, let L[1..n1+1] & R[1..n1+1] be new arrays 

    int L[n1+1];   
    int R[n2+1];  

    for(int i=1; i<n1;i++) 
    { 
     L[i]=A[p+(i-1)]; 
    } 
    for(int j=1; j<n2; j++) 
    { 
     R[j] = A[q+j]; 
    } 
    L[n1+1]=NULL; //sentinel 
    R[n2+1]=NULL; //sentinel 
    int i=1; 
    int j=1; 
    for (int k=p; k<r; k++) 
    { 
     if(L[i]<=R[j]) 
     { 
      A[k]=L[i]; 
      i=i+1; 
     } 
     else 
     { 
      A[k]=R[j]; 
      j=j+1; 
     } 
    } 
} 

void MERGESORT(int *A,int p, int r) 
{ 
    if (p<r) 
    { 
     int q=floor((p+r)/2); 
     MERGESORT(A,p,q); 
     MERGESORT(A,q+1,r); 
     MERGE(A,p,q,r); 
    } 
}

隨着int L[10];和我A[10];我的輸出是：

Sort: 7474 28268 32506 13774 14411 
Press any key to continue . . .

如果有人可以只幫助這兩個問題，我更可能會得到它的工作。

來源

2013-10-25 GiBiT 09

'INT Q =地板（（P + R）/ 2）點樣所有的錯誤; ''地板'是不必要的。適用於整數的部分是無餘數的部分（小數位「被丟棄」）。 – dyp

如果您可以提供[SSCCE]（http://sscce.org），那就太好了。 – dyp

在C++數組中，基於0。所以它們將從L [0-> n]而不是L [1-> n + 1]運行。 –

您未能檢測到您的合併數組的末尾：

for (int k=p; k<r; k++) 
{ 

    // You need to check that i/j are still in range. 
    // otherwise the following test are not valid. 

    if ((i < n1) && (j < n2)) 
    { 
     if(L[i]<=R[j]) 
     { 
     A[k]=L[i]; 
     i=i+1; 
     } 
     else 
     { 
     A[k]=R[j]; 
     j=j+1; 
     } 
    } 
    else 
    { /* More work here */ 
    }

其他評論：

標識符都是國會MERGE歸併一般爲宏保留。如果你使用它們，你很可能會遇到問題。首選混合大小寫的函數名稱。

可以用矢量模擬數組：用C

// Simulate L[1..n1+1] 
minI = 1; 
maxI = n1-1; 
std::vector<int> const L(A+(minI-1), A+(maxI-1));

陣列++爲零索引。你似乎有一個錯誤（特別是在訪問數組的末尾）。我建議你從0開始計數而不是1.大多數C++代碼是用[begin ..1PastEnd）中的迭代器編寫的。我認爲如果你適應這種風格，你會發現你的算法更容易實現。

來源

2013-10-25 23:44:13

對我來說，似乎OP正在使用封閉範圍，例如[p，q]和[q + 1，r]。因此，我認爲它應該是'std :: vector const L（A + p，A + q + 1）;'並且對於第二個向量'A + q + 1，A + r + 1'。 – dyp

有趣我不知道宏，我在這本書中使用了一個算法，他們使用了大寫字母，我儘量使它儘可能地靠近 –

您的代碼有幾個問題，我在評論中指出了它們。這是一個最接近你的代碼的解決方案，它遠非最好的。考慮使用C++容器，例如std::vector。命名至少有爭議，當然合併排序應該作爲就地算法來實現。

//L and R are auxiliary arrays 
//preallocated with (inputSize/2 + 1) constant size 
void MERGE(int *A, int p, int q, int r, int* L, int* R) 
{ 
    if (p > q || q > r) 
    { 
     return; 
    } 

    int n1 = q - p + 1; 
    int n2 = r - q; 

    // note 0-based indices 
    int i = 0; 
    int j = 0; 

    for(;i < n1;i++) 
    { 
     L[i] = A[p + i]; 
    } 

    for(;j < n2;j++) 
    { 
     R[j] = A[q + j + 1]; //+1 because p + n1 - 1 == q + 0 
    } 

    //again - note 0-based indices 
    i = 0; 
    j = 0; 

    for (int k = p; k <= r; ++k) 
    { 
     // The most important fix - in your code you didn't check 
     // for left/right array bounds at all. 
     // Sentinel values aren't needed - size is known 
     if(i < n1 && (j >= n2 || L[i] <= R[j])) 
     { 
      A[k] = L[i]; 
      ++i; 
     } 
     else if (j < n2) 
     { 
      A[k] = R[j]; 
      ++j; 
     } 
    } 
} 

void MERGESORT(int* A, int p, int r, int* L, int* R) 
{ 
    if (p < r) 
    { 
     int q = (p + r)/2; //floor was redundant 
     MERGESORT(A, p, q, L, R); 
     MERGESORT(A, q+1, r, L, R); 

     MERGE(A, p, q, r, L, R); 
    } 
} 

void MERGESORT(int* A, int size) 
{ 
    int*L = new int[size/2 + 1]; //preallocate auxiliary arrays 
    int*R = new int[size/2 + 1]; //size/2 + 1 is what will be needed at most 

    MERGESORT(A, 0, size - 1, L, R); 

    delete L; 
    delete R; 
} 

int main() 
{ 
    int A[5]{ 7474, 28268, 32506, 13774, 14411 }; 

    MERGESORT(A, 5); 

    for (int i = 0;i < 5;++i) 
    { 
     std::cout << A[i] << std::endl; 
    } 

    return 0; 
}

輸出：

幸得也DyP在先前版本:)

來源

2013-10-25 23:56:37 BartoszKP

問題在C++歸併排序實現

回答

相關問題