Falla de segmentación: núcleo abandonado en la función MergeSort

segmentation-fault

Question

¿Alguien puede darnos una idea de por qué la siguiente sección de código daría como resultado un error de segmentación (núcleo volcado)? Estoy seguro de que tengo un puntero extraviado o algo así; sin embargo, no puedo encontrarlo. Cualquier ayuda sería apreciada. Estoy tratando de crear una función 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

No asigna memoria en la función de split :

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

El código anterior en realidad no hace nada útil: modifica sus argumentos, punto. Los argumentos mismos no sobreviven a la llamada de función.

En su lugar, debe asignar copias de las mitades izquierda y derecha de la matriz:

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

Esta no es la implementación más eficiente de mergesort ya que usa el espacio N*log(N) , pero debería funcionar.

Una solución más eficiente es copiar el contenido de la matriz justo antes de la fase de fusión: la split podría escribirse para modificar los punteros a los que recibe direcciones:

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

Pero realmente no es necesario, ya que usar la left y la right para 2 propósitos diferentes es confuso. De hecho, necesita hacer copias de las mitades para pasar a la función de merge , de modo que este último no bloquee los datos a medida que se fusiona en su lugar:

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

En realidad, no es necesario guardar ambas mitades antes de la fase de fusión: si modifica el cálculo del punto middle para asegurarse de que la mitad izquierda sea al menos tan larga como la mitad derecha ( middle = (n+1) >> 1; ), entonces solo necesita guardar la mitad izquierda ya que la fase de fusión no sobrescribirá los elementos que aún no ha copiado. Con este método, ni siquiera necesita agregar la mitad derecha ya que estará en el lugar correcto.

Las funciones split , insert y append deben plegarse en merge . Pasar todas estas variables por referencia conduce a un código complicado, propenso a errores e ineficiente. merge y mergesort devuelven int* sin ningún propósito real, los void .

Un problema menos importante: la comparación en insert() debería ser <= para lograr una clasificación estable (no es un problema para una matriz de int , pero es útil si se generaliza el algoritmo a elementos más complejos).