0

Tentei recriar o algoritmo Mergesort em C++, mas ao compilar, aparece o erro "falha de segmentação". Eis o código abaixo. O que posso estar fazendo de errado?

#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;
}
2
  • O primeiro problema óbvio é que não está inicializando a memória para contar o vetor, pode ter outros.
    – Maniero
    12/03/2017 às 7:06
  • A resposta resolveu sua dúvida? Acha que pode aceitá-la? Veja o tour se não souber como faz. Isso ajudaria muito indicar que a solução foi útil para você. Também pode votar em qualquer pergunta ou resposta que achar útil no site todo.
    – Maniero
    18/03/2017 às 1:00

2 Respostas 2

2

O principal motivo é não inicializar memória para os vetores. Eu fiz usando malloc() mesmo que é do C, afinal já está usando várias coisas que só deveriam ser usadas em C mesmo.

Arrumei mais alguns problemas e organizai o código. Se o código precisa de comentário é porque ele está confuso demais.

Há outros problema no algoritmo, ele não está fazendo carto, mas pelo menos não há mais o erro descrito na pergunta.

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

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

1
  • Obrigado, bigown, pelo tempo, depois que você publicou, tentei achar um jeito melhor de passar o array para a função e dei uma revisada no algoritmo e o erro estava na função merge(): ao invés de colocar no laço for de i=0 até n1, depois j=0 até n2, havia colocado respectivamente de lo até n1 e de hi até n2, por isso a falha de segmentação
    – Benuck
    13/03/2017 às 1:12
0

Obrigado, eis o código corrigido:

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .