C: Mergesort - в чем ошибка? Неверный вывод (повтор) - PullRequest
Новая
       10

C: Mergesort - в чем ошибка? Неверный вывод (повтор)

1 голос
/ 20 марта 2011

Я написал этот "mergesort" на C. Я думаю, что где-то есть ошибка в копировании элементов в исходный массив. Кто-нибудь может мне помочь?

Огромное спасибо заранее. 

enter code here

 /*************************** Merge sort ********************************/
  #include <stdio.h>

  void merge(int arr[], int start1, int end1, int start2, int end2)
  {
   int temp[100], beg1, beg2, i;

   beg1=start1;
   beg2=start2;
   i=0;

   while((beg1<=end1)&&(beg2<=end2))
   {
     if(arr[beg1]<arr[beg2])
      {
        temp[i++]=arr[beg1++];
      }
     else
      {
        temp[i++]=arr[beg2++];
      }
   }
   if(beg1<end1) {
       while(beg1<=end1) temp[i++]=arr[beg1++];
   }

  if(beg2<end2) {  
       while(beg2<=end2) temp[i++]=arr[beg2++];
  }

  i=0;
  for(beg1=start1; beg1<=end1; beg1++)
  {
      arr[beg1]=temp[i++];
  }
 for(beg1=start2; beg1<=end2; beg1++)
  {
      arr[beg1]=temp[i++];
  }
}

 void mergesort(int arr[], int beg, int end)
 {
   int mid;

   if(beg<end) {
      mid=(beg + end)/2;
      mergesort(arr, beg, mid);
      mergesort(arr, mid+1, end);
      merge(arr, beg, mid, mid+1, end);
   }
 }

 int main()
 {
   int i;
   int arr[]={34, 3, 10, 78, 4, 0, 14};
   mergesort(arr, 0, 6);

   printf("Here are the sorted elements:\n");

   for(i=0; i<6; i++){
      printf("%d\t",arr[i]);
   }
   printf("\n");
 }

Output:
  [root@dhcppc0 sorting]# gcc mergesort.c
  [root@dhcppc0 sorting]# ./a.out

     Here are the sorted elements:
          0       0       3       0       10      10

1 Ответ

1 голос
/ 20 марта 2011

end1 и end2 являются действительными индексами, поэтому я не думаю, что у вас должны быть эти if утверждения здесь 

if(beg1<end1) {
   while(beg1<=end1) temp[i++]=arr[beg1++];
}

if(beg2<end2) {  
   while(beg2<=end2) temp[i++]=arr[beg2++];
}

что если beg1 == end1?

если beg1<end1, у вас осталось не менее 2 элементов массива в диапазоне [beg1, end1]. Если есть только один, вы должны скопировать его тоже. Вы должны оставить циклы без присмотра в операторах if. Измените код, представленный выше: 

//if(beg1<end1) {
   while(beg1<=end1) temp[i++]=arr[beg1++];
//}

//if(beg2<end2) {  
   while(beg2<=end2) temp[i++]=arr[beg2++];
//}

Кстати, ваш вид не стабилен. Чтобы исправить это, измените это условие 

if(arr[beg1]<arr[beg2])

до 

if(!(arr[beg2]<arr[beg1]))
...