Partage
  • Partager sur Facebook
  • Partager sur Twitter

Trier un tableau par l'algorithme de fusion

Sujet résolu
    17 février 2020 à 22:08:57

    Bonjour, voila j’essaye de trier un tableau avec le tri par fusion, mais je sais pas pourquoi mon code ne marche pas, alors que tout est en place; voila mon programme: 

    #include <stdio.h>
    #include <stdlib.h>	
    
    void fusionner(int tableau[],int debut,int milieu,int fin);
    
    void triFusion(int tableau[],int debut,int fin){
        int milieu=0;
    
        if (debut<fin)
        {
            milieu=(debut+fin)/2;
            triFusion(tableau,debut,milieu);
            triFusion(tableau,milieu+1,fin);
            fusionner(tableau,debut,milieu,fin);
        }
    }
    
    void fusionner(int tableau[],int debut,int milieu,int fin){
        int i,i1,i2;
        int tmp[100];
    
        i=1;
        i1=debut;
        i2=milieu+1;
    
        while((i1<=milieu) && (i2<=fin)){
            if(tableau[i1]<tableau[i2]){
                tmp[i]=tableau[i1];
                i1++;
            }
            else{
                tmp[i]=tableau[i2];
                i2++;
            }
            i++;
        }
    
        while(i1<=milieu){
            tmp[i]=tableau[i1];
            i1++;
            i++;
        }
    
        while(i2<=fin){
            tmp[i]=tableau[i2];
            i2++;
            i++;
        }
    
        for (int j = 0; j < fin; ++j)
        {
            tableau[j]=tmp[j];
        }
    }
    
    
    int main(){
    	int tableau[100];
    	int taille=0;
    
    	printf("donner la taille: ");
    	scanf("%d",&taille);
    
    	for (int i = 0; i < taille; ++i)
    	{
    		printf("tableau[%d]=",i+1);
    		scanf("%d",&tableau[i]);
    	}
    
    	int debut=1;
    	int fin=taille;
    
    	triFusion(tableau,debut,fin);
    
    	for (int i = 0; i < taille; ++i)
    	{
    		printf("%d\n",tableau[i]);
    	}
    	
    
    return 0;
    }

    quand je mets ses valeurs là dans mon tableau: 

    tableau[1]=4
    tableau[2]=7
    tableau[3]=2
    tableau[4]=1
    tableau[5]=9

    sa me renvoie ça:

    0
    9
    286
    6422056
    6422056
    

    svp aidez moi!



    • Partager sur Facebook
    • Partager sur Twitter
      17 février 2020 à 22:52:52

      Bonjour,

      Ton code est un peut bizarre, la variable i n'a pas de role a proprement parler, elle compte quelque chose mais on ne sait pas quoi. Ton tableau tmp ne presente auccun avantage

      #include <stdio.h>
      #include <stdlib.h>  
       
      void fusionner(int tableau[],int debut,int milieu,int fin);
       
      void triFusion(int tableau[],int debut,int fin){
          int milieu=0;
       
          if (debut<fin)
          {
              milieu=(debut+fin)/2;
              triFusion(tableau,debut,milieu);
              triFusion(tableau,milieu+1,fin);
              fusionner(tableau,debut,milieu,fin);
          }
      }
       
      void fusionner(int tableau[],int debut,int milieu,int fin){
          int i,i1,i2;
          int tmp[100]; // pourquoi tu l'utilise, inutile 
       
          i=1;// il ne commence pas a 1 mais au debut du sous tableau 
          i1=debut;
          i2=milieu+1;
       
          while((i1<=milieu) && (i2<=fin)){
              if(tableau[i1]<tableau[i2]){
                  tmp[i]=tableau[i1];
                  i1++;
              }
              else{
                  tmp[i]=tableau[i2];
                  i2++;
              }
              i++; // incrementation bonne 
          }
       
          while(i1<=milieu){
              tmp[i]=tableau[i1];
              i1++;
              i++;
          }
       
          while(i2<=fin){
              tmp[i]=tableau[i2];
              i2++;
              i++;
          }
       
          for (int j = 0; j < fin; ++j)//cette  boucle ne sert a rien en temps normal
          {
              tableau[j]=tmp[j];
          }
      }
       
       
      int main(){
          int tableau[100];
          int taille=0;
       
          printf("donner la taille: ");
          scanf("%d",&taille);
       
          for (int i = 0; i < taille; ++i)
          {
              printf("tableau[%d]=",i+1);
              scanf("%d",&tableau[i]);
          }
       
          int debut=1;//le debut d'un tableau en c est 0
          int fin=taille;
       
          triFusion(tableau,debut,fin);
       
          for (int i = 0; i < taille; ++i)
          {
              printf("%d\n",tableau[i]);
          }
           
       
      return 0;
      }

      Voila un code avec les lines a probleme avec des commentaires

      jles fautes d'orthographe sont une seconde nature pour moi

      • Partager sur Facebook
      • Partager sur Twitter

      Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il y a que la troisième qui marche

        18 février 2020 à 3:21:54

        Salut,
        « Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il y a que la troisième qui marche »
        J'ai essayé la quatrième. :)
        D'abord, stdlib.h est inutile ici.
        Il faut initialiser 'i' à 0, pas à 1, ni 'debut'.
        La correction 'i++' après les ajouts sélectifs dans 'tmp' est correcte.
        Le tableau 'tmp' est tout à fait utile! C'est trop compliqué de faire un tri fusion sur place.
        ** Je viens de le coder, c'est plus simple que je pensais. J'aimerais tester le nombre de comparaisons et de déplacements dans les deux variantes.
        (Un petit problème, 'tmp' n'est pas réservé dans le 'main'. Ce serait merdique que de jouer avec 'malloc' ici.
        Il faudrait réserver une longueur de 'fin-debut+1' et le libérer avec 'free' à la fin.)
        Sauf qu'il faut le recopier pour 'j' de 0 à 'i', pas 'fin'.
        Ensuite, on le recopie dans tableau[debut+j], pas 'tableau[j]'.
        Je me suis amusé à imprimé 'tmp' et sa longueur utilisée ('i') et c'est très intéressant de voir la progression.
        On appelle triFusion avec les indices 0 à 'taille'-1 pas 'taille'
        Les indices de tableau vont de 0 à N-1.
        Pour faire des tests, je préfère initialiser moi-même mon tableau.
        Je l'ai initialisé en ordre inverse. C'est en général le pire cas pour la plupart des tris.
        Après le tri, je teste si chaque élément est inférieur à son suivant (attention! ne pas tester le dernier avec son suivant).
        Si ça ne marche pas, on essaiera la cinquième méthode. :)
        Si je n'ai rien oublié, ça devrait marcher, ça marche sur mon ordi. J'ai testé jusqqu'à taille=100.

        -
        Edité par PierrotLeFou 18 février 2020 à 15:02:32

        • Partager sur Facebook
        • Partager sur Twitter

        Le Tout est souvent plus grand que la somme de ses parties.

          18 février 2020 à 17:49:10

          A un moment, tu recopies le tableau où tu as fait la fusion dans le tableau d'origine

           for (int j = 0; j < fin; ++j)
            {
              tableau[j] = tmp[j];
            }
          

          en supposant que les indices correspondent.


          Mais avant, ce que tu as fait, c'est fusionner les deux moitiés de la tranche (debut..fin) dans le tableau tmp à partir de l'indice 1 (qui devrait être zero mais peu importe).

          Forcément, avec ça, tes données partent un peu dans la nature.

          ---

          En fait il est plus simple, pour noter une "tranche" de tableau, d'avoir l'indice du premier élément et l'indice qui suit le dernier.

          void triFusion(int tableau[], int debut, int fin)
          {
            if (fin - debut > 1) // plus d'un élément à trier
            {
              int milieu = (debut + fin) / 2;
              triFusion(tableau, debut, milieu);
              triFusion(tableau, milieu, fin);
              fusionner(tableau, debut, milieu, fin);
            }
          }
          
          void fusionner(int tableau[], int debut, int milieu, int fin)
          {
            int tmp[100];
          
            int i = debut;
            int i1 = debut;
            int i2 = milieu;
          
            while ((i1 < milieu) && (i2 < fin))
            {
              tmp[i++] = (tableau[i1] < tableau[i2])
                             ? tableau[i1++]
                             : tableau[i2++];
            }
          
            while (i1 < milieu)
            {
              tmp[i++] = tableau[i1++];
            }
          
            while (i2 < fin)
            {
              tmp[i++] = tableau[i2++];
            }
          
            for (int j = debut; j < fin; ++j)
            {
              tableau[j] = tmp[j];
            }
          }
          

          Appel par

           triFusion(tableau, 0, taille);   // de 0 à taille-1
          



          -
          Edité par michelbillaud 18 février 2020 à 17:52:26

          • Partager sur Facebook
          • Partager sur Twitter
            18 février 2020 à 18:54:29

            @michelbillaud:
            Tu recopies des sous-tableaux dans tmp à partir de l'indice 'i' = 0, n'est-ce pas?
            Puis tu recopies tmp dans tableau de l'indice 'debut' jusqu'à 'fin'. Je me trompe?
            Ne faut-il pas faire;
            tableau[j] = tmp[j - debut];
            C'est une des erreurs qque j'ai déjà mentionnées.
            Ceci dit, j'apprécie la forme concise de ton code.
            J'ai voulu respecter la forme de l'auteur pour ne pas trop le mêler.
            La forme valeur = (condition) ? expression1 : expression2
            est mal connue et apparemment peu appréciée.
            J'ai fait la forme de tri sur place et ça demande beaucoup plus de déplacements.
            Pour un tri de 100 éléments initialement triées en ordre inverse, j'obtient:
            Sur place: 316 comparaisons, 5582 déplacements
            Avec tmp: 316 comparaisons, 1344 déplacements
            Comme je l'ai souligné, le fait que le tableau 'tmp' soit dans la fonction ou ne soit pas alloué avec 'malloc' pose une petite limitation.
            Si on veut compiler séparément les fonctions de tri et le 'main', ça pose problème.
            L'utilisation de 'malloc' pourrait alourdir le code ou impposer une surcharge à la gestion de la mémoire dynamique.
            Le tri sur place ne donne pas ce problème mais cause beaucoup plus de déplacements.
            On s'y attendais, le nombre de comparaisons est le même dans les deux cas.

            -
            Edité par PierrotLeFou 18 février 2020 à 19:27:27

            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

              18 février 2020 à 22:48:06

              Non j'utilise la même plage d'indices pour la partie à trier et la zone de tri. L'indice i commence à début, pas a 0.

              Si tu sais faire la fusion sur place, sans tableau supplémentaire, et en temps linéaire, tu devrais le publier, parce que ce n'est pas un problème simple.

              Les expressions conditionnelles "ternaires" sont un élément de la boîte à outils. Il n'y a pas à aimer ou pas aimer, il faut juste savoir s'en servir, et savoir quand les employer. Et pour savoir les employer, il faut les voir à l'oeuvre  de temps en temps.

              -
              Edité par michelbillaud 18 février 2020 à 22:54:25

              • Partager sur Facebook
              • Partager sur Twitter
                18 février 2020 à 23:47:43

                Voici le code de la fonction fusionner dans le contexte de ce sujet:
                1 void fusionner(int tableau[],int debut,int milieu,int fin){
                2     int i1,i2, tmp;
                3     i1=debut;
                4     i2=milieu+1;
                5     while((i1<i2) && (i2<=fin)){
                6         if(tableau[i1] > tableau[i2]){
                7             tmp = tableau[i2]; // Sauver le minimum se trouvant en i2.
                8             // Décaler les positionde i1 à i2-1 de 1 vers la droite.
                9             for(int k=i2-1; k >= i1; k--)    tableau[k+1] = tableau[k];
                10             tableau[i1] = tmp; // Placer l'élément venant de i2 en i1.
                ♠11            i2++; // Élément suivant de la seconde séquence.
                12         }
                13         i1++; // Nécessaire dans les deux cas.
                14     }
                15 }
                Je ne sais pas si c'est linéaire en N. Les décalages sont moins coûteux que pour le tri par insertion.
                Pour réduire le nombre de décalages et le nombre d'éléments décalée au total, il faudrait savoir combien d'éléments à partir de 'i2' peuvent être placés avant 'i1'
                Si c'est plus que 1, on se retrouve devant un décalage circulaire.
                J'ai déjà traité le sujet et ça risque de devenir assez compliqué. Voici la référence:
                https://openclassrooms.com/forum/sujet/decalage-circulaire-tableau

                -
                Edité par PierrotLeFou 19 février 2020 à 2:57:49

                • Partager sur Facebook
                • Partager sur Twitter

                Le Tout est souvent plus grand que la somme de ses parties.

                  19 février 2020 à 7:15:48

                  Non ce n'est pas linéaire, parce qu'un peu de (mal)chance, il va falloir décaler chaque élément de la moitié du tableau, et ça te donne un algorithme quadratique de fusion, donc dans la catégorie des algorithmes naïfs, comme le tri à bulles par insertion ou par sélection. Et même  pire : n² log n.

                  Google : in place merge sort.  Dans https://www.geeksforgeeks.org/in-place-merge-sort/ il y a bien la fusion sur place, mais pas en temps linéaire. Avec la conclusion que c'est en n² log n, donc que c'est pas bon, et il manque d'en tirer les conséquences, qui sont qu'il vaudrait mieux ne pas en parler :-)

                  Sinon, la fusion sur place linéaire, c'est encore un sujet de recherche chaud (papier de 2008) :

                  http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf

                  -
                  Edité par michelbillaud 19 février 2020 à 10:05:13

                  • Partager sur Facebook
                  • Partager sur Twitter
                    19 février 2020 à 15:12:58

                    Les recherches que j'ai faites ne m'ont en effet donné aucun résultat sur un tri potentiellement linéaire pour un tri sur place.
                    Toutes les variantes utilisent un tableau temporaire. La meilleure possibilité est d'utiliser un tableau correspondant à la moitié de l'intervalle.
                    Je remarque que, si la longueur est impaire, c'est la première moitié qui est la plus longue (un de plus).
                    L'idée est de copier la première moitié dans le tableau temporaire dès le début et de renvoyer la fusion dans le tableau d'origine.
                    Si on ne sauve pas de temps, on sauve la moitié de l'espace requis.
                    Si les fonctions ne savent pas la longueur à trier, il faudra penser à de l'allocation dynamique.
                    Dans l'exemple, je peux trier jusqu'à 100 éléments, mais je ne peux pas pour plus long.
                    Je reste dans le contexte où je compile séparément mes fonctions de tri et le main.
                    J'ai fait de petits test avec l'attribut 'static' et utiliser 'malloc' pour allouer l'espace.
                    Le seul hic est qu'on ne peut faire qu'un seul tri dans le programme.
                    Il faudra que je fasse une fonction 'reset' qui libère l'espace à la fin et remette le pointeur à NULL.
                    Il faudra que ce tableau soit réservé dès le premier appel à triFusion car le premier appel à fusionner ne fusionne que de petits intervalles (2 fois 1 élément)
                    Ensuite il fusionne des intervalles de plus en plus grands. Je ne veux pas passer mon temps à faire des malloc, realloc ou free.
                    Comme ça arrive trop souvent, l'auteur n'est pas très bavard, même s'il s'est connecté depuis la création de son post.
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                    Trier un tableau par l'algorithme de fusion

                    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                    • Editeur
                    • Markdown