gibt es ein Geheimnis aus meinem Code, Merge-Sort mit Prozess in rekursive Weise in C

Question

Ich bin nur ein Neuling. Ich habe ein Mystery-Problem von meinem Code, der eigentlich OS-Klassenzuweisung ist.

mein Code tatsächlich funktioniert, aber wenn ich mit mehr als 16 ganzen Zahlen versuchen,

Es gibt unsortiert Werte.

alle Werte unter 16 ganzen WORK.

Warum ist dieses Problem aufgetreten?

ist das ein Problem über die dynamische Speicher- oder Pipe-Puffergröße?

(. I`m unter Ubuntu 14.04, wenn es hilfreich)

mein Sortiercode ist:

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

und mein merge divide-Code ist:

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

Es scheint mir, dass Sie nicht die richtige Menge an Speicher zuordnen. Zum Beispiel:

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

Wird nur sizel Bytes zuweisen, während Sie brauchen:

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

Außerdem (beachten Sie, es ist kein Fehler) Sie die beiden if ‚s in Ihrem ersten Schnipsel vermeiden kann, weil:

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

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

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

ist logisch äquivalent (für Ihren Code):

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

es scheint, dass Sie verwenden keine rekursive Technik hier

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

dieser gegebene Funktionsaufruf wird die Arbeit von Divide tun, jetzt müssen Sie nur den Code für die Zusammenführung der Sequenzen schreiben. mehr Hilfe check here