Mergesort targeting failure

0

I tried to recreate the Mergesort algorithm in C ++, but when compiling, the error "targeting failure" appears. Here is the code below. What can 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;
}
    
asked by anonymous 12.03.2017 / 04:11

2 answers

2

The main reason is not to initialize memory for the vectors. I've done using malloc() even though it's odo C, after all it's already using several things that should only be used in C itself.

I got some more problems and organized the code. If the code needs comment it is because it is too confusing.

There are other problems in the algorithm, it is not making a card, but at least there is no 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);
}

See running on ideone . And at Coding Ground . Also I put it in GitHub for future reference .

    
12.03.2017 / 08:22
0

Thanks, here is 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);
}
    
13.03.2017 / 02:26