在合并排序算法中得到奇怪的结果[C]

Question

我一直在基于动态数组结构在 C 中实现归并排序算法。我一步一步地跟着伪代码，但我没有达到目的。以下是我如何定义我的结构以及如何创建和初始化它：

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

这里是合并排序的实现：

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0; 
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {     
            param->memory[k] = r->memory[j];
            j++;
            k++;      
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

当我在 [18, 14, 20, 16, 12] 等数组上调用该函数时，我得到了相同的相同数组。我尝试添加一些 printf() 在 mergesort 函数中，我发现它似乎正确地对数组进行了切片。所以问题一定出在dynarray_merge()函数中。我检查第一个数组中的元素是否大于另一个数组中的元素的方式对我来说似乎是正确的，所以我完全被卡住了。

我正在发布我的代码的可编译示例，以更好地向您展示我的意思。

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

typedef struct dynarray {
    void **memory;
    size_t allocated;
    size_t used;
    int index;
} dynarray;

//creates a new, empty, dynarray
void create_dynarray(dynarray **array, size_t size) {
    *array = calloc(size, sizeof **array);
    (*array)->memory = NULL;
    (*array)->allocated = 0;
    (*array)->used = 0;
    (*array)->index = -1;
}

//adds a new element at the bottom of dynarray
void add_elem(dynarray *array, void *data) {
    size_t toallocate;
    size_t size = sizeof(void *);
    if ((array->allocated - array->used) < size) { // if M - N ...
        toallocate = array->allocated == 0 ? size : (array->allocated * 2);
        array->memory = realloc(array->memory, toallocate);
        array->allocated = toallocate;
    }

    array->memory[++array->index] = data;
    array->used = array->used + size;
}

//get length of the dynarray
int dynarray_length(dynarray *array) {
    return array->index + 1;
}

//retrieves an element in a specific position of the dynarray
void *get_i_elem(dynarray *array, int index) {
    if (index < 0 || index > array->index)
        return NULL;

    return array->memory[index];
}

//function used to mergesort the array
void *dynarray_merge(dynarray *param, dynarray *l, dynarray *r, int size) {
    int i = 0,j = 0, k = 0;    
    while (i < size/2 && j < size - size / 2) {
        if (l->memory[i] < r->memory[j]) {
            param->memory[k] = l->memory[i];  
            i++;
            k++;
        } else {
            param->memory[k] = r->memory[j];
            j++;
            k++;    
        }
    }
    while (i < size / 2) {
        param->memory[k] = l->memory[i];
        i++;
        k++;
    }
    while (j < size - size / 2) {
        param->memory[k] = r->memory[j];
        j++;
        k++;
    }
    return param;
}

//function used to slice the dynarray in two subarrays and call merge function
void *dynarray_mergesort(dynarray *param) {
    if (dynarray_length(param) > 1) {
        size_t size = param->used / sizeof(void*);  
        size_t m = size / 2;
        size_t n = size - size / 2;
        struct dynarray *l; 
        create_dynarray(&l, m);
        struct dynarray *r;
        create_dynarray(&r, n);  

        for (size_t i = 0 ; i < m; i++) {
            add_elem(l, param->memory[i]);
        }
        for (size_t j = m; j < size; j++) {
            add_elem(r, param->memory[j]);
        }

        dynarray_mergesort(l);
        dynarray_mergesort(r);
        dynarray_merge(param, l, r, size);
    }  
    return param;
}

//print arrays, useful to test 
void print_array(dynarray *array) {
    for (int i = 0; i < dynarray_length(array); i++) {
        printf("%d\t", *(int *)get_i_elem(array, i));
        //puts("");
    }
}

int main() {
    struct dynarray *a;
    create_dynarray(&a, 5);
    int arr[5] = { 18, 14, 20, 16, 12};
    int *ap = malloc(sizeof(int));
    int *bp = malloc(sizeof(int));
    int *cp = malloc(sizeof(int));
    int *dp = malloc(sizeof(int));
    int *ep = malloc(sizeof(int));
    *ap = arr[0];
    *bp = arr[1];
    *cp = arr[2];
    *dp = arr[3];
    *ep = arr[4];
    add_elem(a, ap);
    add_elem(a, bp);
    add_elem(a, cp);
    add_elem(a, dp);
    add_elem(a, ep);
    printf("\nbefore mergesort\n");
    print_array(a);
    puts("");
    printf("\nafter mergesort\n");
    dynarray_mergesort(a);
    print_array(a);
}

Answer 1

问题是你如何比较元素：

if (l->memory[i] < r->memory[j]) ...

在这里，你比较的是指针，而不是指向的值。您从 main 中的 malloc 调用中获得这些指针，这些指针为您提供升序地址。

您对动态数组的实现使用 void * 作为元素的类型，因此它可以用于任何类型的元素。您的合并排序不知道使用哪种类型，因此不知道如何比较。

您可以像 qsort 那样为排序函数提供回调函数：

typedef int VoidPointerCmp(const void *a, const void *b);

然后将这个函数传递给你的两个归并排序函数：

void *dynarray_mergesort(dynarray *param, , VoidPointerCmp *cmp) ...

并像这样比较您的项目：

if (cmp(l->memory[i], r->memory[j]) < 0) ...

适合整数的比较函数如下所示：

int int_cmp(const void *pa, const void *pb)
{
    const int *a = pa;
    const int *b = pb;

    if (*a < *b) return -1;
    if (*a > *b) return 1;
    return 0;
}

在main中调用：

dynarray_mergesort(a, int_cmp);

一些注意事项：

您为每个条目分配内存。这是没有必要的。您可以使 void 指针指向现有数组的元素：
```
for (int i = 0; i < 5; i++) add_elem(a, &arr[i]);
```
排序不会影响原数组arr.
您没有释放分配的内存或破坏您的动态数组。您可能应该为动态数组编写一个析构函数，并在使用它们后清理临时数组 l 和 r。
我认为您没有正确使用 used 字段。您可能不需要它：拥有分配的大小和数组的当前长度就足够了。（您可以用长度替换索引。）

在合并排序算法中得到奇怪的结果[C]

Getting strange results in mergesort algorithm[C]

c

algorithm

mergesort

dynamic-arrays