Partage
  • Partager sur Facebook
  • Partager sur Twitter

trié un tableau

    24 juin 2019 à 2:07:24

    Bonsoir, je rencontre un problème que je ne comprend pas... 

    J'ai créer une fonction qui permet normalement de trier l'ordre de mon tableau par ordre croissant, mais les deux derniere variable de mon tableau devienne identique... et j'ai beau me creuser la tête je ne comprend pas pourquoi :euh:

    Des personnes pour m'éclairer s.v.p. ?

    ( ma fonction : )

    void ordreTableau(int tab[], int nombreTableau)
    
    {
    
        int i = 0, j = 0, tempo = 0;
    
        for (j = 0; j < nombreTableau; j++)
    
        {
    
            for (i = 0; i < nombreTableau; i++)
    
            {
    
                if (tab[i] > tab[i + 1])
    
                    {
    
                        tempo = tab[i];
    
                        tab[i] = tab[i + 1];
    
                        tab[i + 1] = tempo;
    
                        tempo = 0;
    
                    }
    
            }
    
        }
    
    }



    -
    Edité par MelvinSawada 24 juin 2019 à 15:29:56

    • Partager sur Facebook
    • Partager sur Twitter
      Staff 24 juin 2019 à 2:26:30

      Bonjour,

      Le message qui suit est une réponse automatique activée par un membre de l'équipe. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose, ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention.
      Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé.

      Pour plus d'informations, nous vous invitons à lire les règles générales du forum

      Merci de colorer votre code à l'aide du bouton Code

      Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton Code de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: cpp;">Votre code ici</pre>.

      • Partager sur Facebook
      • Partager sur Twitter
        24 juin 2019 à 7:33:12

        Quand tu fait tab[i+1] avec i égal à nombreTableau-1, tu sort de ton tableau.

        Pourquoi faire tempo = 0 après l'échange??

        • Partager sur Facebook
        • Partager sur Twitter

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

          24 juin 2019 à 9:10:44

          Conseil : au lieu d'attendre que l'inspiration géniale vienne du ciel, simuler sur le papier le déroulement du programme sur un exemple de petite taille dont on constate qu'il déraille.

          Ici un tableau à 2 éléments suffit à constater le problème.

          -
          Edité par michelbillaud 24 juin 2019 à 9:11:46

          • Partager sur Facebook
          • Partager sur Twitter
            24 juin 2019 à 15:08:24

            Merci a vous de vos réponse rapide !

            PierrotLeFou a écrit:

            Quand tu fait tab[i+1] avec i égal à nombreTableau-1, tu sort de ton tableau.

            Pourquoi faire tempo = 0 après l'échange??


            Car je voulais le remettre a 0, mais c'est vrai que a partir du moment ou je lui donne la valeur de mon tableau au début de la fonction if, il n'y a aucun interet ^^'

            Et je n'es pas mis de nombreTableau - 1, que voulais tu dire par la ?

            Cordialement, le newfag.

            -
            Edité par MelvinSawada 24 juin 2019 à 15:16:50

            • Partager sur Facebook
            • Partager sur Twitter
              24 juin 2019 à 15:31:02

              Si tu fais i < nombreTableau, tu te rends jusqu'à nombreTableau - 1, pas vrai?

              À quoi sert la variable j?

              J'aurais attendu for(i = j+1; i < nombreTableau; i++)

              comparer tab[i] et tab[j]

              et échanger tab[i] et tab[j]

              • Partager sur Facebook
              • Partager sur Twitter

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

                24 juin 2019 à 16:55:38

                PierrotLeFou a écrit:

                Si tu fais i < nombreTableau, tu te rends jusqu'à nombreTableau - 1, pas vrai?

                Ben imaginons que nombreTableau = 5;

                si i arrive a 4, ca fait i(4) < nombreTableau(5)

                donc la boucle for est sensé se relancer une derniere fois non ?

                PierrotLeFou a écrit:

                À quoi sert la variable j?


                La variable (j) permet de relancer la boucle for du début autant de fois que il y a de nombreTableau, pour bien mettre en place les variables dans le tableau, car imaginons encore une fois :

                tab[5] = { 8, 5, 12, 2, 13}

                Si je met qu'une boucle for, la fonction vas certe faire ceci :

                1/ if (tab[0] > tab[1])

                5, 8, 12, 2, 13

                2/ if(tab[1] > tab[2])

                5, 8, 12, 2, 13 // le if ne change rien, puisque c'est ok !

                3/ if (tab[2] > tab[3])

                5, 8, 2, 12, 13

                4/ if (tab[3] > tab[4])

                5, 8, 2, 12, 13 // rien non plus car ok !

                5/ J'suis un gros con, et je viens de comprendre pourquoi le -1 sur le nombreTableau du coup ..... 

                Mais du coup la boucle for(j) permet de refaire la boucle for (i) autant de fois qu'il y a de variable dans le tableau pour bien tout retrier

                -
                Edité par MelvinSawada 24 juin 2019 à 17:30:42

                • Partager sur Facebook
                • Partager sur Twitter
                  24 juin 2019 à 17:46:49

                  Michel va m'assassiner et AbcAbc6 croiera avoir perdu son temps, mais je ne peux rejoindre correctement le bouton "code".

                  Il faut effectivement deux boucles.

                  Voici le code que je suggère:

                  .void fonctionTri(int tab[], int nombreTableau) {

                  . int i, j, m; // je n'aime pas initialiser sans raison

                  . for(j = 0; j < nombreTableau; j++) {

                  . m=j; // minimum initial

                  . for(i = j+1; i < nombreTableau; i++) {

                  . if(tab[i] < tab[m]) m=i; // nouveau minimum

                  . }

                  . if(m != j) { // interchanger si différent du premier

                  . tempo = tab[j];

                  . tab[j]=tab[m];

                  . tab[m]=tempo;

                  . }

                  . }

                  .}

                  Tu feras (n*(n-1))/2 comparaisons et au maximum n-1 échanges.

                  Avec ton code, tu fais n*n comparaisons.

                  • Partager sur Facebook
                  • Partager sur Twitter

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

                    24 juin 2019 à 18:51:43

                    Pour l'instant je n'ai encore assassiné personne, du moins on n'a pas pu le prouver.

                    En C "normal" (c-a-d aux normes actuelles), on déclare les variables là où on en a besoin, en général quand on peut leur donner une valeur qui a un sens

                    Par conséquent la variable m, qui sert à  noter la position du maximum au tour i, elle se déclare dans la boucle sur i.

                    Et quand c'est la variable de contrôle d'une boucle for, et qu'on n'en n'a pas besoin de la connaitre à l'extérieur, on la déclare dans la première partie du for. Ce qui donne quelque chose comme ça

                    void triParRechercheduMaximum(int tableau[], int taille) {
                    
                      for (int j = 0; j < taille - 1; j++) {
                          // recherche de l'indice du minimum entre positions j à taille-1
                          int m = j;    
                          for (int i = j + 1; i < taille; i++) {
                              if (tableau[i] < tableau[m]) {
                                m = i;
                              }
                          }
                          //  mise en place
                          int tempo = tableau[j];
                          tableau[j] = tableau[m];
                          tableau[m] = tempo;
                      }
                    }

                    Commentaire :

                    1. j'ai fait sauter le test if (i != m) parce qu'il risque en fait d'être contre productif. Ok il est censé économiser 3 instructions d'échange dans le cas où i = j; mais ça se fait au prix d'un test à chaque tour de boucle. Donc il faut voir les probabilités

                    Si on a un tableau aléatoire de 10 éléments  à trier, on va estimer qu'il y a 9 chances sur  10 que ne fasse pas d'économie au premier tour,  8/9 au second, etc.  Donc ça coute 10 tests + (9/10 + 8/9 +  ... 1/2)*3  affectations, donc 10 tests + 21,.. affectations = 31 instructions. Pas mieux que la version bête sans if.

                    Autre facteur qui rentre en jeu : le if risque de créer une bulle dans le pipeline des instructions.  Comme quoi il faut se méfier en matière d'optimisations, c'est un truc sur lequel l'intuition déconne souvent.

                    2. on arrête la boucle extérieure un coup plus tôt parce que, comme on procède par échanges, une fois qu'on a placé les taille-1 premiers éléments, le dernier est à sa place, donc on gagne le dernier échange.

                    Je me rappelle que quand j'ai commencé à programmer, il y a très longtemps dans une lointaine galaxie, je me suis surpris à écrire quelque chose comme ça :

                    if ( x != 0 ) {   // on initialise si il y a besoin
                       x = 0;
                    }
                    

                    avant de réaliser que c'était complètement con :-)



                    -
                    Edité par michelbillaud 24 juin 2019 à 19:02:39

                    • Partager sur Facebook
                    • Partager sur Twitter
                      24 juin 2019 à 22:45:31

                      Tu viens d'une galaxie lointaine, j'ai programmé à l'âge des dinosaures, c'est à dire avant 1999.

                      Je n'ai jamais vu (et je voyais à l'époque) de telles définitions.

                      Je suis d'accord que mon if ne sauve pas grand chose, statistiquement parlant. Ce que je ne savais pas est qu'il peut forcer la recharge du stack d'instructions.

                      Je faisais un jump en assembler justement pour le forcer si j'avais une boucle in-stack.

                      Dans ce cas, je pensais que la rupture ne se ferait que si le test était faux.

                      En passant, je me suis trompé sur le nombre de comparaisons, c'est (n*(n+1))/2 au lieu de (n-1).

                      • Partager sur Facebook
                      • Partager sur Twitter

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

                        24 juin 2019 à 23:19:43

                        edit : Mon sac est fait.

                        bonne soirée

                        -
                        Edité par MelvinSawada 24 juin 2019 à 23:23:22

                        • Partager sur Facebook
                        • Partager sur Twitter
                          25 juin 2019 à 0:50:04

                          michelbillaud:

                          Ai-je mal codé mes acollades ou tu m'en a passé une petite vite? :)

                          Le  if(m != j)  est à l'extérieur de la boucle sur les  i.

                          Donc, je ne fais le test et les échanges que nombreTableau-1 fois, pas plus (voire moins pour les échanges).

                          Ok! C'est peut-être encore trop.

                          • Partager sur Facebook
                          • Partager sur Twitter

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

                            25 juin 2019 à 7:38:38

                            Pierrot le fou:

                            C'est ce que je dis : les n-1 tests, qui sont faits dans la boucle exterieure, sont en fait pénalisants.

                            Si l'âge des dinosaures était en 1999, que se passait-il en 1976?

                            Mais là on cause de microoptimisation sur des algorithmes qui sont de toute façon quadratique (durée d'exécution asymptotiquement proportionnelle au carré du nombre d'éléments à traiter). Si on veut vraiment avoir des performances raisonnables, il faut complètement changer d'algorithme au lieu de bricoler.

                            -
                            Edité par michelbillaud 25 juin 2019 à 7:44:13

                            • Partager sur Facebook
                            • Partager sur Twitter
                              25 juin 2019 à 14:52:01

                              Je tentais de répondre au problème de départ. Bien sûr, on aurait pu lui suggérer le quicksort, mais ce n'est pas ce qu'il voulait programmer.

                              Je voulais lui montrer le meilleur du pire. Dans son code, il faisait environ n*n échanges au max, et je n'en fait que n-1 au max. Sans compter les problèmes de débordement dans son tableau.

                              Pour 1976, il y a avait encore des cartes perforées et des bandes magnétiques. As-tu connu les rubans papier perforés?

                              • Partager sur Facebook
                              • Partager sur Twitter

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

                                25 juin 2019 à 15:12:08

                                J'ai connu les bandes magnétiques et les cartes perforées.... et l'horreur lorsque ton paquet de cartes non numérotées t'échappe des mains et se retrouve éparpillé au sol :D

                                -
                                Edité par edgarjacobs 25 juin 2019 à 16:04:43

                                • Partager sur Facebook
                                • Partager sur Twitter

                                Aucune aide ne sera donnée par mp

                                  25 juin 2019 à 16:54:56

                                  PierrotLeFou a écrit:

                                  Pour 1976, il y a avait encore des cartes perforées et des bandes magnétiques. As-tu connu les rubans papier perforés?

                                  Hé c'était pas un ordinateur jouet, c'était un IRIS 80, l'ordinateur le plus puissant fabriqué par la CII-HB


                                  Alors on tapait les cartes sur des perfos IBM 29

                                  https://www.youtube.com/watch?v=YnnGbcM-H8c

                                  et ça partait au centre de calcul, pour revenir sous forme de paquet de cartes emballé dans le listing.

                                  Curieusement, je n'ai jamais fais tomber mes paquets de cartes.

                                  -
                                  Edité par michelbillaud 25 juin 2019 à 16:57:19

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    25 juin 2019 à 18:20:43

                                    Je n'ai pas connu les Iris. J'ai travaillé sur le CDC 6600 de Control Data Corporation qui était supposé l'ordinateur le plus puissant de la planète en 1972.

                                    Il fonctionnait à la vitesse fulgurante de 10 MHz (pas GHz!).

                                    Mon médiocre 4790K fonctionne 400 fois plus rapidement.

                                    Moi non plus, je n'ai jamais échappé mes paquets de cartes. Je me suis souvent battu avec les erreurs de parité sur les bandes magnétiques.

                                    • Partager sur Facebook
                                    • Partager sur Twitter

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

                                    trié un tableau

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