0

我正在尝试提出一种算法，该算法使用与 C 库中定义的 qsort 函数相同的参数递归调用合并排序函数。但是，尽管我的值打印出来了，但它们并不按顺序排列。有人可以看看我的功能并告诉我如何纠正这个问题吗？我还包括我使用的比较功能。提前致谢

  int cmp (const void *first, const void *second)
    {  
        if (first < second)
            return -1;
        else if (first > second)
            return 1;
        else
            return 0;
    }



    static void msort (void *b,size_t n,size_t s, int(*cmp)(const void*,const void*) )

    {
        char *tmp;

        void *t;
        if ((t = malloc(s*n)) == NULL)
        {
            printf("\nError: No Memory.");
            return;
        }   
        char *b1, *b2;
        size_t n1, n2;



        n1 = n / 2;
        n2 = n - n1;
        b1 = b;
        b2 = (char *) b + (n1 * s);

        if (n2 <= n1)
            return;

        msort (b1, n2, s, cmp);
        msort (b2, n1+1, s, cmp);

        tmp = t;

        while (n1 > 0 && n2 > 0)
        {
            if ((*cmp) (b1, b2) <= 0)
            {
                memcpy (tmp, b1, s);
                tmp += s;
                b1 += s;
                --n1;
            }
            else
            {
                memcpy (tmp, b2, s);
                tmp += s;
                b2 += s;
                --n2;
            }
        }
        if (n1 > 0)
            memcpy (tmp, b1, n1 * s);
        memcpy (b, t, (n - n2) * s);
    }

这是我的主要内容。我遗漏了您在此处看到的一些功能。

int main()
{
    int n;
    int *a, *b, *c;

printf("enter n: ");
if(scanf("%d", &n) != 1 || n < 10)
{
    fprintf(stderr, "bad input.  goodbye\n");
    abort();
}

printf("sizeof(double) %d\n", sizeof(double) );

printf("running experiments with n=%d\n", n);

a = gen_int_array(n, 5000);
//b = clone_int_array(a, n);
c = clone_int_array(a, n);


//ssort(a, n);
//isort(b, n);
//msort_int(c, n);

//msort_int(d, n);
msort (c, n, sizeof(int), cmp );



if(n<50)
dump_int_array(c, n);

free(a);
free(b );
free(c);

}

4

1 回答 1

1

一个问题是您的比较功能；它正在比较两个指针，仅此而已 - 而不是指向的值。由于您没有向我们展示您正在合并排序的数组的定义，因此我们无法轻松提供更多帮助。但是，假设您正在对 的数组进行排序int，那么比较器可能是：

int comparator(void const *v1, void const *v2)
{
    int i1 = *(int *)v1;
    int i2 = *(int *)v2;
    if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return +1;
    else
        return 0;
}

请注意，此公式避免了算术溢出和其他此类未定义的行为。它也是比较结构和其他更复杂值的不错模板；您可以添加更多对<和>测试，直到您没有更多标准来分隔两个值。

我们还可以观察到您的代码中肯定存在内存泄漏。您在函数内部分配了一个数组，但您不释放它或返回指向它的指针。

SSCCE 与原始msort()和comparator()

SSCCE 是一个简短的、独立的、正确的示例。

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

static int comparator(void const *v1, void const *v2)
{
    int i1 = *(int *)v1;
    int i2 = *(int *)v2;
    if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return +1;
    else
        return 0;
}

static void sort_check(int *array, size_t n)
{
    size_t fail = 0;

    for (size_t i = 1; i < n; i++)
    {
        if (array[i-1] > array[i])
        {
            fprintf(stderr, "Elements %zu (value %d) and %zu (value %d) are out of order\n",
                    i-1, array[i-1], i, array[i]);
            fail++;
        }
    }
    if (fail != 0)
        exit(1);
}

static void msort(void *b, size_t n, size_t s, int(*cmp)(const void*, const void*) )
{
    char *tmp;
    void *t;

    if ((t = malloc(s*n)) == NULL)
    {
        fprintf(stderr, "Error: No Memory.\n");
        return;
    }

    char *b1, *b2;
    size_t n1, n2;

    n1 = n / 2;
    n2 = n - n1;
    b1 = b;
    b2 = (char *) b + (n1 * s);

    if (n2 <= n1)
        return;

    msort (b1, n2, s, cmp);
    msort (b2, n1+1, s, cmp);

    tmp = t;

    while (n1 > 0 && n2 > 0)
    {
        if ((*cmp) (b1, b2) <= 0)
        {
            memcpy (tmp, b1, s);
            tmp += s;
            b1 += s;
            --n1;
        }
        else
        {
            memcpy (tmp, b2, s);
            tmp += s;
            b2 += s;
            --n2;
        }
    }
    if (n1 > 0)
        memcpy (tmp, b1, n1 * s);
    memcpy (b, t, (n - n2) * s);
}

