C:合并阵列的合并，元素数量不均

Question

我一直在为我的程序编程类工作，其中为我们提供了一个不完全运行的合并程序程序。它在带有偶数整数的数组上执行合并 - 符号，但是用奇数的整数抛出了分割故障。

我了解排序的工作原理，并且正在抛出分割故障，因为奇数导致分割故障，因为该数组以某种方式被填满。我还了解，该解决方案将涉及测试原始数组是否均匀或奇怪，然后根据此而将值传递给合并函数。尽管我对该计划的了解确实了解，但我一直在墙上撞了数周，试图使它正常工作，我希望有人能给我一些建议。

在发布此内容之前，我已经对答案进行了很多关注，但是所有其他示例都涉及与结构合并程序，这超出了我到目前为止所学到的。您将在我下面发布的代码中看到。另外，完整程序还涉及其他一些文件，但是我仅包括mergesort.c文件和merge.c文件，正如我的教授向我保证的那样，这是唯一需要进行任何更改的地方。main文件可完美地工作，并且仅负责填充数组并调用mergesort功能。如果需要其他文件，请告诉我，我将发布它们。我没有的唯一原因是因为我们使用了Linux Shell，而且我还没有找到一种实用的方法来将代码从外壳复制到我自己的操作系统，并且需要一段时间才能写出它。/p>

事先感谢您提供的任何指示。这是代码。

Mergesort.c

#include <"mergesort.h">
void mergesort(int key[], int n) //key is the array, n is the size of key
{
    int j, k, m, *w;
    w = calloc(n, sizeof(int));
    assert(w != NULL);
    for (k = 1; k < n; k *= 2) {
        for (j = 0; j < n - k; j += 2 * k) {
            merge(key + j, key + j + k, w + j, k, k);
        }
        for (j = 0; j < n; ++j) {
            key[j] = w[j];
        }   
    }
    free(w);
}

MERGE.C

#include "mergesort.h"
void merge(int a[], int b[], int c[], int m, int n) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }   
    }
    while (i < m) {
        c[k++] = a[i++];
    }
    while (j < n) {
        c[k++] = b[j++];
    }   
}

Answer 1

您的代码有一些问题：

• 包括使用#include "mergesort.h"或#include <mergesort.h>。

• 您必须正确计算传递给merge()的数组的大小，以免它在最后一个块的末尾读取。如当前所编码，n必须是2的力量，以避免不确定的行为。

这是您的目的mergesort.c的校正版本：

#include "mergesort.h"
void mergesort(int key[], int n) {
    // key is the array, n is the number of elements
    int i, j, k, m;
    int *w;
    // allocate the working array
    w = calloc(n, sizeof(int));
    // abort the program on allocation failure
    assert(w != NULL);
    // for pairs of chunks of increasing sizes
    for (k = 1; k < n; k *= 2) {
        // as long as there are enough elements for a pair
        for (j = 0; j + k < n; j = j + k + m) {
            // compute the size of the second chunk: default to k
            m = k;
            if (j + k + m > n) {
                // chunk is the last one, size may be smaller than k
                m = n - j - k;
            }
            // merge adjacent chunks into the working array
            merge(key + j, key + j + k, w + j, k, m);
            // copy the resulting sorted list back to the key array
            for (i = 0; i < k + m; i++) {
                key[j + i] = w[j + i];
            }
        }
    }
    free(w);
}

这里还有一些有关此练习的其他评论，但是您可能不够先进，并且可能不允许更改API：

• 使用2个不同的源文件似乎过大。merge例程是一个辅助功能，应为static。现代编译器将在内联。

• 阵列大小应在相应的指针之后以size_t的形式传递（以保持一致性）。

• 而不是断言分配成功，您应该返回失败代码，并让调用者优雅处理失败。

• 您可以将工作数组的开始进行所有合并操作。这提高了缓存效率。

这是一个具有所有这些更改的版本：

#include "mergesort.h"
static void merge(int a[], size_t m, int b[], size_t n, int c[]) {
    size_t i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < m) {
        c[k++] = a[i++];
    }
    while (j < n) {
        c[k++] = b[j++];
    }
}
int mergesort(int key[], size_t n) { 
    // key is the array, n is the size of key
    // return 0 for success, -1 for failure with error code in errno
    size_t i, j, k, m;
    int *w;
    w = calloc(n, sizeof(int));
    if (w == NULL)
        return -1;
    for (k = 1; k < n; k *= 2) {
        for (j = 0; j + k < n; j += k + m) {
            m = k;
            if (j + k + m > n) {
                m = n - j - k;
            }
            merge(key + j, k, key + j + k, m, w + j);
            // copy the sorted chunk back to the key array
            for (i = 0; i < k + m; i++) {
                key[j + i] = w[i];
            }
        }
    }
    free(w);
    return 0;
}

