[C] Correzione algoritmo di MergeSort

**Skass89** · 03-01-2010, 07:37

ragazzi lo correggiamo insieme? sono stato un sacco di tempo per riuscire ad eseguirlo ma non funziona mi da valori totalmente sballati....e l'errore non lo trovo

codice:

#include <stdio.h>
#define dim 100

void merge(int a[], int inf, int med, int sup);
void msort(int a[], int i, int j);


int main(){
    
    int a[dim];
    int n, i, j;
    
    printf("inserire dimensioni vettore (max %d) = ", dim);
    scanf("%d", &n);
    
    for(i=0;i<n;i++){
                     printf("a[%d] = ", i);
                     scanf("%d", &a[i]);
                     }
    
msort(a,1,n);
for(i=0;i<n;i++)
printf("%d\n", a[i]);

system("pause");
return 0;
}

void msort(int a[], int i, int j){
     
     int med,temp;
     
     if(i+1==j){
                if(a[i]>a[j]){
                             temp=a[i];
                             a[i]=a[j];
                             a[j]=temp;
                             }
                }else{
                      if(i+1<j){
                                med=(i+j)/2;
                                msort(a,i,med);
                                msort(a,med+1,j);
                                merge(a,i,med,j);
                                }
                                
                      }
}

void merge(int a[], int inf, int med, int sup){
     int i,j,k;
     int c[100];
     
     
     i=inf;
     j=med+1;
     k=inf;
     
     while((i<=med)&&(j<=sup)){
                               if(a[i]<a[j])
                               {c[k]=a[i];i++;k++;}
                               else{c[k]=a[j];j++;k++;}
                               }
     while(i<=med)
         {c[k]=a[i];i++;k++;}
     while(j<=sup)
         {c[k]=a[j];j++;k++;}
     
     for(k=inf;k<=inf;k++)
     a[k]=c[k];
}

vi aspetto con ansia

**ZannaZ** · 03-01-2010, 21:06

codice:

for(k=inf;k<=inf;k++)           
    a[k]=c[k];

**Skass89** · 03-01-2010, 21:13

e li l'errore o cosa?

**ignaziodeblasi** · 04-01-2010, 18:57

Un errore è quello perchè(con quelle due righe di codice copi nel vettore a il vettore c già ordinato) se guardi bene prima setti k con

codice:

 k=inf

e subito dopo controlli la condizione

codice:

 k<=inf

.E' normale che non ti eseguirà mai il ciclo perchè la condizione sarà sempre verificata. A te invece interessa il vettore ordinato dalla posizione inf alla posizione sup(vedi gli argomenti della funzione merge).
Quindi il ciclo for sarebbe corretto scriverlo cosi:

codice:

for(k=inf;k<sup;k++)
      a[k]=c[k];

poi ricordati che gli array in C partono da 0 : la chiamata nel main

codice:

 msort(a,1,n);

deve essere sostituita

**Skass89** · 05-01-2010, 11:25

codice:

#include <stdio.h>
#define dim 100

void merge(int a[], int inf, int med, int sup);
void msort(int a[], int i, int j);


int main(){
    
    int a[dim];
    int n, i, j;
    
    printf("inserire dimensioni vettore (max %d) = ", dim);
    scanf("%d", &n);
    
    for(i=0;i<n;i++){
                     printf("a[%d] = ", i);
                     scanf("%d", &a[i]);
                     }
    
msort(a,0,n);
for(i=0;i<n;i++)
printf("%d\n", a[i]);

system("pause");
return 0;
}

void msort(int a[], int i, int j){
     
     int med,temp;
     
     if(i+1==j){
                if(a[i]>a[j]){
                             temp=a[i];
                             a[i]=a[j];
                             a[j]=temp;
                             }
                }else{
                      if(i+1<j){
                                med=(i+j)/2;
                                msort(a,i,med);
                                msort(a,med+1,j);
                                merge(a,i,med,j);
                                }
                                
                      }
}

void merge(int a[], int inf, int med, int sup){
     int i,j,k;
     int c[100];
     
     
     i=inf;
     j=med+1;
     k=inf;
     
     while((i<=med)&&(j<=sup)){
                               if(a[i]<a[j])
                               {c[k]=a[i];i++;k++;}
                               else{c[k]=a[j];j++;k++;}
                               }
     while(i<med)
         {c[k]=a[i];i++;k++;}
     while(j<sup)
         {c[k]=a[j];j++;k++;}
     
     for(k=inf;k<=sup;k++)
     a[k]=c[k];
}

l'ho corretto...."mi ordina l'array" ma un valore sballato me lo da sempre....

**ignaziodeblasi** · 05-01-2010, 13:43

Ci sei quasi..
Allora nel main la chiamata a msort, lhai modificata quasi bene..
Almeno che non vuoi lavorare con le dimensioni dell'array, sarebbe opportuno modificare la chiamata con

codice:

 msort(a,0,n-1)

Poi nella funzione msort(dopo la modifica della chiamata nel main dovevi riadattare il tutto) non c'e bisogno di fare il controllo

codice:

 if(i+1==j)

perchè adesso questo controlla risulta errato(per la modifica della chiamata msort nel main). Basta che modifichi questa funzione con

