Problema mergesort

di il
2 risposte

Problema mergesort

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 :
#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];
        }
}

2 Risposte

  • Re: Problema mergesort

    Il compilatore ti dà un errore? Sicuro sia il compilatore?
  • Re: Problema mergesort

    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 :
    #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)
    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):
    #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];
    }
Devi accedere o registrarti per scrivere nel forum
2 risposte