合併排序問題，當刪除陣列複製步驟

Question

我一直有一個問題，我無法調試相當一段時間。我試圖通過在「C++算法」一書中遵循Robert Sedgewick的算法來實現MergeSort算法，而不需要額外的數組複製步驟。
該算法的簡短描述：

遞歸程序被設置排序B，留在一個結果。因此，遞歸調用是爲了將結果保留在b中，並且我們使用基本的合併程序將這些文件從b合併到a中。這樣，所有的數據移動都是在合併過程中完成的。

問題是我找不到任何邏輯錯誤，但排序不正確。數據被覆蓋到某處，我無法確定導致此問題的邏輯錯誤。數據在程序結束時被排序，但它不再是相同的數據。
例如，輸入數組：{ A, Z, W, B, G, C }產生數組：{ A, G, W, W, Z, Z }。

我明顯可以看出它肯定是某個地方的邏輯錯誤，但我一直在試圖調試這個很長一段時間，我認爲一組新的眼睛可能會看到我失蹤的原因，因爲我真的可以沒有發現任何錯誤。

的完整代碼我運行：

//Here is my complete code that I run and that behaves as specified above. 

#include <iostream> 
#include <stdlib.h> 

using namespace std; 

// function to print the array 
void print(char * a[],int l, int r) 
{ for(int i=l;i<=r;i++) cout << (i+1) << ": " << a[i] << endl; } 

static const int M = 1; 

void insertion(char** a, int l, int r) 
{ int i,j; 
    char * temp; 
    for(i=1;i<r+1;i++) 
    { temp = a[i]; 
    j = i; 
    while((j>0) && strcmp(a[j-1],temp)>0) 
    { a[j] = a[j-1]; 
     j = j - 1; } 
    a[j] = temp; } } 

//merging a and b into c 
void merge(char ** c,char ** a, int N, char ** b, int M) 
{ for (int i=0, j=0, k=0; k<(N+M); k++) 
    { if(i == N) {c[k] = b[j++]; continue; } 
if(j == M) {c[k] = a[i++]; continue; } 
c[k] = strcmp(a[i], b[j])<0 ? a[i++] : b[j++]; } } 

void mergesortAux(char ** a, char ** b, int l, int r) 
{ if(r-l <= M) { insertion(a, l, r); return; } 
    int m = (l+r)/2; 
    mergesortAux(b, a, l, m);  //merge sort left 
    mergesortAux(b, a, m+1, r);  //merge sort right 
    merge(a+l,b+l,m-l+1,b+m+1,r-m); }  //merge 

void mergesort(char ** a,int l, int r, int size) 
{ static char ** aux = (char**)malloc(size*sizeof(char*)); 
    for(int i = l; i<size; i++) aux[i] = a[i]; 
    mergesortAux(a,aux,l,r); } 
//free(aux); } I removed this piece of code as suggested, I realize it's unnecessary 

int main(int argc, char * argv[]) 
{ int size = 6; 
    char **data = (char**)malloc(size*sizeof(char*)); 
    data[0] = "A"; 
    data[1] = "Z"; 
    data[2] = "W"; 
    data[3] = "B"; 
    data[4] = "G"; 
    data[5] = "C"; 

    print(data,0,size-1); 
    printf("---------------------------\n"); 

    mergesort(data,0,size-1,size); 

    printf("---------------------------\n"); 
    print(data,0,size-1); 
    return 0; 
} 

輸出：

1: A 
2: Z 
3: W 
4: B 
5: G 
6: C 
--------------------------- 
--------------------------- 
1: A 
2: G 
3: W 
4: W 
5: Z 
6: Z 

Answer 1

你的整個代碼是完全搞砸了。

您將輸入數組與輸出數組混淆在一起，並嘗試在所有時間進行排序。你的代碼格式很糟糕。你的變量名稱很糟糕。您正在使用冗餘參數（您正在傳遞size以及索引範圍l和r）。你混淆了索引範圍的含義。這段代碼有很多錯誤，我可以在這裏整晚描述一下。

然而，只有最後一個是關鍵的位置：

在這一行：

{ if(r-l <= M) { insertion(a, l, r); return; } 

您嘗試陣列a的l到r部分進行排序。但是，l索引在insertion函數中未使用，所以它將a從0修改爲r（含）。 r表明它是正確的索引，但在此方法中用作數組的大小。

最簡單的解決方法是將其改爲：

if(r-l <= M) { insertion(a+l, l, r-l); return; } 

但固定insertion方法，妥善處理指標可能是一個更好的主意。

此外，我強烈建議您清理整個代碼。這是不可維護的。這是不可讀的。這是C的最黑暗的一面。我永遠不會理解爲什麼人們不能使用可理解的函數/變量名稱，使用結構體來表示複合概念，並將邏輯分割成小的可讀的部分。就好像寫在C中一樣，你認爲你正在設置處理器寄存器中的各個位，並且不能使用長度超過1個字符的變量名。

即使你 - 這個代碼的作者有理解它的問題。這是一個強烈的暗示，有一些嚴重的問題吧:)

對不起，我無奈，我無法抗拒的拼圖，並浪費了很多時間在這:)