codice:

void msort(int a[], int i, int j){

     int med;

        if(i<j){
            med=(i+j)/2;
            msort(a,i,med);
            msort(a,med+1,j);
            merge(a,i,med,j);
        }
}

(L'azione svolta nell' if eliminato si farà direttamente nella funzione merge)
Poi solo 2 precisazioni nella funzione merge: il k deve essere settato a zero(l'array c parte da zero); poi quando nelle ultime righe copi il vettore ordinato in a devi modificare il codice in :

codice:

for(k=inf;k<=sup;k++)
        a[k]=c[k-inf];

perchè copi in a (sup-inf) elementi di c (da 0 a sup-inf) però questi elementi sono quelli che in a occupano i posti da inf a sup
CIAO spero sono stato chiaro

**Skass89** · 05-01-2010, 13:56

codice:

#include <stdio.h>
#define dim 100

void merge(int a[], int inf, int med, int sup);
void msort(int a[], int i, int j);


int main(){
    
    int a[dim];
    int n, i, j;
    
    printf("inserire dimensioni vettore (max %d) = ", dim);
    scanf("%d", &n);
    
    for(i=0;i<n;i++){
                     printf("a[%d] = ", i);
                     scanf("%d", &a[i]);
                     }
    
msort(a,0,n);
for(i=0;i<n;i++)
printf("%d\n", a[i]);

system("pause");
return 0;
}

void msort(int a[], int i, int j){
     
     int med,temp;
     
   
                      if(i<j){
                                med=(i+j)/2;
                                msort(a,i,med);
                                msort(a,med+1,j);
                                merge(a,i,med,j);
                                }
                                
}


void merge(int a[], int inf, int med, int sup){
     int i,j,k;
     int c[100];
     
     
     i=inf;
     j=med+1;
     k=inf;
     
     while((i<=med)&&(j<=sup)){
                               if(a[i]<a[j])
                               {c[k]=a[i];i++;k++;}
                               else{c[k]=a[j];j++;k++;}
                               }
     while(i<med)
         {c[k]=a[i];i++;k++;}
     while(j<sup)
         {c[k]=a[j];j++;k++;}
     
     for(k=inf;k<=sup;k++)
     a[k]=c[k-inf];
}

chiaro???? sei stato fantastico...però il problema non l'abbiamo ancora risolto....diciamo che i valori sballati sono meno gravi nel senso prima mi uscivano uno o più valori del tipo
-18374612...ecc. adesso si avvicinano di più a quelli da me inseriti...spero che non esce nella tracce d'esame se no sto inguaiato....non lo capisco proprio....

**ignaziodeblasi** · 05-01-2010, 14:09

Deve funzionere ...
nel main:

codice:

msort(a,0,n-1);

Devi metterlo cosi visto che hai usato i segni di uguaglianza nelle varie funzioni.
Fammi sapere :P

**Skass89** · 05-01-2010, 14:19

codice:

#include <stdio.h>
#define dim 100

void merge(int a[], int inf, int med, int sup);
void msort(int a[], int i, int j);


int main(){
    
    int a[dim];
    int n, i, j;
    
    printf("inserire dimensioni vettore (max %d) = ", dim);
    scanf("%d", &n);
    
    for(i=0;i<n;i++){
                     printf("a[%d] = ", i);
                     scanf("%d", &a[i]);
                     }
    
msort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d\n", a[i]);

system("pause");
return 0;
}

void msort(int a[], int i, int j){
     
     int med,temp;
     
     if(i+1==j){
                if(a[i]>a[j]){
                             temp=a[i];
                             a[i]=a[j];
                             a[j]=temp;
                             }
                }else{
                      if(i<j){
                                med=(i+j)/2;
                                msort(a,i,med);
                                msort(a,med+1,j);
                                merge(a,i,med,j);
                                }
                                
                      }
}

void merge(int a[], int inf, int med, int sup){
     int i,j,k;
     int c[100];
     
     
     i=inf;
     j=med+1;
     k=inf;
     
     while((i<=med)&&(j<=sup)){
                               if(a[i]<a[j])
                               {c[k]=a[i];i++;k++;}
                               else{c[k]=a[j];j++;k++;}
                               }
     while(i<=med)
         {c[k]=a[i];i++;k++;}
     while(j<=sup)
         {c[k]=a[j];j++;k++;}
     
     for(k=inf;k<=sup;k++)
     a[k]=c[k-inf];
}

FATTO COSì FUNZIONA il controllo if

codice:

if(i+1==j){

anche se non so il perchè...sono andato per esclusione ma l'intero programma non l'ho per niente capito...comunque GRAZIE MILLE senza di te non sarei riuscito a farlo funzionare!!!!

**ignaziodeblasi** · 05-01-2010, 14:23

Ti volevo evitare questo controllo if perche' gia' questa azione viene eseguita nel merge in particolare quando ci sono solo 2 elementi nell'array.E' lo stesso cmq.. Ciao prego

Discussione: [C] Correzione algoritmo di MergeSort

Strumenti discussione

Ricerca discussione

Visualizza

[C] - mergesort che non funziona

Permessi di invio