我的代码有一个谜，在 C 中以递归方式使用进程合并排序

Question

我只是个新手。我的代码中有一个神秘的问题，实际上是 OS class 赋值。

我的代码确实有效，但是当我尝试使用超过 16 个整数时，

它 returns 未排序的值。

任何小于 16 个整数的值都可以。

为什么会出现这种问题？

这是关于动态内存或管道缓冲区大小的问题吗？

（如果有帮助，我在 Ubuntu 14.04 下。）

我的排序代码是：

void merge_conq(unsigned int *A, unsigned int *B, unsigned int *C, int size1, int size2) {

    unsigned int *a = A;
    unsigned int *b = B;
    unsigned int *c = C;
    int count_a = 0;
    int count_b = 0;

    while (count_a < (size1) && count_b < (size2)) {

        if (*a < *b) {
            *c = *a;
            a++;
            c++;
            count_a++;
        }
        else {
            *c = *b;
            b++;
            c++;
            count_b++;
        }
    }

    if (count_a == (size1)) {
        while( count_b < (size2)) {
            *c = *b;
            b++;
            c++;
            count_b++;
        }
    }
    else if(count_b == (size2)) {
        while(count_a < (size1)) {
        *c = *a;
        a++;
        c++;
        count_a++;
        }
    }
}

我的合并划分代码是：

unsigned int* merge(int start, int end, unsigned int* array) {

    //detecting status of children
    int status;
    int state1, state2;
    int fd1[2], fd2[2];
    state1 = pipe(fd1);
    state2 = pipe(fd2);
    if ( state1 == -1 ) {
        printf("error\n");
        exit(0);
    }
    if ( state2 == -1 ) {
        printf("error\n");
        exit(0);
    }

    int length = end - start + 1;
    int sizel, sizer;

    if ( (length % 2) == 0 ) {
        sizel = length / 2;
        sizer = length / 2;
    }
    else{
        sizel = (length / 2) + 1;
        sizer = length / 2;
    }

    pid_t child1 = fork();

    if ( child1 == 0 ) {
        end = (start + end) / 2;
        length = end - start + 1;
        if ( (length % 2) == 0 ) {
            sizel = length / 2;
            sizer = length / 2;
        }
        else {
            sizel = (length / 2) + 1;
            sizer = length / 2;
        }
        if ( start != end ) {
            unsigned int* a;
            a = merge(start, end, array);
            write(fd1[1], a, sizeof(int) * length);
            exit(0);
        }
        else {
            unsigned int last = array[start];
            write(fd1[1], &last, 4);
            exit(0);
        }
    }
    else {
        //right child
        pid_t child2 = fork();

        if ( child2 == 0 ) {
            start = ((start + end) / 2) + 1;
            length = end - start + 1;
            if ( (length % 2) == 0 ) {
                sizel = length / 2;
                sizer = length / 2;
            }
            else {
                sizel = (length / 2) + 1;
                sizer = length / 2;
            }
            if ( start != end ) {
                unsigned int* a;
                a = merge(start, end, array);

                write(fd2[1], a, sizeof(int) * length);
                exit(0);
            }
            else {
                unsigned int last = array[start];
                write(fd2[1], &last, 4);
                exit(0);
            }
        }
        //parent code
        else {
            unsigned int *left=(unsigned int*)malloc(sizel);
            unsigned int *right=(unsigned int*)malloc(sizer);
            unsigned int *result=(unsigned int*)malloc(length);
            child1  = wait( &status);
            child2  = wait( &status);
            read(fd1[0], left, sizeof(unsigned int) * sizel);
            int k;
            for ( k = 0; k < sizel; k++) {
                printf("--%u--", left[k]);
            };
            printf("\n");
            read(fd2[0], right, sizeof(unsigned int) * sizer);
            int s;
            for ( s = 0; s < sizer; s++ ) {
                printf("..%u..",right[s]);
            };
            printf("\n");
            merge_conq(left, right, result, sizel, sizer);
            /*
            int i;
            for( i = 0; i < length; i++ ) {
                printf("**%u**",result[i]);
            };
            printf("\n");
            */
            return result;
        }
    }
}

Answer 1

看来你这里没有使用递归技术

void merge(int arr_new[],int p, int q)
{
 int mid;
 if(p<q)
  {
   mid=(q+p)/2;
   merge(arr_new,p,mid);
   merge(arr_new,mid+1,q);
   merge_sequence(arr_new,p,mid,q);
  }
}

这个给定的函数调用将完成除法的工作，现在您只需要编写合并序列的代码。更多帮助 check here

Answer 2

在我看来，您没有分配正确的内存量。例如：

unsigned int *left=(unsigned int*)malloc(sizel);

只会分配 sizel 个字节，而您需要：

unsigned int *left = malloc( sizel * sizeof(unsigned int) );

此外，（注意，这不是错误）您可以在第一个代码段中避免使用两个 if，因为：

while ( count_a < (size1) && count_b < (size2) ) {    
    // ...
}

if ( count_a == (size1) ) {
    while( count_b < (size2)) {
        // ...
    }
}

else if( count_b == (size2) ) {
    while(count_a < (size1)) {
    // ...
    }
}

在逻辑上等同于（对于您的代码）：

while ( count_a < size1  &&  count_b < size2 ) {    
    // ...
}

while( count_b < size2 ) {
    // if you end up here then count_a == size1
}

while( count_a < size1 ) {
    // sure count_b == size2
}

我的代码有一个谜，在 C 中以递归方式使用进程合并排序

there is a mystery from my code, merge sort using process in recursive way in C

c

ubuntu

fork

mergesort

dynamic-memory-allocation