Targeting failure in Mergesort

Asked

Viewed 86 times

0

I tried to recreate the Mergesort algorithm in C++, but when compiling, the error "segmentation fault" appears. Here is the code below. What could I be doing wrong?

#include <iostream>
using namespace std;
void merge (int *arr, int lo, int m, int hi){
    int n1, n2;
    n1 = m - lo + 1; //maximo do subarray1
    n2 = hi - m; //maximo do subarray2
    int *L, *R, i, j, k;
    for(i=lo; i<n1; i++){
        L[i]=arr[lo+i]; //cria array temporario para armazenar uma subarray 
    } //obs: vai de lo ateh n1-1
    for (j = hi; j< n2; j++){
    R[j]=arr[m+1+j]; //cria array temporario para armazenar outra subarray
    }// obs vai de m+1 ateh n2-1
    i=0;
    j=0;
    k=lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
    while (i<n1 && j<n2){
        if (L[i]<=R[j]){
            arr[k]=L[i]; //se o de L for menor, arr recebe de L
            i++;
        }
        else {
            arr[k]=R[j]; //se o de R for menor, arr recebe de R
            j++;
        }
        k++; //vai preenchendo arr[k]
    }
    while (i<n1){ // termina de preencher arr com o q falta de L
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j<n2){ // termina de preencher arr com o q falta de R
        arr[k] = R[j];
        j++;
        k++;
        }
    }
    void mergesort(int *arr, int lo, int hi){ //dividir e conquistar
        if (lo < hi){
            int m;
            m = (hi + lo)/2;
            mergesort (arr, lo, m);
            mergesort (arr, m+1, hi);
            merge (arr, lo, m, hi);
            }
   }
void printarr(int *arr){ //imprime array ordenado
    for (int i=0; i<sizeof(arr)/sizeof(arr[0]); i++){
        cout << arr[i] << " ";
        }
    }
int main() {
int *vetor, N;
cin >> N;
for (int i = 0; i<N; i++){
    cin >> vetor[i];
}
mergesort(vetor, 0, N);
printarr(vetor);
return 0;
}
  • The first obvious problem is that you are not initiating memory to count the vector, there may be others.

  • Did the answer solve your question? Do you think you can accept it? See [tour] if you don’t know how you do it. This would help a lot to indicate that the solution was useful to you. You can also vote on any question or answer you find useful on the entire site.

2 answers

2

The main reason is not initialize memory for the vectors. I did using malloc() even though it is from C, after all it is already using several things that should only be used in C same.

I fixed some more problems and organize the code. If the code needs comment it is because it is too confused.

There are other problems in the algorithm, it is not doing carto, but at least there is more error described in the question.

#include <iostream>
using namespace std;
void merge(int *arr, int lo, int m, int hi) {
    int n1 = m - lo + 1; //maximo do subarray1
    int n2 = hi - m; //maximo do subarray2
    int *L = (int*)malloc(sizeof(int) * n1);
    int *R = (int*)malloc(sizeof(int) * n2);
    for (int i = lo; i < n1; i++) {
        L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray 
    } //obs: vai de lo ateh n1-1
    for (int j = hi; j < n2; j++) {
        R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
    }// obs vai de m+1 ateh n2-1
    int i = 0;
    int j = 0;
    int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i]; //se o de L for menor, arr recebe de L
            i++;
        } else {
            arr[k] = R[j++]; //se o de R for menor, arr recebe de R
        }
        k++; //vai preenchendo arr[k]
    }
    while (i<n1){ // termina de preencher arr com o q falta de L
        arr[k++] = L[i++];
    }
    while (j < n2) { // termina de preencher arr com o q falta de R
        arr[k++] = R[j++];
    }
}
void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
    if (lo < hi) {
        int m = (hi + lo) / 2;
        mergesort(arr, lo, m);
        mergesort(arr, m + 1, hi);
        merge(arr, lo, m, hi);
    }
}
void printarr(int *arr, size_t size){ //imprime array ordenado
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
}
int main() {
    int N;
    cin >> N;
    int *vetor = (int *)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        cin >> vetor[i];
    }
    mergesort(vetor, 0, N);
    printarr(vetor, N);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

  • Thanks, Bigown, for the time, after you published, I tried to find a better way to pass the array to the function and I revised the algorithm and the error was in the merge() function: instead of putting in the loop from i=0 to n1, after j=0 until N2, had put it up to n1 and from hi to N2 respectively, so the segmentation failure

0

Thank you, here’s the corrected code:

#include <iostream>
using namespace std;
void merge(int *arr, int lo, int m, int hi) {
int n1 = m - lo + 1; //maximo do subarray1
int n2 = hi - m; //maximo do subarray2
int L[n1];
int R[n2];
for (int i = 0; i < n1; i++) {
    L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray 
} //obs: vai de lo ateh n1-1
for (int j = 0; j < n2; j++) {
    R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
}// obs vai de m+1 ateh n2-1
int i = 0;
int j = 0;
int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i]; //se o de L for menor, arr recebe de L
        i++;
    } else {
        arr[k] = R[j++]; //se o de R for menor, arr recebe de R
    }
    k++; //vai preenchendo arr[k]
}
while (i<n1){ // termina de preencher arr com o q falta de L
    arr[k++] = L[i++];
}
while (j < n2) { // termina de preencher arr com o q falta de R
    arr[k++] = R[j++];
}
}
void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
if (lo < hi) {
    int m = (hi + lo) / 2;
    mergesort(arr, lo, m);
    mergesort(arr, m + 1, hi);
    merge(arr, lo, m, hi);
}
}
void printarr(int *arr, size_t size){ //imprime array ordenado
for (int i = 0; i < size; i++){
    cout << arr[i] << " ";
}
}
int main() {
int N;
cin >> N;
int vetor[N];
for (int i = 0; i < N; i++) {
    cin >> vetor[i];
}
mergesort(vetor, 0, N);
printarr(vetor, N);
}

Browser other questions tagged

You are not signed in. Login or sign up in order to post.