реализация mergesort C

Question

я написал этот код на языке C на Xcode, следуя алгоритму сортировки слиянием.Проблема в том, что иногда я получаю EXC_BAD_ACCESS и не могу понять, где ошибка!Алгоритм слияния должен работать (я попробовал это вне функции слияния и работает!).Спасибо за вашу помощь и терпение!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 6

void mymerge (int v[], int i1,int i2, int last); //mergesort core: merge two ordinated arrays in one bigger ordinated array
void mymergesort (int v[], int lower, int upper);//mergesort
void printv (int v[],int lower, int upper);

int main () {
    int i;
    srand((unsigned int)time(NULL));
    int v[DIM];
    for (i=0; i<DIM; i++)
        v[i]=rand()%15;
    printv(v, 0, DIM-1);
    getc(stdin);
    mymergesort(v, 0, DIM-1);
    printv(v, 0, DIM-1);
}
void printv (int v[],int lower, int upper){
    int i;
    for (i=lower; i<=upper; i++)
    printf("%d\t",v[i]);
}
void mymergesort (int v[], int lower, int upper){
    int mid=(upper+lower)/2;
    if (upper<lower) {
        mymergesort(v, lower, mid);
        mymergesort(v, mid+1, upper);
        mymerge(v,lower,mid+1,upper);
    }
}
void mymerge (int v[], int i1,int i2, int last){
    int i=i1,j=i2,k=i1,*vout;
    vout=(int*)malloc((last-i1+1)*sizeof(int));
    while (i<i2 && j<=last) {
        if (v[i]<=v[j]) {
            vout[k++]=v[i++];
        }else {
            vout[k++]=v[j++];
        }
    }
    for (;i<i2;i++) vout[k++]=v[i];
    for (;j<=last;j++) vout[k++]=v[j];
    for (k=i1; k<=last; k++) v[k]=vout[k];
free(vout);
}

РЕДАКТИРОВАТЬ: большое спасибо!но я думаю, что есть другая проблема, когда я пытаюсь отсортировать массив большего размера (200 элементов), программа не работает (я получаю ошибку malloc: неверная контрольная сумма для освобожденного объекта - объект, вероятно, был изменен после освобождения).Но если я запускаю его из отладчика xCode, все работает нормально

Answer 1

Это: vout=(int*)malloc((last-i1)*sizeof(int)); неверно.

Во-первых, количество элементов, которое вы хотите, составляет last-i1+1, а не last-i1 - классический off-by-1.Этот тип ошибки является одной из причин, по которой в коде C принято делать нижние границы включительно и верхние границы исключающими - меньше +1 и -1, что вам нужно сделать, меньше возможностей испортить.

Более серьезная ошибка заключается в том, что вы индексируете vout, начиная с i1.Если вы делаете это таким образом, вам нужно выделить last+1 элемент для vout, и вы никогда не используете первый i1 (индекс 0 .. i1-1).

Исправление: сначала выделитеlast-i1+1 элементов.Во-вторых, инициализируйте k в начале 0, а не i1.В-третьих, измените окончательную копию на

for (k=i1; k<=last; k++) v[k] = vout[k-i1];

Answer 2

У вас две проблемы. Во-первых, вы неправильно вычислили среднюю точку - вы используете (upper - lower)/ 2, но это не обязательно лежит между lower и upper. То, что вы на самом деле хотите, это lower + (upper - lower) / 2. Также нет необходимости выполнять какую-либо работу, если в интервале для сортировки имеется только 1 число, поэтому функция mymergesort() должна выглядеть следующим образом:

void mymergesort (int v[], int lower, int upper)
{
    if (upper > lower) {
        int mid = lower + (upper - lower)/2;

        mymergesort(v, lower, mid);
        mymergesort(v, mid+1, upper);
        mymerge(v,lower,mid+1,upper);
    }
}

Вторая проблема - это проблема в функции mymerge(), на которую уже указал Фабиан Гизен .

Answer 3

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

void merge(int *a, int n1, int *b, int n2, int *arr)
{
  int i=0, j=0, n=0;
  while(i<n1 && j<n2)
  {
    if (a[i] < b[j])
    {
      arr[n++] = a[i];
      i++;
    }
    else
    {
      arr[n++] = b[j];
      j++;
    }
  }
  while( i < n1)
    arr[n++] = a[i++]; 
  while( j < n2)
    arr[n++] = b[j++];
}
void merge_sort(int *a, int n)
{
  int left[n/2], right[n-n/2],i=0;
  if (n<=1)
    return ;
  while(i<n/2)
    left[i] = a[i++];
  while(i<n)
    right[i - n/2] = a[i++];
  merge_sort( left, n/2 );
  merge_sort( right, n-n/2);
  merge(left, n/2, right, n-n/2, a);
}  
void main()
{
  int a[] = { 6, 5, 3, 1,9, 8, 7, 2, 4},i;
  merge_sort(a,sizeof(a)/sizeof(a[0]));
  for(i=0;i<9;i++)
    printf("--%d",a[i]);
  printf("\n");
}


-- s.k

Answer 4

#include<stdio.h>
#include<conio.h>
#define max 20
/*** function  for merging the adjecent subarrays in sorted order ***/
void merge(int A[max],int n,int low,int high, int mid)
{
     int i=low,j=mid+1,k,temp;
     while((i<=j)&&(j<=high))     
     {
        if(A[i]>A[j])          /** if element of the second half is greater then exchg and shift **/
        {
           temp=A[j];
          for(k=j;k>i;k--)    /** shifting the elements **/
           {
             A[k]=A[k-1]; 
           }
           A[i]=temp;
           j++;
        }
        i++;
     }
}
/******* iterative function for merge sort ********/
void merge_sort(int A[max],int n,int low,int high)
{
     int mid;
     if(low<high)                     /** terminating condition  **/
     {
        mid=(high+low)/2;            /** calculating the mid point ***/
        merge_sort(A,n,low,mid);     /*** recursive call for left half of the array ***/
        merge_sort(A,n,mid+1,high);  /*** recursive call for right half of the array ***/
        merge(A,n,low,high,mid);    /** merging the both parts of the array **/
     }
}
/******* begening of the main function **********/
int main()
{
    int A[max],n,i;
    /** reading the inputs fro  users **/
    printf("\n enter the size of the array\n");
    scanf("%d",&n);
    printf("\n enter the array \n");
    for(i=0;i<n;i++)
    {
       scanf("%d",&A[i]);                 
    }
    /*** calling merge sort ***/
    merge_sort(A,n,0,n-1);
    /** printing the sorted array **/
    for(i=0;i<10;i++)
    {
       printf("\n\t%d",A[i]);                 
    }
    getch();
    return 0;
}