mergesort tableau d'int utilisant des pointeurs

Question

Pour l'école, je dois programmer un tri de fusion en utilisant seulement des pointeurs. J'ai essayé presque tout, mais je ne peux pas le faire fonctionner.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define num_elementi(array) (sizeof(array)/sizeof(array[0])) 

void selsort(int arr[],int n); 
void swap(int * a, int * b); 
void print(int arr[],int n); 
void insort(int arr[],int n); 
void mergesort(int arr[],int *p,int *u); 
void merge(int arr[],int * p, int * q,int * u); 

int main(int argc, char *argv[]){ 
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61}; 
    int n=num_elementi(arr); 
    printf("numero elementi array: %d\n",n); 
    print(arr,n); 
    printf("numero elementi array: %d\n",n);  
    mergesort(arr,&arr[0],&arr[n-1]); 
    print(arr,n); 
    system("pause"); 
} 

void selsort(int arr[],int n){ 
    int *i,*j; 
    for(i=arr;i<&arr[n-1];i++){ 
     for(j=i+1;j<&arr[n];j++){ 
      if(*j<*i)swap(i,j);; 
     } 

    } 
} 

void swap(int * a, int * b){ 
    int temp; 
    temp=*a; 
    *a=*b; 
    *b=temp; 
} 

void print(int arr[],int n){ 
    int * p=arr; 
    for(p;p<&arr[n];p++)printf("%d ",*p); 
    printf("\n"); 
} 

void insort(int arr[],int n){ 
    int *i,*k; 
    for(i=&arr[1];i<&arr[n];i++){ 
     k=i-1; 
     while(k>=&arr[0]&& *k>*(k+1)){ 
      swap(k,k+1); 
      k=k-1; 
     } 
    } 
} 


void mergesort(int arr[],int *p,int *u){ 
    if (p<u){ 
     int *q=((u-p)/2)+p; 
     mergesort(arr,p,q); 
     mergesort(arr,q,u-1); 
     merge(arr,p,q,u); 
    } 

} 

void merge(int arr[],int * p, int * q,int * u){ 
    int arr1[u-p]; //inizializzazione array di dimensioni utili 
    int * i=p; //puntatore al primo elemento di arr 
    int *j=q+1; //puntatore al elemento di mezzo +1 di arr 
    int *k= arr1; //puntatore al primo elemento di arr1 
    if (u-p==1){ 
     if (*u<*p){ 
      swap(u,p); 
     } 
     return; 
    } 
    while(i<q && j<u){ 
     if(*i<*j){ 
      *k=*i; 
      i=i+1; 
     } 
     else{ 
      *k=*j; 
      j=j+1; 
     } 
     k=k+1; 
    } 
    while(i<q){*k=*i;i++;k++;} 
    while(j<u){*k=*j;j++;k++;} 

    i=p; 
    k=arr1; 
    for(i,k;i<&arr[u-p];i++,k++){ 
     *i=*k; 
    } 
} 

Quelqu'un peut-il expliquer ce que j'ai mal fait? Merci beaucoup!! PS: S'il vous plaît pardonnez mon très mauvais anglais.

EDIT nouveau code pour la suggestion de Maciej Hehl

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define num_elementi(array) (sizeof(array)/sizeof(array[0])) 

void swap(int * a, int * b); 
void print(int arr[],int n); 
void mergesort(int arr[],int * arr_begin,int * arr_end); 
void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end); 

int main(int argc, char *argv[]){ 
    int arr[]={99,12,14,65,2,7,54,78,5,1,43,59,88,28,61}; 
    int n=num_elementi(arr); 
    print(arr,n); 
    mergesort(arr,&arr[0],&arr[n-1]); 
    print(arr,n); 
    system("pause"); 
} 

void swap(int * a, int * b){ 
    int temp; 
    temp=*a; 
    *a=*b; 
    *b=temp; 
} 

void print(int arr[],int n){ 
    int * p=arr; 
    for(p;p<&arr[n];p++)printf("%d ",*p); 
    printf("\n"); 
} 

void mergesort(int arr[],int * arr_begin,int * arr_end){ 
    int * med,*arr1,*p,*p1; 
    printf("i'm doing something\n"); 
    if(arr_begin<arr_end){ 
     med=arr[arr_end-arr_begin]/2+arr_begin; 
     mergesort(arr,arr_begin,med); 
     mergesort(arr,med+1,arr_end); 
     arr1=malloc((arr_end-arr_begin)*sizeof(int)); 
     printf("msort calls ended begin merge\n"); 
     merge(arr1,arr_begin,med,med+1,arr_end); 
     for(p=arr,p1=arr1;p<arr_end&&p1<&arr1[arr_end-arr_begin];p++,p1++){ 
      *p=*p1; 
     } 
    } 

} 

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end){ 
    int *pdest=destination; 
    if (r1_end-r1_begin==1){ 
     if (*r1_end<*r1_begin){ 
      swap(r1_end,r1_begin); 
     } 
     return; 
    } 
    if (r2_end-r2_begin==1){ 
     if (*r2_end<*r2_begin){ 
      swap(r2_end,r2_begin); 
     } 
     return; 
    } 
    while(r1_begin<=r1_end&&r2_begin<=r2_end){ 
     if(*r1_begin<*r2_begin){ 
      *pdest=*r1_begin; 
      r1_begin++; 
     } 
     else{ 
      *pdest=*r2_begin; 
      r2_begin++; 
     } 
     pdest++; 
    } 
    while(r1_begin<r1_end){ 
     *pdest=*r1_begin; 
     r1_begin++;pdest++;   
    } 
    while(r2_begin<r2_end){ 
     *pdest=*r2_begin; 
     r2_begin++;pdest++; 
    } 

} 