static int *gen_int_array(size_t n, int max_val)
{
    int *a = malloc(n * sizeof(*a));
    if (a == 0)
    {
        fprintf(stderr, "Out of memory.\n");
        exit(1);
    }
    for (size_t i = 0; i < n; i++)
        a[i] = rand() % max_val;
    return(a);
}

static int *clone_int_array(int *master, size_t n)
{
    int *a = malloc(n * sizeof(*a));
    if (a == 0)
    {
        fprintf(stderr, "Out of memory.\n");
        exit(1);
    }
    for (size_t i = 0; i < n; i++)
        a[i] = master[i];
    return(a);
}

static void dump_array(FILE *fp, char const *tag, int *a, size_t n)
{
    char const *pad = "";
    fprintf(fp, "Array: %s (size %zu)\n", tag, n);
    for (size_t i = 0; i < n; i++)
    {
        fprintf(fp, "%s%d", pad, a[i]);
        pad = ",";
    }
    putc('\n', fp);
}

int main(int argc, char **argv)
{
    int n;
    int *a, *b;

    if (argc == 1)
        n = 10;
    else
        n = atoi(argv[1]);
    if (n <= 0)
        n = 10;

    printf("running experiments with n = %d\n", n);

    a = gen_int_array(n, 5000);
    b = clone_int_array(a, n);

    dump_array(stdout, "Unsorted", a, n);

    printf("Q-Sort\n");
    qsort(a, n, sizeof(int), comparator);
    dump_array(stdout, "Q-sorted", a, n);
    sort_check(a, n);

    printf("M-Sort\n");
    msort(b, n, sizeof(int), comparator);
    dump_array(stdout, "M-sorted", b, n);
    sort_check(b, n);

    free(a);
    free(b);

    return(0);
}

这个的输出（没有参数，在 Mac OS X 10.7.5 上）是：

running experiments with n = 10
Array: Unsorted (size 10)
1807,249,73,3658,3930,1272,2544,878,2923,2709
Q-Sort
Array: Q-sorted (size 10)
73,249,878,1272,1807,2544,2709,2923,3658,3930
M-Sort
Array: M-sorted (size 10)
1807,249,73,3658,3930,1272,2544,878,2923,2709
Elements 0 (value 1807) and 1 (value 249) are out of order
Elements 1 (value 249) and 2 (value 73) are out of order
Elements 4 (value 3930) and 5 (value 1272) are out of order
Elements 6 (value 2544) and 7 (value 878) are out of order
Elements 8 (value 2923) and 9 (value 2709) are out of order

如您所见，qsort()以正确的顺序获取数据。msort()不会改变任何东西的顺序。测试工具未设置为管理 0 行数据，但运行msort 1从msort()函数获取核心转储。当退化案例因分段错误而失败时，这总是一个不好的迹象。

大小为 1 的问题（和大小为 0）通过检查n进入msort()并返回 if来解决n <= 1。

下一个问题是条件 where if (n2 <= n1); 它早早返回。事实上，这个条件总是会触发一个偶数的n; 当您从 的奇数值开始时n，递归会生成一个偶数值，并且会提前返回。因此，排序永远不会发生。这是演示此行为的函数的（部分）检测版本：

static void msort(void *b, size_t n, size_t s, int (*cmp)(const void *v1, const void *v2) )
{
    if (n <= 1)
        return;     /* Already sorted */

    printf("-->> msort(%zu)\n", n);
    void *t = malloc(s*n);

    if (t == NULL)
    {
        fprintf(stderr, "Error: No Memory.\n");
        printf("<<-- msort(%zu)\n", n);
        return;
    }

    size_t n1 = n / 2;
    size_t n2 = n - n1;

    if (n2 <= n1)
    {
        fprintf(stderr, "Oops: %zu <= %zu\n", n2, n1);
        free(t);
        printf("<<-- msort(%zu)\n", n);
        return;
    }

    char *b1 = b;
    char *b2 = (char *) b + (n1 * s);

    msort(b1, n2, s, cmp);
    msort(b2, n1+1, s, cmp);

    char *tmp = t;

    while (n1 > 0 && n2 > 0)
    {
        if ((*cmp)(b1, b2) <= 0)
        {
            memcpy(tmp, b1, s);
            tmp += s;
            b1 += s;
            --n1;
        }
        else
        {
            memcpy(tmp, b2, s);
            tmp += s;
            b2 += s;
            --n2;
        }
    }
    if (n1 > 0)
        memcpy(tmp, b1, n1 * s);
    memcpy(b, t, (n - n2) * s);
    free(t);
    printf("<<-- msort(%zu)\n", n);
}

