运行实施合并排序时的时髦结果

Question

我正在尝试实施合并排序以进行时间分析，在测试用于实施此目的的函数时，我得到了一些奇怪的结果并且无法弄清楚原因。我正在生成一个包含 20 个随机值的数组，然后调用 mergeSort 然后打印 "sorted" 数组的结果。

没有错误信息，但结果不是预期的。输出似乎是针对前几个值排序的，然后是中间的一些 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++];
}

将其放在将 W 复制到 A 的最终 for 循环之前。

另一种方法是更改循环，使条件为 ||，这意味着只要任一数字在范围内，它就会继续。然后，您必须在使用之前测试数字是否在范围内。有很多方法可以做到这一点，一个简单的方法是先测试一下：

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
        }
    }
}

运行实施合并排序时的时髦结果

Funky Results when running implementation of Merge Sort

c++

arrays

sorting

mergesort

运行 实施合并排序时的时髦结果

Funky Results when running implementation of Merge Sort

c++

arrays

sorting

mergesort

运行实施合并排序时的时髦结果