運行實施合併排序時奇怪的結果

Question

我想實現合併排序進行時間分析和測試用於實現此功能時，我得到一些時髦的結果，並找不出原因。我生成了一個20個隨機值的數組，然後調用mergeSort，然後打印「排序」數組的結果。

沒有錯誤消息，但結果不是預期的結果。輸出將顯示爲前幾個值的排序，然後是0之間的值，並且最終以非常大的值結束，即使生成的數字應該在1和100之間。輸出如下：

>sort-timings 
1 3 8 11 0 14 17 24 0 0 29 96 20 2293400 3 2293400 2293400 26085452 1971496002 1971496002 >Exit code: 0 Time: 0.4162 

我已經實現的代碼是：

void merge(int A[], int leftStart, int leftEnd, int rightStart, int rightEnd, int W[]) { 
    //Merge A[leftStart]....[leftEnd] with A[rightStart]...[rightEnd] 
    //Into W, indexed by k, copy resulting W into A 
    int i = leftStart; 
    int j = rightStart; 
    int k = leftStart; 
    while(i <= leftEnd && j <= rightEnd) { 
     if(A[i] < A[j]) { 
     W[k++] = A[i++]; 
     } 
     else if(A[i] > A[j]) { 
     W[k++] = A[j++]; 
     } 
     else { 
     W[k++] = A[i++]; 
     W[k++] = A[j++]; 
     } 
    } 
    for(i = leftStart; i <= rightEnd; i++) { 
     A[i] = W[i]; 
    } 
} 

void mergeSort(int A[], int low, int high, int W[]) { 
    //mergeSort Helper Function 
    if(low == high) { 
     return; //1 element is sorted 
    } 
    int mid = (low + high)/2; 
    mergeSort(A, low, mid, W); //Sort first half 
    mergeSort(A, mid + 1, high, W); //Sort second half 
    merge(A, low, mid, mid + 1, high, W); 
    return; 
} 

void mergeSort(int A[], int W[], int n) { 
    mergeSort(A, 0, n - 1, W); 
} 

void generateRandomArray(int A[], int n) { 
    unsigned int seed = time(0); 
    srand(seed); 
    for(int i = 0; i < n; i++) { 
     A[i] = (rand() % 100) + 1; // 1 <= A[i] <=10000 
    } 
} 

int main() { 
    const int ARRAY_SIZE = 20; 
    int array[ARRAY_SIZE]; 
    int tempArray[ARRAY_SIZE]; 
    generateRandomArray(array, ARRAY_SIZE); 
    mergeSort(array, tempArray, ARRAY_SIZE); 
    for(int i = 0; i < ARRAY_SIZE; i++) { 
     cout << array[i] << " "; 
    } 
} 

Answer 1

您及早停止你的merge迴路。目前，當i超出範圍或j超出範圍時，會停止某些值，但這些值不會複製到W，從而導致輸出中未初始化的值。

解決這個問題的一個簡單方法是在完成主循環後複製剩餘的值。如果循環完成，因爲i超出範圍，您想要複製j的其餘部分，同樣如果循環完成，因爲j超出範圍，則需要複製i的其餘部分。

您可以通過主循環後加入循環，以確保雙方i和j達到其範圍的末端實現這一點：

while (i <= leftEnd) { 
    W[k++] = A[i++]; 
} 
while (j <= rightEnd) { 
    W[k++] = A[j++]; 
} 

把這個最終for循環之前那份W爲A。

另一種替代方法是更改​​循環，以便條件爲||，這意味着它將在任一數字處於範圍內時繼續。在使用之前，您必須測試一個數字是否在範圍內。有許多方法可以做到這一點，一個簡單的方法是，先測試一下：

while (i <= leftEnd || j <= rightEnd) { 
    if (j > rightEnd) { 
     W[k++] = A[i++]; 
    } 
    else if (i > leftEnd) { 
     W[k++] = A[j++]; 
    } 
    else if (A[i] < A[j]) { 
    ... 

Answer 2

使用標誌（mtoa）跟蹤哪個方向的合併基於遞歸的水平備用版本，避免複製數據。它只在TopDownMerge（）中增加一個索引後檢查索引是否超出範圍。我不確定這是否會造成顯着的性能差異。

void TopDownMergeSort(int a[], int b[], size_t n) 
{ 
    if(n < 2) 
     return; 
    TopDownSplitMerge(a, b, 0, n, true); 
} 

void TopDownSplitMerge(int a[], int b[], size_t ll, size_t ee, bool mtoa) 
{ 
size_t rr; 
    if ((ee - ll) == 1){     // if size == 1 
     if(!mtoa)       // copy to b if merging a to b 
      b[ll] = a[ll]; 
     return; 
    } 
    rr = (ll + ee)>>1;      // midpoint, start of right half 
    TopDownSplitMerge(a, b, ll, rr, !mtoa); 
    TopDownSplitMerge(a, b, rr, ee, !mtoa); 
    if(mtoa)        // if merging to a, merge b to a 
     TopDownMerge(b, a, ll, rr, ee); 
    else         // else merge a to b 
     TopDownMerge(a, b, ll, rr, ee); 
} 

void TopDownMerge(int a[], int b[], size_t ll, size_t rr, size_t ee) 
{ 
    size_t o = ll;       // b[]  index 
    size_t l = ll;       // a[] left index 
    size_t r = rr;       // a[] right index 
    while(1){        // merge data 
     if(a[l] <= a[r]){     // if a[l] <= a[r] 
      b[o++] = a[l++];    // copy a[l] 
      if(l < rr)      // if not end of left run 
       continue;     //  continue (back to while) 
      while(r < ee){     // else copy rest of right run 
       b[o++] = a[r++]; 
      } 
      break;       //  and return 
     } else {       // else a[l] > a[r] 
      b[o++] = a[r++];    // copy a[r] 
      if(r < ee)      // if not end of right run 
       continue;     //  continue (back to while) 
      while(l < rr){     // else copy rest of left run 
       b[o++] = a[l++]; 
      } 
      break;       //  and return 
     } 
    } 
}