Ошибка сегментации - Сброс сердечника в функции MergeSort

Question

Может ли кто-нибудь объяснить, почему следующий раздел кода привел к ошибке с ошибкой сегментации (с явным сбросом)? Я уверен, что у меня странный указатель или что-то еще; однако я не могу его найти. Любая помощь будет оценена по достоинству. Я пытаюсь создать функцию MergeSort.

int* mergesort(int* num, int n) 
{ 
    int *left, *right; 
    int middle = n/2; 

    if (n <= 1) 
     return num; 

    //split array into two halves each with elements of 0...middle-1 and middle...n-1 correspondingly 
    split(num, n, &left, &right, middle); 
    left = mergesort(left, middle); 
    right = mergesort(right, n-middle); 

    merge(num, left, right, middle, n-middle); 

    free(left); 
    free(right); 

    return num; 
}  

void split(int* num, int n, int** left, int** right, int middle) 
{ 

    left = &num; 
    right = &num + middle; 

} 

int* merge (int* num, int* left, int* right, int sizeLeft, int sizeRight) 
{ 
    int i, j, k, n; 
    i = j = k = 0; 
    n = sizeLeft + sizeRight; 

    while (k < n) 
    { 
     if (i < sizeLeft) 
     { 
      if (j < sizeRight) 
      { 
       insert(num, left, right, &i, &j, &k); 
      } 
      else 
      { 
       append(num, left, sizeLeft, &i, &k); 
      } 
     } 
     else 
     { 
      append (num, right, sizeRight, &j, &k); 
     } 
    } 
} 

void insert(int* num, int* left, int* right, int* i, int* j, int*k) 
{ 
    if (left[*i] < right[*j]) 
    { 
     num[*k] = left[*i]; 
     (*i)++; 
    } 
    else 
    { 
     num[*k] = right[*j]; 
     (*j)++; 
    } 

    (*k)++; 
} 

void append(int* num, int* half, int sizeHalf, int* i, int* k) 
{ 
    while (*i < sizeHalf) 
    { 
     num[*k] = half[*i]; 
     (*i)++; (*k)++; 
    } 
} 

Answer 1

Вы не выделять память в функции split:

void split(int* num, int n, int** left, int** right, int middle) { 
    left = # 
    right = &num + middle; 
} 

код, указанный выше на самом деле ничего не делает полезной: она изменяет его аргументы, период. Сами аргументы не выходят за вызов функции.

Вы должны вместо этого выделить копии левой и правой половин массива:

void split(int *num, int n, int **left, int **right, int middle) { 
    *left = malloc(middle * sizeof(**left)); 
    memcpy(*left, num, middle * sizeof(**left)); 
    *right = malloc((n - middle) * sizeof(**right)); 
    memcpy(*right, num + middle, (n - middle) * sizeof(**right)); 
} 

Это не самая эффективная реализация mergesort, как он использует N*log(N) пространство, но он должен работать.

Более эффективное решение, чтобы скопировать содержимое массива непосредственно перед фазой слияния: split может быть записан, чтобы изменить указатели, на которые он получает адрес:

void split(int *num, int n, int **left, int **right, int middle) { 
    *left = num; 
    *right = num + middle; 
} 

Но это на самом деле не нужно, как используя left и right для 2 различных целей, если сбивать с толку. Действительно, Вы должны сделать копии половин, чтобы перейти к merge функции так тэ последний не затирать данные, как она сливается в месте:

mergesort(num, middle); 
mergesort(num + middle, n-middle); 

left = malloc(middle * sizeof(*left)); 
memcpy(left, num, middle * sizeof(*left)); 
right = malloc((n - middle) * sizeof(*right)); 
memcpy(right, num + middle, (n - middle) * sizeof(*right)); 

merge(num, left, right, middle, n-middle); 

free(left); 
free(right); 

Вы на самом деле не нужно, чтобы сохранить обе половины до фазы слияния : если вы измените вычисление точки middle, чтобы убедиться, что левая половина меньше, чем правая половина (middle = (n+1) >> 1;), вам просто нужно сохранить левую половину, поскольку фаза слияния не будет перезаписывать элементы, которые еще не были скопировано. С помощью этого метода вам даже не нужно добавлять правую половину, поскольку она уже будет в нужном месте.

Функции split, insert и append следует сложить на merge. Передача всех этих переменных по ссылке приводит к сложному, подверженному ошибкам и неэффективному коду. merge и mergesort оба возвращают int* для реальной цели, делают их void.

Менее важный вопрос: сравнение в insert() должно быть <= для достижения стабильного рода (не проблема для массива int, но полезно, если вы обобщить алгоритм более сложные элементы).