C:元素个数奇数的数组归并排序

Question

我一直在为我的程序化编程 类(class)做作业，其中为我们提供了一个无法完全运行的合并排序程序。它对具有偶数个整数的数组执行合并排序，但抛出具有奇数个整数的段错误。

我理解排序是如何工作的，并且抛出段错误是因为奇数导致段错误，因为数组以某种方式被过度填充。我也知道解决方案将涉及测试原始数组是偶数还是奇数，然后根据此不同地将值传递给合并函数。尽管我确实了解该程序，但几周来我一直在用头撞墙，试图让它正常工作，我希望有人能给我一些建议。

在发布这篇文章之前，我已经四处寻找答案，但所有其他示例都涉及使用结构的合并排序程序，这超出了我目前所学的范围。你会在我下面发布的代码中看到。此外，完整的程序还涉及一些其他文件，但我只包括了 mergesort.c 文件和 merge.c 文件，正如我所确信的那样我的教授，是唯一需要进行任何更改的地方。 main 文件工作完美，只负责填充数组和调用 mergesort 函数。如果需要其他文件，请告诉我，我会发布它们。我没有的唯一原因是因为我们使用的是 Linux shell，我还没有找到一个实用的方法来将代码从 shell 复制并粘贴到我自己的操作系统中，并且需要一段时间才能写出来。

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

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 预处理器指令不正确，要么使用 #include "mergesort.h"或 #include <mergesort.h> .

• 您必须计算传递给 merge() 的数组的大小正确，因此它不会读取超出最后一个 block 的末尾。按照目前的编码，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 routine是一个辅助函数，当之无愧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 的最后一个元素和 b 的第一个元素在merge允许在部分或完全排序的数组上大幅提高速度。

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

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

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