私のコードから謎があり、Cで再帰的にプロセスを使用してソートをマージする

Question

私はちょうど初心者です。 実際にOSクラスの割り当てである私のコードから謎の問題があります。

私のコードは実際に動作しますが、私は16以上の整数、

にしようとすると、それはソートされていない値を返します。

16個未満の任意の値WORK。

なぜこの種の問題が発生しましたか？

は、ダイナミックメモリまたはパイプバッファサイズに関する問題ですか？

（。Ubuntuの14.04下I`mそれが役に立つ場合）

私のソートコードです：

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

あなたは正しい量のメモリを割り当てていないようです。たとえば：

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

ほかに、あなたが最初のスニペットで2 if年代を避けることができます（注を、それは誤りではありません）：あなたが必要としながら、

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

は、唯一sizelバイトを割り当てます理由：

：

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 
} 

Answer 2

それはと思われますここで再帰的手法を使用していません。

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); 
    } 
} 

この関数呼び出しは分割作業を行います。シーケンスをマージするコードを書くだけで済みます。詳細help check here