csortingsegmentation-faultmergesort

Merge sort an array of structs


I'm trying to merge sort an array of structs, I've had many different seg faults but at the moment its happening in the arrayCopy function:

void arrayCopy(item10array dest[], item10array src[], const int lenght, const int leftShift) {
    for (int i = 0; i < lenght; i++) {
        structCopy(dest[i], src[leftShift + i]);
    }
}

I have changed small things until I pushed the seg fault into the function arrayCopy, I dont understand what is causing the error.

typedef struct 
{
    char Nome[50]; //vem do ficheiro ruas.txt
    unsigned int int_arr[6];
    char char_arr[6];
} Arteria;

typedef struct
{
    Arteria arteria;
    int cont;
} item10array;

void structCopy(item10array dest, item10array src) {

    strcpy(dest.arteria.Nome, src.arteria.Nome);

    for (int j = 0; j < 6; j++) {
        dest.arteria.int_arr[j] = src.arteria.int_arr[j];
        dest.arteria.char_arr[j] = src.arteria.char_arr[j];
    }

    dest.cont = src.cont;
}

void arrayCopy(item10array dest[], item10array src[], const int lenght, const int leftShift) {
    for (int i = 0; i < lenght; i++) {
        structCopy(dest[i], src[leftShift + i]);
    }
}

void mergeSorted(item10array *array, const int l, const int m, const int r) {
    int left_lenght = m - l + 1;
    int right_lenght = r - m;

    item10array temp_left[left_lenght];
    item10array temp_right[right_lenght];

    int i, j, k;

    arrayCopy(temp_left, array, left_lenght, l);
    arrayCopy(temp_right, array, right_lenght, m + 1);

    for (i = 0, j = 0, k = l; k <= r; k++) {
        if ((i < left_lenght) && (j >= right_lenght || temp_left[i].cont <= temp_right[j].cont)) {
            structCopy(array[k], temp_left[i]);
            i++;
        } else {
            structCopy(array[k], temp_right[j]);
            j++;
        }
    }  
}

void sortRecursion(item10array *arrray, int l, int r) {
    //isto é desnecessario mas dá me paz de alma
    if (r <= 1)
        return;
    if (l < r) {
        //encontrar o meio do array
        int m = l + (r - l) / 2;

        sortRecursion(arrray, l, m);
        sortRecursion(arrray, m + 1, r);

        mergeSorted(arrray, l, m, r);
    }
}

void sortItem10(item10array *rua, int lenght) {
    sortRecursion(rua, 0, lenght - 1);
}

void item10letra(Arteria *origin_ptr) {
    item10array rua[345] = {{"0", 0, 0, 0}};
    for (int i = 0; i < 345; i++) {
        rua[i].arteria = origin_ptr[i];
    }
    char letra;
    int cont = 0;
    int lenght = sizeof(item10array) * 345;

    for (int i = 0; i < 345; i++) {
        rua[i].arteria = origin_ptr[i];
    }

    for (int i = 0; i < 345; i++) {
        for (int j = 0; j < 6 && rua[i].arteria.char_arr[j] != 0; j++) {
            if (rua[i].arteria.char_arr[j] == letra) {
                cont++;
            }
        }
        rua[i].cont = cont;
    }

    sortItem10(rua, lenght);
}

Some things aren't named in English, that's because I'm also not named in English.

Thanks.


Solution

  • As posted, structCopy does not do anything useful because the src and dest structures are passed by value, so assigning the members of src to those of dest only modifies the function argument and has no effect on the structure arrays passed to arrayCopy.

    Structures can be copied simply by assignment. Here is a modified version of arrayCopy:

    void arrayCopy(item10array dest[], const item10array src[],
                   int length, int leftShift) {
        for (int i = 0; i < length; i++) {
            dest[i] = src[leftShift + i];
        }
    }
    

    The problem in your sort program is elsewhere:

    Here is a modified version of your code:

    typedef struct {
        char Nome[50]; //vem do ficheiro ruas.txt
        unsigned int int_arr[6];
        char char_arr[6];
    } Arteria;
    
    typedef struct {
        Arteria arteria;
        int cont;
    } item10array;
    
    void arrayCopy(item10array dest[], const item10array src[],
                   int length, int leftShift) {
        for (int i = 0; i < length; i++) {
            dest[i] = src[leftShift + i];
        }
    }
    
    void mergeSorted(item10array *array, int l, int m, int r) {
        int left_length = m - l;
        int i, j, k;
        item10array temp_left[left_length];
    
        // only save the left part, elements in the right part are
        // never overwritten before they are copied.
        arrayCopy(temp_left, array, left_length, l);
    
        for (i = 0, j = m, k = l; k < r; k++) {
            if (i < left_length
            &&  (j >= r || temp_left[i].cont <= array[j].cont)) {
                array[k] = temp_left[i++];
            } else {
                array[k] = array[j++]);
            }
        }  
    }
    
    void sortRecursion(item10array *array, int l, int r) {
        if (r - l > 1) {
            // encontrar o meio do array
            int m = l + (r - l) / 2;
    
            sortRecursion(array, l, m);
            sortRecursion(array, m, r);
            mergeSorted(array, l, m, r);
        }
    }
    
    void sortItem10(item10array *rua, int length) {
        sortRecursion(rua, 0, length);
    }
    
    void item10letra(Arteria *origin_ptr) {
        item10array rua[345] = {{"0", 0, 0, 0}};
        int length = sizeof(item10array) / sizeof(item10array[0]);
        char letra = 'a';
    
        for (int i = 0; i < length; i++) {
            int cont = 0;
            rua[i].arteria = origin_ptr[i];
            for (int j = 0; j < 6 && rua[i].arteria.char_arr[j] != 0; j++) {
                if (rua[i].arteria.char_arr[j] == letra) {
                    cont++;
                }
            }
            rua[i].cont = cont;
        }
        sortItem10(rua, length);
    }