您可以通过删除功能merge()中索引变量的几乎一半的测试来进一步改善实现：

static void merge(int a[], size_t m, int b[], size_t n, int c[]) {
    /* always called with m > 0 and n > 0 */
    for (size_t i = 0, j = 0, k = 0;;) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
            if (i == m) {
                while (j < n) {
                    c[k++] = b[j++];
                }
                break;
            }
        } else {
            c[k++] = b[j++];
            if (j == n) {
                while (i < m) {
                    c[k++] = a[i++];
                }
                break;
            }
        }
    }
}

您可以使用这些进一步的想法来改善mergesort和merge：

• 比较a的最后一个元素和merge中b的第一个元素允许在部分或完全排序的数组上进行大量改进。

• merge可以返回要复制的元素的数量，在排序的情况下删除所有复制。

• 通过将左侧块复制到临时数组并合并到key数组中，您可以减小临时数组的大小。

• 合并平衡块大小而不是2的功率减少了2个数组大小的非功率的比较总数，但是使用递归方法更容易实现。

Answer 2

，所以我发现了您的分割错误在哪里开始。如果您仔细观察Mergesort中的第一个内部循环：

        for(j = 0; j < n - k; j += 2 * k)
        {
            merge(key + j, key + j + k, w + j, k, k);
        }  

您会注意到，该条件并没有真正与您对合并功能作为数组切片的边界所提供的内容相吻合。条件为j < n - k，因此j的最大值为n - k - 1。但是，在您合并的参数中，您通过的第二个阵列板从key + j + k开始，并说它的大小k，因此您最终以index j + k + k - 1占用，如果您用最大值替换了j，则获得n - k - 1 + k + k - 1 = n。这意味着您正在告诉他可以进行合并功能，直到索引n。由于键的大小为n，因此没有索引n。那么，您必须如何重写状况？我们刚刚计算了合并将访问的最大索引：j + k + k - 1。因此，这意味着您只需要将j + k + k - 1 < n设置为条件即可。这意味着：

        for(j = 0; j <= n - (k*2); j += 2 * k)
        {
            merge(key + j, key + j + k, w + j, k, k);
        } 

现在，我们摆脱了细分故障，我们可以转到第二部分：使其适合所有尺寸。它仅适用于尺寸的原因是2（甚至不是所有尺寸：尝试对此[2，3，5，6，4，1]）的功率，这是因为您的k。k设置了确定将在循环中合并的切片的大小。k在每回合后都会乘以2，因此它只会获得2个功率的尺寸！当它不是2的力量时，它将忽略"超越" 2的功能的部分...如果您明白了我的意思？在解决解决分段错误的更改之前，它将尝试这样做，但出于这个原因失败（并返回错误）。我们现在要做的就是使它排序他只是忽略的最后一个切片。我将仅复制Mergesort功能，因为这是唯一会改变的事情：

void mergesort(int key[], int n) //key is the array, n is the size of key
{
    int j, k, neglected, *w;
    w = calloc(n, sizeof(int));
    assert(w != NULL);
    for(k = 1; k < n; k *= 2){
        for(j = 0; j <= n - (k*2); j += 2 * k){
            merge(key + j, key + j + k, w + j, k, k);
        }
        //size of part that got neglected (if it could fully be divided in slices of 2*k, this will be 0)
        neglected = n % (2*k);
        //copy everything except the neglected part (if there was none, it will copy everything)
        for(j = 0; j < n-neglected; ++j) {
            key[j] = w[j];
        }
        if(neglected != 0 && neglected < n){ //couldn't devide it fully in slices of 2*k ==> the last elements were left out! merge them together with the last merged slice 
            merge(key + n - (2*k) - neglected, key + n-neglected, w + n - (2*k) - neglected, 2*k, neglected);
            for(j = n - (2*k) - neglected; j < n; ++j) { //copy the part we just merged
                key[j] = w[j];
            }
        }
        for(j = 0; j < n; ++j) {
            key[j] = w[j];
        }
    }
    free(w);
}

另外，我的编译器抱怨您不使用的变量：m