样品运行：

running experiments with n = 1
Array: Unsorted (size 1)
1807
Q-Sort
Array: Q-sorted (size 1)
1807
M-Sort
Array: M-sorted (size 1)
1807

running experiments with n = 2
Array: Unsorted (size 2)
1807,249
Q-Sort
Array: Q-sorted (size 2)
249,1807
M-Sort
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
Array: M-sorted (size 2)
1807,249
Elements 0 (value 1807) and 1 (value 249) are out of order

running experiments with n = 3
Array: Unsorted (size 3)
1807,249,73
Q-Sort
Array: Q-sorted (size 3)
73,249,1807
M-Sort
-->> msort(3)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
<<-- msort(3)
Array: M-sorted (size 3)
249,73,1807
Elements 0 (value 249) and 1 (value 73) are out of order

running experiments with n = 4
Array: Unsorted (size 4)
1807,249,73,3658
Q-Sort
Array: Q-sorted (size 4)
73,249,1807,3658
M-Sort
-->> msort(4)
Oops: 2 <= 2
<<-- msort(4)
Array: M-sorted (size 4)
1807,249,73,3658
Elements 0 (value 1807) and 1 (value 249) are out of order
Elements 1 (value 249) and 2 (value 73) are out of order

running experiments with n = 5
Array: Unsorted (size 5)
1807,249,73,3658,3930
Q-Sort
Array: Q-sorted (size 5)
73,249,1807,3658,3930
M-Sort
-->> msort(5)
-->> msort(3)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
<<-- msort(3)
-->> msort(3)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
-->> msort(2)
Oops: 1 <= 1
<<-- msort(2)
<<-- msort(3)
<<-- msort(5)
Array: M-sorted (size 5)
249,73,1807,3658,3930
Elements 0 (value 249) and 1 (value 73) are out of order

running experiments with n = 6
Array: Unsorted (size 6)
1807,249,73,3658,3930,1272
Q-Sort
Array: Q-sorted (size 6)
73,249,1272,1807,3658,3930
M-Sort
-->> msort(6)
Oops: 3 <= 3
<<-- msort(6)
Array: M-sorted (size 6)
1807,249,73,3658,3930,1272
Elements 0 (value 1807) and 1 (value 249) are out of order
Elements 1 (value 249) and 2 (value 73) are out of order
Elements 4 (value 3930) and 5 (value 1272) are out of order

这是你的问题......我已经展示了一些调试技术，并诊断了一些问题。请注意，跟踪函数进入和退出可能会有所帮助（尽管我作弊并且没有诊断大小 0 或 1 进入/退出）。特别是在递归代码中，它有助于识别函数的关键参数（这里，n虽然数组的开始地址也可能是相关的），以便可以检测到单独的调用。

我感到无聊，或粗心，或其他什么...此代码有效。递归调用中的更改，以及合并循环结束时的清理，以及复制回原始数组。并完全删除了可疑的if (n2 <= n1)块；我想不出它的目的。哦，还有更多诊断，在进入和退出时打印数组。

static void msort(void *b, size_t n, size_t s, int (*cmp)(const void *v1, const void *v2) )
{
    if (n <= 1)
        return;     /* Already sorted */

    printf("-->> msort(%zu)\n", n);
    dump_array(stdout, "Entry to msort()", (int *)b, n);
    void *t = malloc(s*n);

    if (t == NULL)
    {
        fprintf(stderr, "Error: No Memory.\n");
        printf("<<-- msort(%zu)\n", n);
        return;
    }

    size_t n1 = n / 2;
    size_t n2 = n - n1;

    char *b1 = b;
    char *b2 = (char *) b + (n1 * s);

    msort(b1, n1, s, cmp);
    msort(b2, n2, s, cmp);

    char *tmp = t;

    while (n1 > 0 && n2 > 0)
    {
        if ((*cmp)(b1, b2) <= 0)
        {
            memcpy(tmp, b1, s);
            tmp += s;
            b1 += s;
            --n1;
        }
        else
        {
            memcpy(tmp, b2, s);
            tmp += s;
            b2 += s;
            --n2;
        }
    }
    if (n1 > 0)
        memcpy(tmp, b1, n1 * s);
    else if (n2 > 0)
        memcpy(tmp, b2, n2 * s);
    memcpy(b, t, n * s);
    free(t);

    dump_array(stdout, "Exit from msort()", (int *)b, n);
    printf("<<-- msort(%zu)\n", n);
}
于 2013-02-12T02:59:51.087 回答