C：元素个数奇数的数组归并排序
C: Merge-Sort of an array with uneven number of elements
我一直在为我的 过程编程 class 分配作业，其中提供了一个无法完全运行的合并排序程序。它对具有偶数个整数的数组执行合并排序，但抛出具有奇数个整数的分段错误。
我了解排序是如何工作的，并且抛出分段错误是因为奇数导致分段错误，因为数组以某种方式被过度填充。我也知道解决方案将涉及测试原始数组是偶数还是奇数，然后根据此不同地将值传递给合并函数。尽管我确实了解该程序，但几周来我一直在用头撞墙，试图让它正常工作，我希望有人能给我一些建议。
在 post 进行此操作之前，我已经四处寻找答案，但所有其他示例都涉及使用结构的合并排序程序，这超出了我目前所学的范围。您将在下面的代码 I post 中看到。此外，完整的程序还涉及一些其他文件，但我只包括了 mergesort.c 文件和 merge.c 文件，正如我的教授向我保证的那样，这是唯一有任何更改的地方需要制作。 main 文件工作完美，只负责填充数组和调用 mergesort 函数。如果需要其他文件，请告诉我，我会 post 提供。我没有的唯一原因是因为我们使用的是 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++];
}
}
您的代码有一些问题：
包含预处理器指令不正确，请使用 #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 紧跟在相应的指针之后传递（为了保持一致性）。
而不是断言分配成功，你应该return一个失败代码并让调用者优雅地处理失败。
您可以将工作数组的开头用于所有合并操作。这提高了缓存效率。
这是包含所有这些更改的版本：
#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 可以 return 复制回的元素数量，在排序的情况下删除所有复制。
将左边的chunk复制到临时数组中，并合并到key数组中，可以减小临时数组的大小。
合并平衡的块大小而不是 2 的幂减少了非 2 的幂数组大小的比较总数，但使用递归方法更容易实现。
所以我找到了您的分段错误的来源。如果您仔细查看合并排序中的第一个内部 for 循环：
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，所以你最终在索引 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 的幂时，它只会忽略获得 "over" 2 的幂的部分......如果你明白我的意思？在我们做出解决分段错误的更改之前，它本来会尝试这样做但由于这个原因而失败（并且 return 一个错误）。
我们现在要做的是让它对他刚刚忽略的最后一片进行排序。我只会复制合并排序函数，因为它是唯一会改变的东西：
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
我一直在为我的 过程编程 class 分配作业，其中提供了一个无法完全运行的合并排序程序。它对具有偶数个整数的数组执行合并排序，但抛出具有奇数个整数的分段错误。
我了解排序是如何工作的，并且抛出分段错误是因为奇数导致分段错误，因为数组以某种方式被过度填充。我也知道解决方案将涉及测试原始数组是偶数还是奇数，然后根据此不同地将值传递给合并函数。尽管我确实了解该程序，但几周来我一直在用头撞墙，试图让它正常工作，我希望有人能给我一些建议。
在 post 进行此操作之前，我已经四处寻找答案，但所有其他示例都涉及使用结构的合并排序程序，这超出了我目前所学的范围。您将在下面的代码 I post 中看到。此外，完整的程序还涉及一些其他文件，但我只包括了 mergesort.c 文件和 merge.c 文件，正如我的教授向我保证的那样，这是唯一有任何更改的地方需要制作。 main 文件工作完美，只负责填充数组和调用 mergesort 函数。如果需要其他文件，请告诉我，我会 post 提供。我没有的唯一原因是因为我们使用的是 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++];
}
}
您的代码有一些问题：
包含预处理器指令不正确，请使用
#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紧跟在相应的指针之后传递（为了保持一致性）。而不是断言分配成功，你应该return一个失败代码并让调用者优雅地处理失败。
您可以将工作数组的开头用于所有合并操作。这提高了缓存效率。
这是包含所有这些更改的版本：
#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可以 return 复制回的元素数量，在排序的情况下删除所有复制。将左边的chunk复制到临时数组中，并合并到
key数组中，可以减小临时数组的大小。合并平衡的块大小而不是 2 的幂减少了非 2 的幂数组大小的比较总数，但使用递归方法更容易实现。
所以我找到了您的分段错误的来源。如果您仔细查看合并排序中的第一个内部 for 循环：
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，所以你最终在索引 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 的幂时，它只会忽略获得 "over" 2 的幂的部分......如果你明白我的意思？在我们做出解决分段错误的更改之前，它本来会尝试这样做但由于这个原因而失败（并且 return 一个错误）。
我们现在要做的是让它对他刚刚忽略的最后一片进行排序。我只会复制合并排序函数，因为它是唯一会改变的东西：
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