Problema mergesort

Forum di discussioni su C e C++

Moderatori: Toki, skynet

Regole del forum
Leggi: IProgrammatori.it - Regolamento Forum
Alexgd96
New Entry
Messaggi: 2
Iscritto il: 12 ott 2017, 11:02

Problema mergesort

Messaggioda Alexgd96 » 12 ott 2017, 11:11

Ho un problema con questo algoritmo, quando lo vado ad eseguire Windows smette di funzionare e il compilatore mi da un errore ma non capisco il problema. Questo è il codice :

Codice: Seleziona tutto

#include <iostream>
using namespace std;

void mergesort(int a[], int left, int right);
void merge(int a[], int left, int center, int right);

int main()
{
    int n;
    int v[n];
    cout<<"inserisci il numero";
    cin>>n;
    int i;
    for(i=1;i<n+1;i++)
    {
            cout<<"inserisci un valore :";
            cin>>v[i];
    }
    mergesort(v,1,n);
    for(i=1;i<n+1;i++)
    {
            cout<<"Ordinato : "<<v[i];
    }
    return 0;
}

void mergesort(int a[], int left, int right)
{
        int center=(left+right)/2;
        mergesort(a,left,center);
        mergesort(a,center+1,right);
        merge(a,left,center,right);

}

void merge(int a[], int left, int center, int right)
{
        int i,j,k;
        int b[100];
        i = left;
        j = center + 1;
        k = 0;
        while((i<=center) && (j<=center))
        {
                if(a[i]<=a[j]) {b[k]=a[i]; i++;}
                else           {b[k]=a[j]; j++;}

                while(i<=center)
                {
                        b[k]=a[i];
                        i++;
                        k++;
                }
                while(i<=right)
                {
                        b[k]=a[j];
                        j++;
                        k++;
                }
                for(k=left;k<=right;k++)
                        a[k]=b[k-left];
        }
}
oregon
Utente Senior
Messaggi: 9679
Iscritto il: 20 nov 2011, 18:54
Località: Roma

Re: Problema mergesort

Messaggioda oregon » 12 ott 2017, 11:13

Il compilatore ti dà un errore? Sicuro sia il compilatore?
___________________
"Il gioco del Lotto : la tassa sull'imbecillità". (Bruno De Finetti, grande matematico italiano)
spx
New Entry
Messaggi: 3
Iscritto il: 09 ott 2017, 23:20

Re: Problema mergesort

Messaggioda spx » 14 ott 2017, 10:04

Alexgd96 ha scritto:Ho un problema con questo algoritmo, quando lo vado ad eseguire Windows smette di funzionare e il compilatore mi da un errore ma non capisco il problema. Questo è il codice :

Codice: Seleziona tutto

#include <iostream>
using namespace std;

void mergesort(int a[], int left, int right);
void merge(int a[], int left, int center, int right);

int main()
{
    int n;
    int v[n];
    cout<<"inserisci il numero";
    cin>>n;
    int i;
    for(i=1;i<n+1;i++)
    {
            cout<<"inserisci un valore :";
            cin>>v[i];
    }
    mergesort(v,1,n);
    for(i=1;i<n+1;i++)
    {
            cout<<"Ordinato : "<<v[i];
    }
    return 0;
}

void mergesort(int a[], int left, int right)
{
        int center=(left+right)/2;
        mergesort(a,left,center);
        mergesort(a,center+1,right);
        merge(a,left,center,right);

}

void merge(int a[], int left, int center, int right)
{
        int i,j,k;
        int b[100];
        i = left;
        j = center + 1;
        k = 0;
        while((i<=center) && (j<=center))
        {
                if(a[i]<=a[j]) {b[k]=a[i]; i++;}
                else           {b[k]=a[j]; j++;}

                while(i<=center)
                {
                        b[k]=a[i];
                        i++;
                        k++;
                }
                while(i<=right)
                {
                        b[k]=a[j];
                        j++;
                        k++;
                }
                for(k=left;k<=right;k++)
                        a[k]=b[k-left];
        }
}

Ciao! Dal tuo modo di scrivere codice direi che sei alle primissime armi. Per questo motivo non ti posterò un mergesort impeccabile come farebbe il vanitoso di turno perchè credo non ti servirebbe a nulla. In compenso però ho modificato il tuo codice in modo che funzioni. Non ho commentato quasi nulla perchè lascio a te il compito di confrontarlo con il tuo e capire quali fossero gli errori. Ti lascio solo alcuni consigli che sicuramente ti saranno comodi:
1)

Codice: Seleziona tutto

int n;
    int v[n];
    cout<<"inserisci il numero";
    cin>>n;

Una dichiarazione del genere è sbagliata. Hai due possibilità: puoi impostare una dimensione massima per l'array (per esempio 100) ed assicurarti che l'utente non inserisca una sequenza con più di 100 elementi, oppure utilizzare l'allocazione dinamica (basta cercare in rete per la spiegazione su cosa sia).

2)Convenzionalmente gli indici partono da 0 quindi, a meno di casi particolari, vanno inizializzati a tale valore

Di seguito il codice funzionante (comunque non scritto benissimo):

Codice: Seleziona tutto

#include <iostream>
using namespace std;

void mergesort(int a[], int left, int right);
void merge(int a[], int left, int center, int right);

int main()
{
    int n;
    int v[100];
    cout<<"inserisci il numero: ";
    cin>>n;
    int i;
    for(i=1;i<n+1;i++)
    {
            cout<<"inserisci un valore: ";
            cin>>v[i];
    }
    mergesort(v,1,n);
    cout<<"Ordinato : ";
    for(i=1;i<=n;i++)
    {
            cout<<v[i]<<" ";
    }
    return 0;
}

void mergesort(int a[], int left, int right)
{
      //CASO BASE: se left>=right significa che la sottosequenza ha dimensione <=1 e quindi non effettuo nessuna chiamata ricorsiva
      if(left<right){
           int center=(left+right)/2;
           mergesort(a,left,center);
           mergesort(a,center+1,right);
           merge(a,left,center,right);
       }

}

void merge(int a[], int left, int center, int right)
{
        int i,j,k;
        int b[100];

        i = left;
        j = center + 1;
        k =1;
        while((i<=center) && (j<=right))
        {
                if(a[i]<=a[j]) {b[k]=a[i]; i++; k++;}
                else           {b[k]=a[j]; j++; k++;}
        }
      while(i<=center)
               {
                        b[k]=a[i];
                        i++;
                        k++;
                }
        while(j<=right)
                {
                        b[k]=a[j];
                        j++;
                        k++;
                }
       for(k=left;k<=right;k++)
            a[k]=b[k-left+1];
}

Torna a “C/C++”

Chi c’è in linea

Visitano il forum: Nessuno e 163 ospiti