Answer 1

A principal, si vous ajoutez un printf("*** n=%d\n", n) avant chaque appel à print, vous remarquerez que, avant le second appel, la sortie est n=61. C'est-à-dire que vous triez bien le tableau, mais au moment où vous l'imprimez une seconde fois, vous imprimez 61 numéros.
Vous pouvez également remarquer que 61 est le plus grand nombre dans le tableau, et que n est défini juste après arr, alors n et arr seront dans des adresses de mémoire consécutives dans la pile. Je pense que n est en cours d'écrasement pendant l'appel de fonction mergesoft.
Effectivement, l'écrasement se produit lorsque vous appelez mergesoft avec &arr[n]. Le dernier élément du tableau a l'index n-1. Le nième indice correspond en fait à la variable n. Changer l'appel à: mergesort(arr,&arr[0],&arr[n-1]);

Answer 2

EDIT

Vos modifications faites ma réponse originale (ci-dessous) à d'autres lecteurs absurde :) Oh, eh bien ...

La première chose est de décider si votre begin et end les pointeurs définissent une plage [début, fin] ou [début, fin]. Je suggère le premier choix car il est utilisé dans la bibliothèque C++. Si vous êtes d'accord avec cela, l'appel

mergesort(arr,&arr[0],&arr[n]); 

est correct. Vous devez changer &arr[n] en &arr[n-1] seulement si vous décidez, vous voulez les pointeurs begin et end pour définir la gamme [début, fin] que je suggère de ne pas faire.

En fait, les pointeurs begin et end suffisent pour trier la gamme et votre fonction mergesort n'a pas besoin du premier paramètre.

Le calcul de med est incorrect

med=arr[arr_end-arr_begin]/2+arr_begin; 

Il a été correct dans la version précédente (la variable a été nommé q)

Les appels ci-dessous sont également incorrectes

mergesort(arr,arr_begin,med); 
mergesort(arr,med+1,arr_end); 

premier appel est censé trier la plage [arr_begin, med), pas [arr_begin, med] (*med n'appartient pas à cette plage), donc le second c tous devraient trier la gamme commençant à med.

L'allocation de arr1 est correcte, du fait que la différence end - begin est égale au nombre d'éléments. C'est l'avantage de choisir la plage [begin, end] au lieu de [begin, end]. Ce serait bien cependant, si vous libérez la mémoire allouée après utilisation.

L'appel à fusionner est incorrect, comme les appels au mergesort ci-dessus. La deuxième plage doit débuter à med car med dépasse la première plage, et non son dernier élément.

L'implémentation de merge est trop compliquée. Vous n'avez pas besoin d'échanger quoi que ce soit. Vous prenez juste des éléments des deux gammes et les copiez à la destination. Ces trois boucles while qui ont commencé mon post original (ci-dessous) sont suffisantes, mais faites attention aux conditions.

Je répète encore une fois les points medpassé la première gamme et des points arr_endpassé la deuxième plage. En prenant cela en considération, devriez-vous utiliser les opérateurs <= ou <?

---

Je n'aime pas l'incohérence dans les conditions i<=q, j<=u, i<q, j<u dans le code suivant:

while(i<=q && j<=u){ 
    if(*i<*j){ 
     *k=*i; 
     i=i+1; 
    } 
    else{ 
     *k=*j; 
     j=j+1; 
    } 
    k=k+1; 
} 
while(i<q){*k=*i;i++;k++;} 
while(j<u){*k=*j;j++;k++;} 

Vous appelez votre mergesort comme ceci:

mergesort(arr,&arr[0],&arr[n]); 

ce qui signifie que u est un pointeur, qui pointe vers le point après le dernier élément de votre tableau. En d'autres termes, vous semblez penser à vos pointeurs, comme des itérateurs begin et end qui définissent la plage [début, fin) - *begin appartient à la gamme, mais *end pas,

Dans la définition de mergesort Vous écrivez

int *q=((u-p)/2)+p; 
mergesort(arr,p,q); 
mergesort(arr,q+1,u); 

ce qui est incompatible avec les hypothèses ci-dessus. q peut être égal à p si u == p+1.

mergesort(arr,p,q); signifie sorte la gamme [p, q) (q est passé la gamme) mergesort(arr,q+1,u); signifie sorte la gamme [q + 1, u) (u est passé la gamme)

Si vous étiez cohérent dans Votre représentation d'une plage avec des pointeurs, vous ne toucheriez jamais l'élément *q de cette façon. Considérer la plage comme [begin, end] au lieu de [begin, end] (dans le second cas, *end fait partie de la plage) est cohérent avec la façon dont les itérateurs sont utilisés en C++, mais ce n'est pas obligatoire. Vous pouvez utiliser des pointeurs pour définir la plage également dans le second sens, mais dans ce cas, vous devez modifier l'appel mergesort(arr,&arr[0],&arr[n]); à mergesort(arr,&arr[0],&arr[n-1]);. Dans les deux cas, vous devez repenser les conditions dans le code cité au début.

Ceci est un devoir, donc je ne vais pas le résoudre pour vous, mais voici un petit indice, qui pourrait aider à y penser. Redéfinir Votre merge donc il faut 2 gammes, de fusionner, de façon explicite:

void merge(int * destination, int * r1_begin, int * r1_end, int * r2_begin, int * r2_end); 

et penser comment l'utiliser. Plus tard Vous pouvez simplifier les choses. Vous n'avez pas vraiment besoin du paramètre de destination et vous n'avez pas besoin de copier tous les éléments fusionnés. Vous pouvez copier une seule plage en premier et ensuite, fusionner directement dans la destination, en prenant des éléments de la copie de la première plage et de la seconde plage.